先报个人难度:红 红 橙 黄 绿
T1
逐个枚举,找到第一个比 h1h_1h1 大的就输出.
T2
模拟,吃掉一盘菜就把所需的对应元素逐个减少,如果最后都小于 000 就说明已经足够了.
T3
如果 AiA_iAi 为 111 那么 BiB_iBi 就为 222,否则 BiB_iBi 为 111,
如果和还有剩余就全加在 BBB 中一个为 222 的元素上.
注意判断特殊情况,n=1n=1n=1 时是得不出来的
T4
思路1
加一个偏移量使 di mod (A+B)d_i\text{ mod } (A+B)di mod (A+B) 的最大值最小,判断此时最大值是否小于 AAA.
但是这个偏移量不好找,取最大值、最小值都行不通,按 did_idi 一个一个试的话时间复杂度是 O(n2)O(n^2)O(n2) 的,会超时.
所以这个办法行不通
思路2
欢乐赛#34T3 给了我一点启发
我们注意到,把所有 did_idi 取模后排序,则 d1,d2,d3,d4...dn,d1d_1,d_2,d_3,d_4...d_n,d_1d1 ,d2 ,d3 ,d4 ...dn ,d1 构成了一个环,如图所示.
而这个环的长度为 A+BA+BA+B.
事实上题目就是让我求这个环砍掉一条边后形成的链的最短长度.
所以我们只需要判断是否满足 A+B−max{di}<AA+B-\max\{d_i\}<AA+B−max{di }<A 即可.
T5
这题应该改名为后缀和问题(
注意到 n≤3×105n\le 3\times10^5n≤3×105,明显就是给暴力分块做的
对于这类问题,一次查询运算次数只需要不超过 10310^3103 次就行,这里我取 ⌊n⌋\lfloor\sqrt n\rfloor⌊n ⌋ 的近似值 600600600.
当 b>600b\gt 600b>600 时,运算次数必定小于 600600600,直接暴力枚举.
所以我们只需要思考 b≤600b\le 600b≤600 的情况就行.
340PTS
按内存极限预处理 b≤24b\le 24b≤24 的情况,剩下的暴力.
dp[i][j]dp[i][j]dp[i][j] 为当 a=j,b=ia=j,b=ia=j,b=i 时的答案.
500PTS
仔细思考,如果我们隔一个预处理一个,如
变成
2,4,6查询时再计算,那这样运算次数只多了一次,但是内存却省了一半!
按照这个办法,把 dp[i]dp[i]dp[i] 的步长改为 i×600i\times600i×600,运行次数仍然不超过 600600600.