0%

Codeforces-162

哭瞎了。

OI 生涯最后一次 CF 做小号然后怒跌。

幸亏没用大号做……否则要会黄啊……

solution

A

双端队列就可以了。读到一个 l 就在右边插入 i ,否则就在左边插入 i

B

直接 dp 就可以了。转移的时候优化一下,记录 g[i] 表示 i 的倍数的最大的 f 值,每次 O(sqrt(n)) 利用 g 来求 f, 再用 f 来更新 g

C

观察数据范围发现 O(nq) 可过,但是 O(nq log n) 也许会超,考虑每次询问重新处理。令 f[i] 表示选取第 i 个球的最大收益,通过枚举最后一个球的颜色来转移。由于只有两种可能性:与上次颜色相同,与上次颜色不同。对于每种颜色维护最大值,线段树查询。

这样会 T 。其实只要维护最大的两个元素就可以了,不用线段树,复杂度降至 O(nq)

D

考虑枚举 S 中的每个位置,实时维护 T 中的所有可行位置。

维护两个量, L, R 表示 S 在当前位置时, T 最近、最远在哪里。那么所有可行的位置一定在 [L, R] 内。但并不是所有的位置都是可行的,考虑在当前位置前一位时 [L, R] 内的所有相邻元素,如果相邻两个是 [S[i], S[i - 1]] ,那么 i 这个位置是不能到达的,减去即可。可以证明,其余的位置都可以到达。

E

rng_58 的程序居然这么暴力。哭瞎。

f[i] 表示从 i 开始的 LIS 的长度。暴力维护 f

插入:由于高度小,只有高度比他小的元素, f 才会受到影响,暴力更新。

删除:由于序号小,只有序号比他小的元素, f 才会受到影响,暴力更新。

situation

首先做了 A ,还是很快的。

然后看了 B 后觉得记录约数是可行的,于是写了。(然后不小心写挂了 T_T)

然后脑残想去 cha 人?于是 Lock 了 B ,然后一个人都没 cha 到。

感觉不行啊,要跪的节奏啊,于是看 CDE 去。

C 瞬间 YY 出 O(nq log n) 的怕 T 不敢写。

一看 E 那不是原题么肿么没人做啊。于是写啊写写啊写好开心~过样例了好开心~交上去 WA 2 了好开心~再仔细一看看错题了好开心~T_T

完了彻底玩脱了。于是赶紧补 C ,YY 出一个 O(nq) 的。结果维护最大的两个值的时候维护错了,交了 4 次才过。

E 题无望,D 题或许还有点可能性。于是继续 YY ,YY 出一个算法了好开心~手跑过不了样例好开心~

继续 YY ,经过各种常数微调似乎可以过样例好开心~3 个样例交上去就 WA 4 好开心~

于是乎小号都会跌……T_T

这大概是除了那次 Bayan 外跌得最惨的一次了……

others

liouzhou_101 稳定发挥 rank 16 怒虐场。

wwwwodddd rank 53 也不错。

cherudim 终于可以不用熬夜了。

大叔只过了 B 。不过遇上了一件奇葩的事:有人用大叔的 ID 交程序 = =|| 。这是肿么做到的……

nonsense

今晚 8 点有 TC 。没小号给我撑着大号要怒跌了。