AT 经典90题（031-060）

31.VS AtCoder

考虑 sg 函数，每次异或上 \((w_i,b_i)\) 的 sg 函数看最后是不是 \(0\) 即可。注意 \(b\) 那一位的上界为 \(1500\) 而不是 \(50\)。

32.AtCoder Ekiden

考虑全排列枚举跑步顺序并判断不合法即可。

33.Not Too Bright

先特判 \(n\) 或 \(m\) 为 \(1\) 的情况。对于其他情况答案就是 \(\lceil\frac{n}{2}\rceil\times\lceil\frac{m}{2}\rceil\)。

34.There are few types of elements

考虑使用双指针，如果 \(r\) 能右移就右移。最后把所有这样的区间长度取最大值即可。

35.Preserve Connectivity

经典结论，先把给出的点按照 dfn 排序。求的东西就是 \(\displaystyle\sum_{i=1}^{k}(dep_{v_i})-\sum_{i=2}^{k}(dep_{lca(v_{i-1},v_i)})-dep_{lca(v_1,v_k)}\)。