Div2 A
答案取决于 _ 连续段长度，有一些细节，比如什么时候答案要加一减一，以及字符串是单独的 ^。
Div2 B
首先先把全 \(1\) 串给特判掉。
记将字符串视为首位相接的环的时，最大 \(1\) 连续段长度为 \(x\)，答案为 \({\lfloor {x+1 \over 2} \rfloor}({\lfloor {x\over 2}\rfloor+1})\)。
Div2 C & Div1 A
对是否存在数 \(\mathrm{mex}+1\) 分类讨论
- 如果有，那么记录最左边的那个位置为 \(l\)，最右边位置为 \(r\)，操作即为 \(\mathrm{set}(l,r,\mathrm{mex})\)，同时判断 \([1,l)\cup(r,n]\) 的 \(\mathrm{mex}\) 是否是原来那个/
- 否则，直接将一个大于 \(\mathrm{mex}\) 或者重复出现的数改为 \(\mathrm{mex}\)。
Div2 D & Div1 B
首先注意到答案最多为 \(2\)。
考虑第一刀纵切和第一刀横切，若先纵切，那么 \(h\) 即为最大的 \(x_i\)，\(w\) 为 \(x_i=h\) 的 \(\sum y_i\) 加上剩余矩形中最大的 \(y_i\)。类似的，可以算出先横切的答案。
固定了矩形大小之后，判断合法性。考虑当前这刀切什么，必然是一个 \(x\) 或 \(y\) 等同于当前 \(h\) 和 \(w\) 的矩形，但是不能同时相等(除去最后只剩下一个矩形)。直接找到一个矩形，剩余的作为子问题递归完成。
Div2 E & Div1 C
观察到有解当前仅当是链上挂叶子，证明考虑从一个深度超过 \(1\) 子树跳到另一个深度超过 \(1\) 的子树，那么再跳就跳不出来了。
实现上求出树的直径，然后黑白染色，从左开始每次走白点到尽头再走黑点回来。
Div2 F & Div1 D
记 \(f_i\) 表示最小的 \(j\) 使得 \(j\) 到 \(i\) 的集合可以全部保留，考虑转移：
- \(k_i=0\)，此时 \(f_{i} \leftarrow f_{i-1}\)
- 考虑它前面最近的和他有交的集合 \(S_p\)，若不存在或者 \(p<f_{i-1}\)，那么 \(f_{i} \leftarrow f_{i-1}\)
- 否则要找到一个 \(q \ge p\)，使得 \(q\) 后集合清空，然后 \(f_{i} \leftarraw q+1\)
这启发我们找到那些位置之后可以被清空：
- \(k_i=0\) 或者 \(\exists f_{i-1} \le j \le i,k_j=0)\)，那么可以实现
- 否则依旧考虑它前面最近的和他有交的集合 \(S_p\)，若 \(p\) 存在并且 $p \ge f_{i-1}，那么可以实现，否者不能。
用 set 维护所有可以的位置，对 \(f\) 的转移等同于在其中 lower_bound
Div1 E
考虑这个询问操作能告诉我们什么：
如果当前图(只考虑能用的关键边，下同)联通，那么答案恒为 \(1\)，否则有概率为 \(0\)。
考虑我们取出一条边，将一个连通块分开，如果这是一个桥，那么分别查询 \(u\)，\(v\) \(k\) 次，就有可能查出 \(0\)。当 \(k=20\) 时，概率趋近于 \(100 \%\)。
接下来我们只要对每条边进行这个操作，我们先求出一个关键边的生成树，那么每次只要断掉生成树的一条边，接上考察的一条边，如果还联通说明它是关键边。
现在问题是如何求生成树。
也很简单，扫描每个边，把不是桥的边堵上就好了。