刷题笔记


9.26日考试

T1:质因数分解+快速幂 将N!进行质因数分解 如果分解质数的个数为奇数就删掉一个如果为
    偶数则直接乘入答案
T2:树状数组求逆序对  如果[l,r]是合法的 那么对于[l,r]中的每一个数都减一个L则∑≥0
    并且如果都减一个R则∑≤0
    我们用A[i]表示前i个数的前缀和
    那么不合法状态就是对于区间[l,r]中的每一个数如果减一个L那么A[r]-A[l-1]<0则
    A[l-1]>A[r] 如果都用R减去这个数 那么A[l-1]>A[r]为不合法状态
    于是问题就转换为了一个求前缀和逆序对的问题
T3:搜索 对于k=1的数据可以直接求解  对于其他数据可以进行搜索 判断对于当前这个葱是和
    前面的放在一个栅栏里还是自己再用一个栅栏  最终去最优解  剪枝:最优化剪枝

Read More

9.28考试

T1:他

题目

一张长度为N的纸带,我们可以从左至右编号为0−N(纸带最左端标号为
0)。现在有M次操作,每次将纸带沿着某个位置进行折叠,问所有操作之后纸带
的长度是多少。

Read More

9.27小测试

T1:删除

题目

现在,我的手上有 n 个数字,分别是 a1, a2, a3, …, an。
我现在需要删除其中的 k 个数字。当然我不希望随随便便删除,我希望删除 k
数字之后,剩下的 n − k 个数中有最多的不同的数。

Read More

刷墙

题目

Bessie从栅栏上的位置0开始,并且遵循着一个N次移动的次序(1 <= N <=
100,000)。例如“10 L”表示Bessie向左移动了10个单位长度,“15 R”表
示Bessie向右移动了15个单位长度。现给出Bessie所有移动的列表,Farmer
John想要知道哪些区域的栅栏至少涂了两层涂料(只涂一层涂料的区域可能在大雨
中被洗掉)。Bessie在她的行走中最远到达距起始点1,000,000,000个单位长度

Read More

出租车拼车

题目

假设 N 位 Oier 准备拼车,此时为 0 时刻,从校门到目的地需要支付给出租

车师傅 D 元(按车次算,不管里面坐了多少 Oier),假如 S 分钟后恰能赶上比赛,

Read More

书本整理

题目

Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。

Read More

观光公交

题目

风景迷人的小城Y 市,拥有n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点,随后依次前往 2、3 、4 ……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻,公交车只能往前开,或在景点处等待。

Read More

采访美术馆

题目

经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画。

Read More