2024-07-31 训练总结

经典的一场因为一题没调出来全部废掉的比赛。

United Cows of Farmer John

基础计数题，枚举左端点用线段树统计右端点的方案数即可。不过这题右端点有两个，不过本质上还是相同的。

因为第二题失误忘记对拍导致细节写错。

下次一定要在结束一道题前写好对拍而非最后一起写，不然会咕咕的。

Permutation

就是这题了，可以很容易想出 \(f_{i,j,k,p}\) 表示三角形三个端点为 \(i,j,k\) 同时使用了 \(p\) 个点的方案数，\(O(n^5)\) 就可以实现，非常基础的 dp 题目，但是因为没有调出来使得没有对第一题对拍痛失 100 pts。

应该牢记定时策略，一题必须在 0.5h 内有头绪，0.5h 内思考细节，1h 内实现，超时就放弃。

附判断点是否在三角形内。

中位数（middle）

和联考的一道题很像——萨雷格兹和她的蜘蛛。本质都是通过二分答案，把 \(\ge mid\) 的设为 \(1\)，把 \(<mid\) 的设为 \(0\)（这题是 \(-1\)，不过本质是一样的），想到就非常容易了。

观察两题的共同点，发现都有 \(a_i=0/1\) 的部分分，以后要对此类题目产生警惕。

破烂森林（garakuta）

非常好的类矩阵树定理题，本质证明过程是差不多的。

这里有一个证明，长度为奇数的置换环的逆序对数量为偶数，长度为偶数的置换环逆序对数量为奇数，根据归纳法证明：

1. 当置换环长度为 \(n=1\) 时，容易发现他的逆序对数量为 \(0\)，是偶数，满足条件；
2. 若置换环长度为 \(n=m-1\) 时满足条件，则证明置换环长度为 \(n=m\) 时也满足条件。原本的置换环可以分为三个部分 \([X]i[Y]\)，我们将新的点 \(m\) 加入环中的 \(i\) 前面，置换环可以表述为 \([X]m[Y]i\)。容易发现 \(m\) 大于 \([X]\) 中任意一个数，所有 \([X]\) 部分对答案没有贡献。对于 \([Y]\) 中的任意一个数 \(a\)，若原本有 \(i>a\)，那么原本的逆序对数量为 \(1\)，在新的置换环中容易发现逆序对数量依旧是 \(1\)。若原本有 \(i<a\)，那么原本的逆序对数量为 \(0\)，在新的置换环中容易发现逆序对数量是 \(2\)，但对奇偶性没有贡献。所以 \([Y]\) 部分对答案没有贡献。只有 \(i\) 移动到最后一个位置后，因为 \(i<m\)，所以会产生 \(1\) 的贡献。综上，置换环长度为 \(n=m\) 时的逆序对数量奇偶性与置换环长度为 \(n=m-1\) 时的不同。
3. 根据归纳法可知，原命题成立。

然后根据题解的走就好了。

容易发现这类矩阵树定理题都有一个相似条件——有重边和自环。做到时要注意。

综上

1. 结束一道题前写好对拍而非最后一起写
2. 牢记定时策略
3. 有 \(a_i=0/1\) 的部分分，可以联想到二分，把 \(\ge mid\) 的设为 \(1\)，把 \(<mid\) 的设为 \(0\)
4. 有重边和自环 \(\Rightarrow\) 矩阵树定理