第一次打 $\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
赛后想出来一个做法，但貌似是错的，就不写题解了。