(如果文中有伪证，请联系我)
C3
每个公司会把景点划分成 \(c=n^2-k\) 个连通块。
当 \(c\le n-1\) 时，必存在 \(2\) 个景点，它们在 \(A,B\) 公司中均位于同一个连通块内，不合法。
当 \(c = n\) 时，我们
- 让 \(A\) 公司的第 \(i\) (\(1\le i\le n\)) 个连通块包含所有编号为 \(jn+i\) 的点；
- 让 \(B\) 公司的第 \(i\) (\(1\le i\le n\)) 个连通块包含所有编号在 \([(i-1)n+1,in]\) 内的点；
可以使任意 \(2\) 个景点不被 \(A,B\) 公司同时联通。
因此，符合题意的最小 \(k\) 为 \(n^2-n+1\)。
C4
即，求最小的整数 \(c\)，使得存在一张点数为 \(c\) 的图，第 \(i\) 个点高度为 \(x_i\)，且存在 \(n\) 条边，第 \(i\) 条边连接 \(u_i,v_i\)，且
\[|x_{u_i}-x_{v_i}|=F_i \]记 \(G_i\) 表示加入了前 \(i\) 条边的图。注意到
\[\forall n\ge 2, \ F_n\ge \sum_{i=1}^{n-2} F_i \]因此，\(\forall i\ge 1\)，要想在 \(G_{2i-1}\) 中加入一条两端高度差为 \(F_{2i+1}\) 的边，必然会连通 \(2\) 个不同连通块。
记 \(l_i\) 为 \(G_i\) 中连通块个数。可以归纳地证明 \(G_{2i-1}\le c-i\)，因此 \(Ans\ge \lceil\frac{n}{2}\rceil+1\)。
\(c = \lceil\frac{n}{2}\rceil+1\) 的方案：\(\forall 1\le i\le c\)，\(x_i = F_{2i-1}\)。
C5
设 \(m=\frac{p-1}{2}\)。
假设存在一种方案，那么可以选出 \((n_1,a_1),(n_2,a_2),\cdots,(n_{2m},a_{2m})\) (\(a\) 是 \(2m\) 阶排列) 和一个长度小于 \(pm(m+1)\) 的 \(01\) 序列，使得 \(\forall 1\le i\le 2m\)，它的长度为 \(pn_i\) 的前缀中有 \(a_in_i\) 个 \(1\)。
不妨设 \(n\) 为递增序列。那么 \(\forall 1\le i<2m\)，\(0\le a_{i+1}n_{i+1} - a_in_i\le p(n_{i+1}-n_i)\)。经过推导，可得
\[\frac{n_{i+1}}{n_i} \ge \max\left(\frac{a_i}{a_{i+1}},\frac{p-a_i}{p-a_{i+1}}\right) \]写几个例子，发现总有 \(n_{2m}\ge m(m+1)\)。
不妨假设在 \(a\) 中，\(2m\) 在 \(1\) 左边。假设 \(a_u=1\)，\(a_v>m\) 且 \(a_{v+1..u}\le m\)，\(mx\) 为 \(a_{u..2m}\) 最大值。则
- \(n_v\ge v\)
- \(n_u/n_v\ge m+1\)
- 对 \(v\) 进行讨论
- \(v<m\) 时，\(n_{2m}/n_v \ge 2m/(v+1)\) \((\because mx\ge 2m-v)\)
- \(v\ge m\) 时，\(n_{2m}/n_v \ge 1\)
因此，\(n_{2m}\ge m(m+1)\)，与假设矛盾，得证。
C6
规定 \(i\) 和 \(4n-i+1\) 要同时选或同时不选。因为每种颜色要选恰好 \(2\) 个，所以我们肯定是选了 \(n\) 对总和为 \(4n+1\) 的硬币，体积和是对的。
假设硬币 \(i\) 的颜色为 \(c_i\)，我们对每种颜色建一个结点，并在 \(c_i\) 和 \(c_{4n-i+1}\) 之间连边 (\(\forall 1\le i\le 2n\))。现在我们得到了一个每个点度数均为 \(4\) 的图，我们要保留一个边的子集，使得每个点度数均为 \(2\)。跑一遍欧拉回路，只保留奇数步经过的边即可。
*C7
即证，\(\forall (R_1,C_1),(R_2,C_2)\)，\(\exists (R',C')\subseteq(R_1,C_1)\) 使得 \(|R'|\le \min(|R_1|,|R_2|)\)。
第一步，找到 \(2\) 个单射
- \(\rho: R_1\to R_1\)
- \(\sigma: C_1\to C_1\)
使得 \(|\rho(i)|\le \min(|R_1|,|R_2|)\)，且 \(\forall (i,j)\in R_1\times C_1\) 都有 \(a(\rho(i),j) \ge a(i,\sigma(j))\)。
因为 \((R_1,C_1), (R_2,C_2)\) 均合法，所以可以找到以下 \(4\) 个单射：
- \(\rho_1: R_2\to R_1\) 使得 \(\forall (i,j)\in R_2\times C_1\) 都有 \(a(\rho_1(i),j)\ge a(i,j)\)
- \(\rho_2\)：\(R_1\to R_2\) 使得 \(\forall (i,j)\in R_1\times C_2\) 都有 \(a(\rho_2(i),j)\ge a(i,j)\)
- \(\sigma_1: C_2\to C_1\) 使得 \(\forall (i,j)\in R_1\times C_2\) 都有 \(a(i,j)\ge a(i,\sigma_1(j))\)
- \(\sigma_1: C_1\to C_2\) 使得 \(\forall (i,j)\in R_2\times C_1\) 都有 \(a(i,j)\ge a_(i,\sigma_2(j))\)
令 \(\rho = \rho_1\circ \rho_2\)，\(\sigma = \sigma_1\circ\sigma_2\)，则 \(|\rho(i)|\le \min(|R_1|,|R_2|)\)，且 \(\forall (i,j)\in R_1\times C_1\) 都有
\[\begin{split} & a(\rho(i),j) \\ = & a(\rho_1(\rho_2(i)),j) \\ \ge & a(\rho_2(i),j) \\ \ge & a(\rho_2(i),\sigma_2(j)) \\ \ge & a(i,\sigma_2(j)) \\ \ge & a(i,\sigma_1(\sigma_2(j))) \\ = & a(i,\sigma(j)) \end{split} \]第二步，构造答案。
设 \(k\) 为任意非负整数，则 \(\forall (i,j)\in R_1\times C_1\) 都有 \(a(\rho^k(i),j)\ge a(i,\sigma^k(j))\)，这是因为
\[a(\rho^k(i),j) \ge a(\rho^{k-1}(i),\sigma(j)) \ge \cdots \ge a(i,\sigma^k(j)) \]令 \(k=\max(|R|,|C|)!\)，\(R'=|\rho^k(i)|\)，\(C'=|\sigma^k(j)|\)。那么 \(\forall i\in R'\) 都有 \(\rho^k(i)=i\)。
因为 \((R_1,C_1)\) 合法，设
- \(\rho_0: R\to R_1\) 使得 \(\forall (i,j)\in R\times C_1\) 都有 \(a(\rho_0(i),j)\ge a(i,j)\)
- \(\sigma_0: C\to C_1\) 使得 \(\forall(i,j) \in R_1\times C\) 都有 \(a(i,j)\ge a(i,\sigma_0(j))\)
那么，
-
\(\forall(i,j)\in R\times C'\) 都有
\[a(\rho^k(\rho_0(i)),j)\ge a(\rho_0(i),\sigma^k(j))=a(\rho_0(i),j)\ge a(i,j) \] -
\(\forall (i,j) \in R'\times C\) 都有
\[a(i,j)\ge a(i,\sigma_0(j)) = a(\rho^k(i),\sigma_0(j))\ge a(i,\sigma^k(\sigma_0(j))) \]
得证。
标签：le,IMOSL2020,sigma,times,forall,ge,rho,C3,C7 From： https://www.cnblogs.com/alfalfa-w/p/17589841.html