A

• 首先，插入的字符必须和左右两边的字符都不一样
• 其次，对于插入位置的选择，显然最好插在两个一样的字符中间，如果没有一样的字符，插在最前面即可

B

• 观察样例发现题目中要求的位置就在样例中
• 手玩一下，尝试改变样例里那个形状，发现改变任何一个格子都不满足题意，所以得出结论：题目要求的位置当且仅当六个格子形如

...
*.*

• 直接枚举每个位置即可

C

• 首先，左括号为1，右括号为 -1，合法括号串显然满足前缀和非负
• 在奇数位置上，前缀和总是二的倍数
• 如果要尽量缩小匹配括号之间的距离，显然能早放右括号就早放右括号
• 如果某个奇数位置的前缀和是 0，显然只能放左括号
• 否则，一定会放右括号，这样做一定没有后效性：因为如果放的话，前缀和最少是 2，一定可以支持连续放两个右括号，然后就到下一个奇数位置了

D

• 注意到 \(u\) 可以取到的最大值与子树内的最小值有关，考虑树形 DP
• 设 \(f_u\) 表示 以 \(u\) 为根的子树内最小值的最大值
• 容易列出转移：\(f_u=min(min_{v\in u}(f_v),\frac {min_{v\in u}(f_v)-a[u]}{2}+a[u])\)
• 对于叶子：\(f_u=a_u\)
• 对于根：\(f_u=a_u+min_{v\in u}(f_v)\)

E

• 容易发现：对于一个怪物，k 越大，越容易蘸豆，k 越小，越不容易蘸豆
• 观察询问的形式，大胆猜想回复询问是 \(O(1)\) 的；而我们对于每个怪物 \(i\)，要计算出：k 至少为多少才能与这个怪物蘸豆
• 考虑二分：设当前二分的值为 \(k\)，则不与当前怪物蘸豆的充要条件是：\(k\times a_i<=在第 i 个怪物之前蘸豆的总次数\)
• 注意到 \(在第i个怪物之前的蘸豆总次数\) 难以快速求出，但注意到，我们在计算到 \(i\) 时，已经算出了与前 \(i-1\) 个怪蘸豆所需的最小 \(k\)，于是我们可以使用树状数组快速求出 \(在第i个怪物之前的蘸豆总次数\)
• 时间复杂度 \(O(n\log^2{n})\)