12.29
来到了 BSZX。
50+0+0=50
T1 一开始样例错了就先没看，于是几乎一整场都在想 T2，尝试了设第一排所有横边是否选为未知数来列方程，但一直不会优化，最后只写了个暴力。然后去想 T1，发现确定了每个点度数之后所有符合条件的图的最大匹配是一段区间，但我以为这个题不能做多项式复杂度，于是就写了个搜每边的度数集合的做法。T3 读了题但来不及写了。
T2 最后有个小细节导致暴力挂了。这次的发挥不是很好，对着最难的 T2 做了一整场，但是连第一步一个非常巧妙的转化都没想到，T1 会了结论之后没有想到去 dp，总的来说还是题做少了。
T1 题解：
考虑确定了每个点的度数之后，最大匹配有哪些可能。求出可能的最小值和最大值之后，每次交换更改一条边最大匹配变化量为 \(1\)，所以能贡献到的是一段区间。最大值比较显然，就是两边非零度数个数的 \(\min\)，最小值考虑将最大匹配转为最小点覆盖，即选最少的点使得度数之和 \(\ge m\)，按度数从大到小排序然后取一个前缀即可。但是排序这个过程难以维护，可以考虑错解不优，设 \(f_{i,j,k,l,p}\) 表示考虑了前 \(i\) 个点，度数之和为 \(j\)，非零度数有 \(k\) 个，最小点覆盖中选了 \(l\) 个点，度数之和为 \(p\) 的答案，转移是简单的，复杂度为 \(\mathcal{O}(n^3m^3)\)。
T2 题解：
先是一个非常巧妙的转化，设 \(f_{i,j}\) 表示完全包含 \((i,j)\) 的环数量的奇偶性，也即从 \((i,j)\) 向任意一个方向引出一条射线，穿过环数的奇偶性，那么一条边有没有选就是相邻两个格子 \(f\) 的异或。考虑每个内部格点必须选的限制，相当于度数必须为 \(2\)，也就是某个 \(2\times 2\) 的 \(f\) 中对角线不能都相同。于是设 \(a_{i,j} = f_{i,j}\oplus f_{i+1,j+1},b_{i,j} = f_{i+1,j}\oplus f_{i,j+1}\)，限制就是两个变量或为 \(1\)。而一个格子的颜色相当于钦定两个变量的异或值，然后还有一些边界问题，发现所有限制都是二元的，于是可以 2-SAT 去做了。
T3 题解：
相当于建出 \(m\) 层的图，对每个前缀的层跑最大流。考虑优化，最大流转最小割，于是只需要对每层记录 \(f_S\) 表示起点能到达哪些点，于是有 \(\mathcal{O}(4^nm)\) 的做法，显然可以轮廓线 dp 优化，可以做到 \(\mathcal{O}(2^nnm)\)，需要一些卡常。
12.30
100+60+52=212
T1 发现求出两边前 \(10^6\) 个不同的墙的位置即可，大概写到了 9:00。T2 首先想到了 \(\mathcal{O}(n^2)\) 的做法，然后尝试优化了很久还是不会，后面突然发现两个区间必有一个经过带权中点，然后就是简单 DS 维护了。T3 先会了个 \(\mathcal{O}(mn^2)\) 的 dp，然后发现能优化到 \(\mathcal{O}(nm)\)，然后就不会了。
最后 T2 因为一个小细节挂了，不写对拍导致的，以后像 DS 题如果有多的时间最好写个对拍。
T2 题解：观察到两个区间必有一个经过序列的带权中点，否则全部选择一个序列一定更优。不妨设经过了 \(a\) 序列的 \(a_{mid}\)，那么对于 \(b\) 序列的一个区间 \([l,r]\)，在 \(a\) 中选择的一定是从 \(mid\) 往左右拓展的极长段，于是可以把 \([l,r]\) 的贡献写成关于区间最小值和区间最大值的东西，扫描线+单调栈+线段树维护即可，复杂度为 \(\mathcal{O}(n\log n)\)。
T3 题解：对于同一个 \(m\)，一个 \(n\) 有三种情况：必败、只有第一步选择 \(x\) 才能胜利，第一步有多种选择能胜利，记为 \(f_n\) 之后可以 \(\mathcal{O}(n^2)\) 转移，容易优化到 \(\mathcal{O}(n)\)。如果 \(m\) 为偶数，只需判断是否有 \((m+1)\nmid n\) 即可。否则，观察到必败态很少，并且可以发现任意两个必败态之差一定是 \(m+1\) 或 \(m+2\)，如果一个必败态为 \(x\)，下一个必败态的位置取决于 \(x+\frac{m+1}{2}\) 是否为“有多种选择能赢”，然后可以一直递归下去。