Codeforces Round
直角，口胡一下刚刚过去的一场 CF 的题。
其实本来想打的然而没仔细看时间以为还是 22：35 开始结果一看 18：05 就开始了于是没赶上。
A. Luntik and Concerts
给出 $a$ 个 $1$，$b$ 个 $2$ 和 $c$ 个 $3$。把这些数字分配到两个集合 $S_1,S_2$ 里，并最小化 $\left|\sum_{x\in S_1}x-\sum_{x\in S_2}x\right|$。
多组数据。$1\leqslant a,b,c\leqslant 10^9$。
$\texttt{1s/512MB}$。
观察样例之后大胆猜想最小值一定是 $0$ 或 $1$。
于是 $a+2b+3c$ 为奇数时答案为 $1$，为偶数时答案为 $0$。
虽然只是个猜想不过看上去很靠谱而且如果是在考场上的话已经可以开始写了。
至于证明，肯定分类讨论几波就出来了就不整了（光速逃
B. Luntik and Subsequences
给定一个长度为 $n$ 的序列 $a$。令 $S=\sum_{i=1}^{n}a_i$，求 $a$ 有多少个子序列的和等于 $S-1$。
多组数据。$1\leqslant n\leqslant 60$，$0\leqslant a_i\leqslant 10^9$。
$\texttt{1s/512MB}$。
注意到一个满足条件的子序列一定是 $a$ 删掉恰好一个 $1$ 和若干个 $0$ 得到的。
设 $a$ 中有 $c_0$ 个 $0$，$c_1$ 个 $1$，则答案为 $c_1\cdot 2^{c_0}$。
所以说为啥数据范围这么小。
C. Grandma Capa Knits a Scarf
给定一个长度为 $n$ 的字符串。从中删去若干个同种字符（可以一个不删或全部删去）使得原字符串变成回文串。无解输出 $-1$；否则输出至少需要删去多少个字符。
多组数据。$1\leqslant n\leqslant 10^5$，字符集小写字母。$\sum n\leqslant 2\times 10^5$。
$\texttt{1s/512MB}$。
首先，如果给定字符串最左侧和最右侧的字符相同，我们可以将它们删去，即不考虑它们。重复这个动作直到字符串最左侧和最右侧的字符变得不同（或者字符串变为空串，那么答案就是 $0$）。
假设我们选择删去最左侧的字符，将其记为 $c$。重复上述动作，如果最左侧和最右侧的字符相同，就将它们删去；如果不同，这两个字符中有 $c$ 就将其删去然后计数器 $+1$，没有 $c$ 就无解。直到字符串变为空串或者得出无解结论。
不过说实话看上去有点假。
D. Vupsen, Pupsen and 0
给定一个长度为 $n$ 的序列 $a$，$a_i\neq 0$。试构造一个同样长度为 $n$ 的序列 $b$，$b_i\neq 0$ 且 $\sum_{i=1}^{n}|b_i|\leqslant 10^9$，使得 $\sum_{i=1}^{n}a_ib_i=0$。
多组数据。$2\leqslant n\leqslant 10^5$，$0\lt|a_i|\leqslant 10^4$。$\sum n\leqslant 2\times 10^5$。
$\texttt{1s/512MB}$。
注意到对于任意实数 $x,y$，有 $y\cdot x + (-x)\cdot y = 0$。于是对于 $a_{2k-1},a_{2k}$，我们构造 $b_{2k-1}=a_{2k},b_{2k}=-a_{2k-1}$。
但是这样 $a_n$ 可能会单出来，于是我们就将其和 $a_1$ 再配对一次即可。
注意到此时 $\sum_{i=1}^{n}|b_i|\leqslant\sum_{i=1}^{n}|a_i|+|a_1|$……好像超了。
好家伙管他的直接 xjb 一通乱凑得了。
E. Pchelyonok and Segments
给定一个长度为 $n$ 的序列 $a$。构造 $k$ 个区间 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$ 满足：
- $r_i-l_i+1=k-i+1$。
- 若 $i\lt j$ 则 $r_i\lt l_j$。
- 若 $i\lt j$ 则 $\sum_{x=l_i}^{r_i}a_x\lt\sum_{x=l_j}^{r_j}a_x$。
只需输出 $k$ 的最大值。
多组数据。$1\leqslant n\leqslant 10^5$，$1\leqslant a_i\leqslant 10^9$。$\sum n\leqslant 10^5$。
$\texttt{2s/512MB}$。
令 f[i][j] 表示在原序列的第 $i$ 个后缀构造 $j$ 个区间时最左侧的区间上 $a_i$ 的和的最大值。
显然靠右的区间上 $a_i$ 的和越大，靠左的区间就会有越多的选择。
注意到 $j$ 一定和 $\sqrt{n-i+1}$ 同级，这使得我们可以 $O(n\sqrt{n})$ 暴力搞。
转移的时候就对于每个 $j$ 维护一下所有 f[i][j] 的最大值就好。
F and G
不会（理直气壮
自己去看 CF 的题解吧（光速逃