智慧构造

P10644

Public NOIP Round #8 D. 矩阵

令 $f_i=\sum_{j=1}^m a_{i,j}$，$g_j=\sum_{i=1}^n a_{i,j}$。当 $c'_{i,j}=f_i-g_j$ 时认为 $c'_{i,j}$ 的符号是正确的。记 $p1$ 为一个不全相同的行，$p2$ 为一个不全相同的列。如果能构造出合法的 $\sum f_i=\sum g_j$，可以同 arc135d 的方法，取出同符号的 $f_i,g_j$ 消掉绝对值较小的，再取出符号相反的 $f_i,f_j$ 或 $g_i,g_j$ 消掉绝对值较小的。

如果存在 $p1,p2$。找到一个 $c_{p1,p2}\neq c_{p1,p3}$，枚举 $c'_{p1,p2}$ 和 $c'_{p1,p3}$ 的符号，令 $f_{p1}=0,g_{p2}=c'_{p1,p2},g_{p3}=c'_{p1,p3}$，带进去解 $f_i,g_j$ ，有唯一解。然后调整，令 $f_{p1}$ 初始为 $\frac{\sum f_i-\sum g_j}{n-m}$ 使 $\sum f_i=\sum g_j$。

如果不存在 $p1$ 和 $p2$，即所有 $c_{i,j}$ 相等。如果 $n$ 为偶数，构造 $g_j=0$，前 $\frac{n}{2}$ 个 $f_i$ 为 $c_{1,1}$，其他为 $-c_{1,1}$。否则 $n$ 为奇数，令 $g_j$ 全为 $x$，有 $n1$ 个 $f_i$ 为 $x+c_{1,1}$，$n2=n-n1$ 个为 $x-c_{1,1}$，有 $c_{1,1}=\frac{(m-n)x}{n1-n2}$。$n1\neq n2$，枚举 $n1$ 求 $x$。$m$ 为奇偶也同理。

否则不妨设 $p1$ 有值。因为每列的 $c_{i,j}$ 都相等，构造第一行复制 $n$ 次。所以有 $n\times f_1=\sum f_i=\sum g_j$，$g_j=f_1-c'_{i,j}$，$\sum g_j=m\times f_1-\sum c'_{1,j}$。所以 $(n-m)\times f_1=-\sum c'_{1,j}$。设 $dp_{i,s}$ 表示前 $i$ 个 $c'_{i,j}$ 的和为 $s$ 是否可行。bitset $O(\frac{n^3}{w})$ 加速。

arc189e

$n\le 3$ 无解。$n=4$ 时 $(1,2),(3,4)$ 权值为 $1$，$(1,4),(2,3)$ 权值为 $2$，$(1,3),(2,4)$ 权值为 $3$。$n=5$ 时如样例。

证明 $mx=2$ 不合法。归纳，对于 $n-1$ 的 $p_1,\dotsb,p_{n-1}$ 使得 $mx=2$ 不合法，如果全同色，$n$ 可以加在最前或最后；否则找到分界点 $p_x$，$p_x$ 以前为 $1$，以后为 $2$，如果 $(p_x,n)$ 为 $1$，$p_1,\dotsb,p_x,n,p_{x+1},\dotsb,p_{n-1}$ 不合法，否则 $p_1,\dotsb,p_{x-1},n,p_x,\dotsb,p_{n-1}$ 不合法。

对于 $n>5$ 时 $mx=3$ 合法。将 $n$ 分为 $4$ 个集合 $X1,X2,X3,X4$，对应 $n=4$ 时的 $1,2,3,4$。集合内权值为 $3$，集合间权值为 $n=4$ 的权值。可能不合法的方案会要求连续在 $X1$ 和 $X2$ 间切换，再连续在 $X1$ 和 $X4$ 间切换，即 $|X1|\ge |X2|+|X4|$。其他一些可能不合法的情况也要求其中一个集合至少为另外两个集合之和。令 $|X1|\ge |X2|\ge |X3|\ge |X4|\ge |X1|-1$。但当 $n=5$ 时会寄，特判即可。

CF1097E

记 $c_n$ 为最大的 $k$ 使得 $\frac{k(k+1)}{2}\le n$。可以构造 $((1),(3,2),(6,5,4),\dotsb)$ 使得 $f_n\ge c_n$。

在 $c_n$ 内划分任意一个排列。设最长上升子序列长为 $len$。如果 $len>k$，取出，$\frac{(k-1)k}{2}\le n-len$。否则由 Dilworth，存在 $len$ 个下降子序列可以拼出原序列，贪心构造。

P9731

对于 $m=2$，一定有解。连边 $(u,v)$，把奇数度的点连向一个虚点，跑欧拉回路。可以保证原来奇数度的点入度出度差为 $1$。

对于更大的 $m$，当作 $n\times \frac{m}{2}$ 对 $2$ 个的处理，使得左右两边差值 $\le 1$。分治左右两边。

P11066

分为要向左的点和要向右的点。从后往前做，要向左的点先向右一步，要向右的点直接去要去的位置。再从前往后，要向左的点去要去的位置。问题是，对于只要向右走一步的点，会在这时挡到路。

先做一步调整。调整会把空位从最右移到最左，所以上面部分反过来。每次从后往前考虑 $i$ 和 $i+1$，如果 $m$ 为奇数就不考虑最后一个点。如果 $i$ 和 $i+1$ 在右移一格后需要调整，就交换 i+2,i+2,0,i+1，否则直接 i+2,i+1，把空位向左移。

理论上 $5n$，常数较小。