[AGC066A] Adjacent Difference
给定 \(n \times n\) 的矩阵 \(A\) 和常数 \(d\)。你需要构造 \(n \times n\) 的矩阵 \(B\) 使得：
-
\(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} |a_{i,j} - b_{i,j}| \leq \dfrac{dn^2}{2}\)
-
\(B\) 中相邻两个数之差的绝对值 \(\geq d\)
\(2 \leq n \leq 500\)，\(1 \leq d \leq 1000\)，\(|A_{i,j}| \leq 1000\)。
啊？
我们发现这种限制和黑白染色很类似，于是你考虑下面两种构造：
-
黑格全部 \(\geq d\)，白格全部 \(\leq 0\)
-
黑格全部 \(\leq 0\)，白格全部 \(\geq d\)
但你发现这个构造其实不牛，如果黑格和白格都更接近 \(d\) 这不就炸了吗。
尤其是，这种构造在值域范围较大的时候比较不牛。
考虑本质上你只要构造差 \(\geq d\) 即可，所以：
-
黑格全部 \(\equiv d \pmod {2d}\)，白格全部 \(\equiv 0 \pmod {2d}\)
-
黑格全部 \(\equiv 0 \pmod {2d}\)，白格全部 \(\equiv d \pmod {2d}\)
然而这个东西和上面的构造有着一样的问题，考虑一些更牛的构造！
- 黑格全部 \(\equiv x \pmod {2d}\)，白格全部 \(\equiv x + d \pmod {2d}\)
此时枚举 \(x\)，这就是对的了。
因为你考虑这样一件事，所有情况下，所有格子的代价平均值都是 \(\dfrac{d}{2}\) 的。
也就是说所有情况的代价平均值是 \(\dfrac{dn^2}{2}\)，则必然存在一种情况的代价 \(\leq \dfrac{dn^2}{2}\)。
[集训队互测] 子集匹配
令 \([n] = \{0,1,\dots,n-1\}\)。
令 \(A\) 为 \([n]\) 所有大小为 \(k\) 的子集构成的集合。
令 \(B\) 为 \([n]\) 所有大小为 \(k-1\) 的子集构成的集合。
对于 \(S \in A\) 且 \(T \in B\)，若 \(T \subseteq S\)，则 \(S\) 到 \(T\) 有边。
求一组 \(A\) 到 \(B\)，大小为 \(|B|\) 的匹配。
\(1 \leq n \leq 27\)，\(2k \geq n\)。
考虑将 \(S\) 中 \(0\) 看成 \(1\)，\(1\) 看成 \(-1\)。
此时找到 \(S\) 的前缀和的最大值，其后面一个位置必然为 \(1\)，将其变为 \(0\)。