较简单的场。submissions.
很久以后复健 abc 第一场。G 题开太慢没 \(2400\) 差评。
A
直接加。
B
如果 \(s=\texttt{rev}(s)\)，则是 Yes，否则是 No。
C
There is exactly one way to arrange the \(N\) people consistent with the information given.
所以给出的是一条链。直接记录后继即可。
D
码量最大的一题。（我写的）
可以记录一个地方最多往右、下最多走几步，再对每个点开始枚举。
当然可以不记录最多往右、下最多走几步，遇到 x 就 break，见最短代码。
E
小思维。
知道坏肚子的人的集合等同于知道是哪瓶，也就是说每一瓶给到的人的集合互不相同。所以最少要 \(\log (N)\) 个人品尝。
构造很简单。
F
本场最难的。我开始以为程序难写就跳过了。
显然要预处理每个颜色有多少球，把 \(c\) 复制一遍接到结尾。
从左往右移球，记录一个指针指到最后一个占了一个盒子的求。当我们发现有空盒子的时候，指针往后挪，加入新盒子的时候（颜色放不下多开一个或者出现新的颜色），就放进去。删除球，可以直接减。
代码很简单。所有里面第四短。
G
dp 题。所有里面第 \(11\) 短。是不是换根 dp（）。
预处理出以 \(1\) 为根，每个节点儿子里面的答案，设为 \(cnt_u\)。\(cnt_u=\sum_{v\in G_u}cnt_v+\texttt{# of nodes less than }u\texttt{ in the sons}\)。后面这个可以用 bit 处理。
设 \(dp_u\) 为最终答案。那么，\(dp_{v}=cnt_v+dp_u-cnt_v-\texttt{# of sons in }v \texttt{ including }v\texttt{ that is less than }u\)。后面这个也就是前面可以一起处理的。
对着图很好理解。
标签：cnt,ABC,记录,less,337,texttt,dp From： https://www.cnblogs.com/SFlyer/p/17977728