比赛总结 Dwango Programming Contest V [清奇脑回路, 乱搞]
菜的真实
C - k-DMC
给\(Q\)个\(k\), 对于每个\(k_i\), 回答在程序初始给定的长度为\(N\)的字符串\(S\)中: 有多少个三元组\((a, b, c)\) 满足\(S[a] = D, S[b] = M, S[c] = C\)并且\(c - a < k_i\); \(N \le 10^6, Q \le 75\), 要求\(NQ\)做法
我(不确定这题\(NQ\)能不能过): Asia啊 这题复杂度多少啊 Asia: 这题(单次询问)复杂度线性的(注意句式为省略句) 我: ???? Asia: 这是基础操作啊 我: ?????????(吓傻跪烂.jpg)
迫真线性
过于真实
对于每一个询问\(k_i\), 遍历\(S\), 遇到一个\(M\)就入队加入贡献, 遇到\(C\)就把不合法的\(M\)出队, 去掉不合法贡献, 计算当前队列的合法贡献
贡献:
先做一个前缀和数组fr[i]代表前i个字符中\(D\)的个数, 当前队列能对\(M\)产生的贡献为[队列中所有\(M\)位置的fr - \(C\)的下标减去\(k_i\)所在的位置的fr \(\times\) 队列元素个数],
所以入队的时候加上当前位置的fr即可
注意不要在减k的时候下标越界
1 |
|
D - Square Rotation
我怎么…只会搜索啊…
1 |
E - Cyclic GCDs
我怎么…读不懂题啊…
1 |
By 准备退役旅游的Cansult