2022/04/03 做题记录

AT4362

考虑容斥，发现对于一个 $x$，每个数只有一个对应的数使它们的和为 $x$，于是对于任意一种不合法方案我们可以唯一的找出若干组不合法的对，但对对数容斥不是很方便（因为钦定对数之后还需要考虑这些对具体是什么），考虑本质不同的对只有 num=min(i, 2 * k + 2 - i) / 2 种，于是我们枚举这种方案中钦定有多少不同种的对。

$$\sum_{i=0}^{\text{num}} (-1)^i {\text{num} \choose i} f(n-i*2)$$

其中 f(x) 为投 x 个骰子得到的不同的结果数，可以用插板法，从小到大考虑，每一块代表这个数与上一个数的差，第一个数为 1，最后一块代表最后一个数与 k 的差，可以发现

$f(x) = {(k-2)+(x+1) \choose x}$

code: /code/2022.4.3/AT4362.cpp

P2046

首先，我们称四联通且海拔相等为一个联通块。

如果全局最大联通块大于 1,那么把它调整成 1 一定不劣。

如果全局最小联通块小于 0,那么把它调整成 0 一定不劣。

考虑全局次小联通块不为 1，

如果它不与 0 联通块相邻，把它调整成与它相邻的最小值一定不劣。

否则这一块与其它块的贡献在 [与它相邻且比它小的最大联通块的权值，与它相邻且比它大的最小联通块的权值] 上一定是一个线性函数，因为所有道路的大小关系都没有改变。

它一定在区间端点取最小值，调整过去即可。

于是问题转化成了将原图划分成一个包含左上角的 0 联通块和一个包含右下角的 1 联通块，联通块内边和从 1 联通块指向 0 联通块的边的权值为 0 ，从 0 联通块指向 1 联通块的边的权值为 1，如果我们把左上看为 S，右下看为 T，这实际上就是求原图最小割。

可以发现将每一个最小割的边顺时针旋转 90 度后都构成了一条从蓝色区域到红色区域的路径，于是我们可以将原来的方格看成点，方格边界看成边，建图跑最短路即可。

code: /code/2022.4.3/P2046.cpp

P2423

考虑 A 国最多选选两个人（因为要求两两奇偶性不同），于是可以枚举（注意也可以不选 A 国的人）并标记可以选的 B 国的人。

发现 B 国奇偶性不同的人一定是朋友，于是反图一定是个二分图。

而原图最大团等于反图最大独立集，并且二分图最大独立集等于总点数减最大匹配(https://blog.csdn.net/Techmonster/article/details/50011363)，直接匈牙利即可，复杂度看起来很高但可以过。

code: /code/2022.4.3/P2423.cpp

P3452

题意可以转换为求反图联通块数。

我们维护一个链表表示所有未被访问的点。

每次取出第一个点，标记它所有能到达的点，遍历链表将所有未被标记的点删除并加入队列，取消所有标记，然后每次从队列取出第一个数执行上述操作，直到队列为空。

发现每个点被遍历但没有没删除会“牺牲”一条边的贡献（因为每一点作为队首也只有一次），于是复杂度为 $\text{O(m)}$。

code: /code/2022.4.3/P3452.cpp