7.24
\(100+100+100+0=300\)。
整体：前三题发挥稳定，最后一题确实超出了我的知识范围，但是较为简单的 30 pts 没有细想，比较可惜。
T1：
两个 0-1 串，每次选中两个串上的两个等长（位置不一定相等）区间，询问两个区间不相等的位置数量，对 \(2\) 取模。
Solution：考虑对 2 取模经典问题模型，这类问题有一些有趣的解决方案：
第一个是考虑异或操作，因为异或就是模 \(2\) 意义下的加法，而且有较多性质。
第二个是考虑消掉一些重复（或者可以一一对应）的项来达到正确的复杂度，具体说根据实际情况考虑分治，meet-in-the-middle 等算法。
回到本题中，本题较简单，因为发现两数不同就意味着异或为 \(1\)，有奇数个也意味着不同数量的异或为 \(1\)，考虑异或的结合律，则答案就是把选中部分全部异或。
维护前缀和即可。
T2：
在 \((n+1)\times (m+1)\) 的点阵图中选中 \(k\) 个点，满足：
-
它们在一条直线上；
-
相邻两点距离不小于 \(d\)。
求满足条件的方案数。
多测，\(n,m,d\le 500,k\le 50,T\le 20\)。
Solution：枚举数数题。
考虑枚举左下端点和右上端点，则此时方案数较为好计算，考虑使用插板法，并预处理组合数，复杂度 \(n^2m^2T\) 真美丽。
但是发现其实枚举端点是没啥意义的，因为答案只和 \(\Delta x,\Delta y\) 有关。
考虑枚举 \(\Delta x,\Delta y\) 并计算每一个的贡献次数，复杂度回到 \(nmT\)。
T3：
给定一棵以 \(1\) 为根的有根树，你可以任选起点，每次向某个祖先或者子树内某个点跳，但是不能重复经过已经去过的点，问最多能走过多少个点。
Solution：
考虑二叉树，发现中序遍历挺对的，难道一定有解全覆盖？
并不是。菊花图就不是。
但是我们发现答案形如：解决一个子树，回到一个祖先，解决另一个子树并把没解决的部分挂上去。
选那两个子树呢？肯定是最大的两个，故每次操作形如吸收所有子树的答案并取最大的两个合并再加 \(1\)。
于是使用 set 启发式合并以获得 \(O(n\log ^2 n)\) 的复杂度。