智慧构造

P10644

Public NOIP Round #8 D. 矩阵

sol。

令 $f_i={\sum }_{j=1}^m{a}_{i,j}$，$g_j={\sum }_{i=1}^n{a}_{i,j}$。如果能构造出合法的 $\sum f_i=\sum g_j$，就 arc135d 的方法。

分类讨论是否存在一个不全相同的行、一个不全相同的列。

arc189e

sol。

特判 $n\le 5$。

归纳证明 $mx=2$ 不合法。对于 $n>5$ 时 $mx=3$ 合法。将 $n$ 分为 $4$ 个集合 $X1,X2,X3,X4$。集合内权值为 $3$，集合间权值为 $n=4$ 的权值。可能不合法的方案要求其中一个集合至少大于等于为另外两个集合之和。令 $|X1|\ge |X2|\ge |X3|\ge |X4|\ge |X1|-1$。

CF1097E

记 $c_n$ 为最大的 $k$ 使得 $\frac{k(k+1)}{2}\le n$。可以构造 $((1),(3,2),(6,5,4),\cdots )$ 使得 $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$，常数较小。

CF538G

将坐标轴转 45 度，两维独立。将坐标替换为 $\frac{x+t}{2}$，每次加一或不动。

设一个循环节加 $k$。对于 $\mathrm{mod}l$ 相邻的位置，$x_i-x_j-(t_i\mathrm{mod}l-t_j\mathrm{mod}l)\le k(\frac{t_i}{l}-\frac{t_j}{l})\le x_i-x_j$，解不等式。

P7320

生成树。要么叶子，要么叶子两两匹配形成路径。dfn 序上有交的叶子对连成的路径有交。

agc037d

正反出发各做一次重排行，相当于把 $[(k-1)\times m+1,k\times m]$ 看做一种颜色的通配符。希望重拍列之后每行变成相同的。

左部点 $n$ 行，右部点 $n$ 种颜色，连边为原来这一行有几种这个颜色，每个点 $m$ 条入（出）边。求 $m$ 组完美匹配，第 $t$ 组若 $(i,j)$ 则 $b_{i,t}$ 颜色为 $j$。

是 $m$ - 正则二分图，由霍尔定理一定存在完美匹配，删掉一组完美匹配后是 $m-1$ - 正则二分图。所以一定存在 $m$ 组完美匹配。

可以由 loj180 做到 $O(nm\log n)$。

CF2138E2

可以用 $2k$ 造出 $2^k$。$det=16$ ：

  1  1  0  0  0  0  0  0
 -1  1  1  0  0  0  0  0
  0  0  1  1  0  0  0  0
  0  0 -1  1  1  0  0  0
  0  0  0  0  1  1  0  0
  0  0  0  0 -1  1  1  0
  0  0  0  0  0  0  1  1
  0  0  0  0  0  0 -1  1

可以在此基础上 $+2^i$。$det=18$：

  1  1  0  0  0  0  0  0
 -1  1  1  0  0  0  0  0
  0  0  1  1  0  0  0  0
  0  0 -1  1  1  0  0  0
  0 -1  0  0  1  1  0  0
  0  0  0  0 -1  1  1  0
  0  0  0  0  0  0  1  1
  0  0  0  0  0  0 -1  1
 

想选右下角的 $-1$，左上的 $8\times 8$ 选法唯一，有 $-1$ 的逆序对，右下任意。

多个 $2^i$ 可以叠加。$det=21$：

  1  1  0  0  0  0  0  0
 -1  1  1  0  0  0  0  0
  0  0  1  1  0  0  0  0
  0  0 -1  1  1  0  0  0
  0  0  0 -1  1  1  0  0
  0  0  0  0 -1  1  1  0
  0 -1  0  0  0  0  1  1
  0  0  0  0  0  0 -1  1

要求选法固定的矩形必须相互包含。

一行最多选 $2$ 个，不能同时操作 $i$ 和 $i+1$。但是 $2^i+2^{i+1}=2^{i+2}-2^i$，一定存在合法操作。构造时从低位开始考虑每个 $1$ 连续段。

agc064e

记 $s_i={\sum }_k{a}_{i,k}$，$t_i={\sum }_k{a}_{k,i}$。则 $c_{i,j}=s_i+t_j-a_{i,j}$，只要 $c_{i,j}$ 满足一定性质，就能反推一个 $a_{i,j}$。

对 $a_{i,j}$ 一行求和，$s_i={\sum }_j{a}_{i,j}=n\times s_i+{\sum }_k{t}_k-{\sum }_j{c}_{i,j}$。又因为 $\sum c_{j,k}$ 把整个 $a_{i,j}$ 算了 $2n-1$ 遍，所以 $(n-1)s_i={\sum }_j{c}_{i,j}-\frac{\sum c_{j,k}}{2n-1}$。

只要满足整除，使得存在 $s_i$ 即可。就是：$\sum c_{j,k}\mathrm{mod}2n-1\equiv 0$，所有 ${\sum }_k{c}_{i,k}$ 和 ${\sum }_{k}l{c}_{k,i}$ 模 $n-1$ 同余。

现在是，存在一种构造 $c_{i,j}$ 的方式，满足模 $n-1$ 同余的性质，且可重集就是 $\{a_i+b_j\}$。然后如果再不满足模 $2n-1$ 的性质，就调整一个数即可。

也就是，希望构造 $c_{p_{i,j},q_{i,j}}=a_i+b_j$，使得每行每列之和都是 $\sum a_i+b_j$。要求 $(p_{i,j},q_{i,j})$ 对互不相同。

这个可以是，构造 正交拉丁方，对于 $n\ne 2,6$ 都有解，不会。

对于 $n$ 奇数，可以构造：$p_{i,j}=i-j$，$q_{i,j}=i+j$。

对于 $n$ 偶数，再利用一点题目性质，由于模 $n-1$，所以 $n$ 个数有两个同余，分别为 $0$ 和 $\frac{n}{2}$。可以，构造 $a_0$ 和 $a_{\frac{n}{2}}$ 分别在两个列中出现 $2$ 次，剩下元素每行每列各一个。那就是 $p_{i,j}=i+j$，$q_{i,j}$ 的第 $0$ 和 $\frac{n}{2}$ 行分别是 $0,\dots ,\frac{n}{2}-1$ 和 $\frac{n}{2},\dots ,n-1$，剩下再按某种方式排。

根本说不清是什么、为什么，下面是 $n=6$ 和 $n=8$ 的 $q_{i,j}$：

0 0 1 1 2 2 
2 4 0 5 1 3 
3 2 4 0 5 1 
5 3 3 4 4 5 
1 5 2 3 0 4 
4 1 5 2 3 0 

0 0 1 1 2 2 3 3 
3 6 0 7 1 4 2 5 
5 3 6 0 7 1 4 2 
2 5 3 6 0 7 1 4 
4 4 5 5 6 6 7 7 
7 2 4 3 5 0 6 1 
1 7 2 4 3 5 0 6 
6 1 7 2 4 3 5 0 

感觉并没有很懂。