1110总结
1110总结
T1
莫名奇妙写挂的题。
题本身意义不大，但是我写了很蠢的做法。
分析问题本质上是需要动态查 \(i\ge l,a_i\in x_i\)，\(a_i\) 不是很大，可以直接预处理每一个元素的 \(next\)，就很方便了，但是考场上写了扫描做法，还写挂了，非常蠢。
拿到题不要直接开冲，可以多想一下有没有更好写的做法/更方便，前面的题没那么难。
T2
观察发现答案不超过 \(1\) 的充要条件是存在一条长度为奇数的路径，答案不超过 \(2\) 的充要条件是存在一条路径。
先假定图联通，所以问题变成了计算无向图 \(s,t\) 之间是否存在长度为奇数的路径，有以下三种方式
直接最短路
思想是分层图跑最短路，但实现上没那么麻烦，考场写的这个做法。
DFS
如果有奇环，那在奇环上绕一圈任意可达了，所以考虑先 DFS 求个深度，如果有奇环答案全部为 \(1\)，否则路径唯一求出来就行
二分图
还是奇环的思想，实现上使用黑白染色。
并查集
这是常数最小的写法，还是考虑分层图，有一条边则合并不同层的两个点，查奇数路径就是不同层是否联通，偶数路径就是相同层是否联通。
T3
不算太难的题，但是确实没有想出来。
首先有个经典结论，先手必败的充要条件为所有可选元素为偶数，证明归纳，显然。
算先手必败显然比先手必胜好算，所以算必败。
先把元素做前缀和，再对 \(2\) 取模。问题就是需要选一个子矩阵，满足首尾两列元素值相同。
考场上想到了可以哈希，由于常数，虽然是 \(n^2m\) 的，但只有 \(52pts\)。
非哈希做法
考虑固定下边界，移动上边界的过程，发现相同元素的集合在不断变小，而有了这个集合就可以算答案，这个东西是可以每次 \(O(m)\) 计算的，这样的常数较小，可以得到 \(76pts\)。
正解1
先得想到它已经是个字符串题了，考虑上边界不断变化的过程，发现不合法的矩阵个数等于当前 \(m\) 个字符串两两之间 \(LCP\) 的和，然后考虑字符串排序的方式求 LCP，类似后缀排序的 \(height\) 数组，发现后缀排序是很好做的，因为每次上移一行，就是归并排序的过程，\(height\) 和 \(rk\) 都可以线性维护，得到了 \(height\) 之后就单调栈搞定。
Another Approach
考虑非哈希做法的等价类思想，发现虽然维护过程是 \(O(nm)\) 的，但实际上等价类的个数是 \(O(m)\) 的，考虑以移动下边界的方式考察当前下边界所有上边界的等价类，自顶向下的更新等价类，该拆分的拆分，实际上和正解1本质相同。
T4
条件比较特殊，需要先观察。
记 \(T'\) 为 \(T\) 的修剪。
\(T\) 的修剪和 \(T\) 的右子树相同，那么考虑 \(T\) 的右子树 \(R(T)\)，那么 \(L(R(T))=L(T')\)，递归的，\(R(R(T))\) 和 \(R(T)\) 的修剪相同。
归纳边界是 \(L(T)=\emptyset\)，此时右子树可以任意延申右儿子而不受限制，先假设当左儿子为空时右儿子也必须为空，这样就有了一个边界。
因此，如果 \(L(T)\) 确定了，就可以确定出有边界的树的唯一形态。
考察 \(L(T)\) 的各项数据对应到的 \(T\) 的数据。
容易发现： \[ leaf_T=size_{L(T)} + 1\\ height_T=height_{L(T)}+1\\ size_T=height_T+\sum\limits_{u\in L(T)} height_u \] 接下来的事情变成了设计一种合理的方式去枚举合法的 \(L(T)\)，并能够计算这些数据。
子树合并枚举二叉树
枚举二叉树，比较合理的一种方式是以子树大小为阶段来合并，需要记录的信息是 \(dp[i][j][k]\) 表示子树大小为 \(i\)，高度为 \(j\)，\(\sum height_u\) 为 \(k\) 的总方案数，合并的时候需要枚举三维做卷积，复杂度为 \(n^2k^2m^2\)，难以通过本题。
不难发现 \(j\) 可以用前缀和优化，但是其它两维是卷积，动不了的，复杂度 \(O(n^2km^2)\)，实际上常数比较小，可以过掉。
深度顺序枚举二叉树
刚刚的方式是子树合并的方式构造二叉树，现在考虑用深度顺序构造，设 \(dp[i][j][k][s]\) 为构造深度为 \(i\)，树大小为 \(j\)，\(\sum height\) 为 \(k\)，可用点数为 \(s\) 的方案数，转移需要枚举向下构造的点数 \(t\)，得到 \(t\) 后可以预处理转移系数，顺便计算出新的 \(j,k,s\)，复杂度为 \(O(kmn^3)\)，更加优秀，事实上 \(j,s,t\) 远远取不到 \(n\)，是非常优秀的复杂度。
但是这个方法是假的，因为深度和 \(\sum height\) 没有必然联系，所以无法计算 \(k\)。
高度顺序枚举二叉树
考虑以子树高度的顺序，降序构造二叉树，这和深度顺序又不一样。
考虑设 \(dp[i][j][k][s]\) 表示子树高度为 \(i\)，大小为 \(j\)，\(\sum height\) 为 \(k\) ，叶子个数为 \(s\) 时的方案数，注意这里是按照高度顺序构造，即强制要求先选的部分的高度大于后选的。所以又额外的要求是枚举接下来的增量时需要将所有叶子至少叠加一层，枚举增量 \(t\) 时预处理系数即可，复杂度和深度顺序类似。