构造趣题几道

发表于 2024-04-24 更新于 2024-05-10 本文字数： 2.1k 阅读时长 ≈ 2 分钟

对于一个 $n\times n$ 的矩阵， $[1,n\times n]$ 在其中各出现一次。

定义一条好路径为一个坐标序列 $(x_1,y_1),(x_2,y_2),...,(x_k,y_k)$ 满足 $(x_1,y_1)$ 是「山谷」并且 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 相邻，且坐标上的数字单调增。

「山谷」表示这个点的数字比与他相邻的点都小，相邻是四联通。

对于所有满足条件的矩阵，求好路径最小值，并构造方案。

来源：IMO 2023 T6

还是蛮有趣的。

小的向大的连边，dag 的路径计数，随便构造大概都是指数级的，肯定要尽量构造成树，这样路径比较唯一。

首先起点只有一个肯定优，不然隔开两个点能到范围的部分会计算多次，那么这个起点肯定可以到达所有点，不然就会有多个起点，因此答案是 $\mathcal O(n^2)$ 级别的。

由于路径中间出现环很容易乘起来到达指数级，所以考虑只在树的叶子处形成环，也就是我们选定若干点作为终点，把终点去掉之后，剩下的点形成一棵树。

还需要满足的条件是终点不能相邻。

考虑一下这样构造的答案，注意到总点数已知，总边数已知，去掉这些点只要满足剩下的点联通并且点边数满足条件就一定是树，而一个终点对答案增加的贡献与对点边数产生的贡献是相同的，所有合法方案的答案是相同的，计算后可以得到是 $2n^2-2n+1$ 。

然后考虑构造，由于终点不能联通，又要把其他点隔开，所以剩余点可以构造为若干条横着的「鱼骨」，然后左边串联起来即可。

$n$ 个人要打比赛，每两个人一场，一天比一场，总共 $\binom{n}{2}$ 天。

设第 $i$ 个人打的第一场比赛在第 $a_i$ 天，最后一场在 $b_i$ 天，求 $\min (\sum_{i=1}^n b_i-a_i+1)$ ，并构造方案。

来源：IMO2018 预选题 C5 。

注意：这里是一个 OI 化的题解，构造方案无一定合法的证明。

首先一个显然的观察， $[a_i,b_i]$ 不会存在严格包含的区间，不然可以调整使得答案不变。

考虑给出一组区间，如何构造方案。

先左端点排序，标号为 $[a_1,b_1],[a_2,b_2]...$ 。

那么直接贪心，左端点处加入区间，然后每次弹出右端点最小的区间，优先队列维护即可。

但是没啥用，还是要去构造方案，这个构造用增量法不好搞，考虑直接找其下界。

观察一下贪心放的位置的本质，对于 $1$ 来说，相当于是把 $(1,i)(i>1)$ 放在了 $a_i$ 之后第一个空的位置，然后对于 $2$ ，就是把 $(2,i)(i>2)$ 放在 $a_i$ 后面第一个空的位置，需要满足不能放到 $b_2$ 后面的地方。

因此容易观察出一个 $a_i$ 与 $b_j$ 直接的关系，具体的，设 $a_i+f_{i,j}\le b_j$ ，我们去找 $f_{i,j}$ 的一个值。

模拟上面的过程，容易得到：

f_{i,j} = \begin{cases} j(n-i+1), & i>j \\ (i-1)(n-i+1)+\sum_{k=i}^j (n-k) , & i\le j \end{cases}

开始猜了一个答案是 $\sum f_{i,i}$ ，然后爆。

差分约束一下？没啥用。

注意到由于左端点全部小于右端点，所以只要找一组左右的匹配求 $\max (\sum f_{i,p_i})$ 即可。

瞎 jb 找规律，发现 $\sum_{i=1}^n f_{i,n-i+1}$ 是最大的，打表观察出是答案。

考虑构造，由于 $f$ 满足交叉对称，所以想构造出满足所有约束的区间，尽量要满足 $a_i,b_{n-i+1}$ 关于 $\binom{n}{2}/2$ 对称，此时有取到他们距离的具体值，因此直接构造即可。