Codeforces Round 953 (Div. 2)
闲来无事水题解。
A
。
B
。
C
显然 \(k\) 是偶数。考虑 \(k\) 的上界，\(p_{1}=n,p_{n}=1\)，产生 \(2n-2\) 的贡献，同时递归到子问题。
那么等价于有 \(1\sim n-1\) 的物品可以有贡献，可以直接贪心构造。
D
好像做复杂了。
\(i\) 能赢有两种情况：
- 没有得到新的票，那么票数大于自己或者排在前面且票数等于的都要被干掉。还要保证此时编号最小的 \((mex)\) 加上那些人的票不会超过自己。如果超过自己了，容易发现 \(i\) 能赢必须满足 \(i\) 要得到票。转化成下一个情况。
- 既然 \(i\) 是 \(mex\)，那么先把 \(1\sim i-1\) 干掉。如果此时还有比 \(i\) 大的，只需要删掉那个数后一定合法（因为他是最大的）。
维护前缀和做到 \(O(n)\)。
E
容易发现对于每个询问会改变的信息只有边界，暴力修改更新贡献再暴力还原。复杂度 \(O(n)\)。
F
注意到副对角线上的元素相同且 \(k\ge2\)，所以转化为一维的问题。预处理因数做到 \(O(n\ln n)\)。
标签：953,Codeforces,Round,Div,mex,sim From： https://www.cnblogs.com/OIshima/p/18286159