比赛链接
https://codeforces.com/contest/1400
题解
(A.String Similarity)
有很多种构造方式。
最简单的一种是(s_ns_ns_n....s_n) 时间复杂度 : (O(N))
代码 : https://codeforces.com/contest/1400/submission/90913221
(B. RPG Protagonist)
注意到 (cnts leq 2 * 10 ^ 5) , 那么可以枚举一个人选了多少个 (swords)。
贪心即可。 时间复杂度 : (O(N))
代码 : https://codeforces.com/contest/1400/submission/90929076
(C. Binary String Reconstruction)
对于(s)中的每个(0) ， 可以知道 (w_{i-x} , w_{i+x}) 都为(0)
将其它的值都赋为(1) ， 最后判断是否符合要求。 即可。
还有一个做法是 (2-SAT) , 不过太麻烦了。
时间复杂度 : (O(N))
代码 : https://codeforces.com/contest/1400/submission/90935046
(D. Zigzags)
枚举(i , k) , 用乘法原理计算贡献。
具体实现时只要维护两个数组 , (in , out) 即可。
时间复杂度 : (O(N^2))
代码 : https://codeforces.ml/contest/1400/submission/90943961
(E. Clear the Multiset)
首先考虑没有(2)操作怎么做。
这是个经典问题。 对于所有的 (a_i > a_{i-1}) , 都对答案造成了 (a_i - a_{i-1}) 的贡献。
那么如果有(2)操作怎么做呢？
考虑动态规划。 设 (dp_{i,j}) 表示前 (i)个数 ， 第 (i) 个数是原数组中第 (j) 个数的代价和最小值。
直接转移即可。
时间复杂度 : (O(N ^ 2))
代码 : https://codeforces.ml/contest/1400/submission/90959792
(F.x-prime Substrings)
将所有 "(x-prime Substrings)" 插入 (AC) 自动机。这个复杂度是可以接受的。
然后就是一个朴素的动态规划了。
记 (dp_{i,j}) 表示第前 (i) 个字符 ， 当前在 (j) 号节点的最小值。
时间复杂度 : (O(NM)) ( (M) 为自动机节点数)
代码 : https://codeforces.ml/contest/1400/submission/91011980
(G.Mercenaries)
首先考虑没有 (M) 个限制怎么做。
枚举选了多少个 ，假设选了 (N) 个 ， 记 (Li leq N , Ri geq N)的有(K)个。 那么贡献即为 (N choose K)。
如果有 (M) 个限制怎么做呢？
考虑直接容斥原理。 用至少(0)个不满足 - 至少(1)个不满足 + 至少(2)个不满足 - .... + ...
预处理一些组合数的前缀和。 就可以做到 (O(2^M * M + NM)) 的复杂度。
代码 : https://codeforces.ml/contest/1400/submission/91009317