Codeforces Round #849 (Div. 4) 题解
第一次打 \(\text{Div.4}\)，感觉体验还行，差一题 AK。
A
直接使用 if 语句判断某个字符是否在字符串 \(\text{codeforces}\) 中出现过，幼儿园小朋友都会做。
时间复杂度 \(\mathcal{O}(T)\)，空间复杂度 \(\text{O}(1)\)。
AC Code
B
用两个变量 \(x,y\) 记录当前走到哪里。若出现过 \(x=1,y=1\) 的情况，输出 YES，否则输出 NO。
时间复杂度 \(\mathcal{O}(Tn)\)，空间复杂度 \(\mathcal{O}(1)\)。
AC Code
C
在 \(\text{while}\) 循环中判断头尾字符是否相等。若相等，则将头尾字符删去，并将答案加 \(1\)，否则退出循环。
时间复杂度 \(\mathcal{O}(Tn)\)，空间复杂度 \(\mathcal{O}(n)\)。
AC Code
D
设 \(f_i\) 表示 \(a_1 \sim a_i\) 中不同字符的个数，\(g_i\) 表示 \(a_i \sim a_n\) 中不同字符的个数.
答案即为 \(\max\limits_{1\le i \le n-1}{f_i+g_{i+1}}\)。
时间复杂度 \(\mathcal{O}(Tn)\)，空间复杂度 \(\mathcal{O}(n)\)。
AC Code
E
本题有几个关键的性质：
\(1.\) 每个数至多被选择 \(1\) 次。
\(2.\) 若对一段连续的区间 \([l,r]\) 进行操作，那么最终结果是 \(a_l=-a_l,a_{r+1}=-a_{r+1}\)，并且其他位置均不改变。
这样一来，对于序列中的任意两个数，我们都能使他们同时取反。
统计序列中负数的数量，设为 \(cnt\)。
若 \(cnt\) 为偶数，则直接将序列中所有负数取反。
若 \(cnt\) 为奇数，且序列中最小的非负整数绝对值小于序列中最大的负数的绝对值，则将序列中所有负数取反，并将最小的非负整数取反。
否则，将除最大负数的所有负数取反。
这样做能保证答案最优。
时间复杂度 \(\mathcal{O}(T n \log n)\)，空间复杂度 \(\mathcal{O}(n)\)。时间复杂度较劣的原因是因为我使用了排序。
AC Code
F
简单数据结构题。
考虑构造一个操作次数的差分数组 \(b\)。
对于每一个操作 \([l,r]\)，很显然将 \(b_l\) 加 \(1\)，\(b_{r+1}\) 减 \(1\)。
对于每一个询问 \(x\)，\(x\) 的操作次数即为 \(\sum\limits_{i=1}^n\) \(b_i\)。若 \(\sum\limits_{i=1}^n \le 5\)，则暴力修改，并记录 \(x\) 位置的答案。否则直接输出 \(x\) 位置保留的答案。
用一个树状数组维护 \(b\) 数组。
时间复杂度 \(\mathcal{O}(Tn \log n)\)，空间复杂度 \(\mathcal{O}(n)\)。
AC Code
G1
这题怎么比 F 还简单很多啊。
转化一下题意。假设有一个 容量为 \(c\) 的背包，并且有 \(n\) 个物品，第 \(i\) 个物品的体积为 \(a_i+i\)，价值为 \(1\)。
考虑做 0/1 背包，复杂度无法通过。注意到每个物品价值都为 \(1\)，所以贪心地选就可以了。
时间复杂度 \(\mathcal{O}(Tn \log n)\)，空间复杂度 \(\mathcal{O}(n)\)。
AC Code
G2
赛后想出来一个做法，但貌似是错的，就不写题解了。