【学习笔记】构造

没长脑子

构造题大都很新，所以解决它们并不是一件容易的事 。

Nastia and a Beautiful Matrix

出师不利

要使能填的数目最大，大概长这样 。

发现奇数行可以随便填，于是直接莽，然后 wa 了 。

首先判断出众数不能超过 $n\times \lceil \frac{n}{2}\rceil$ 次。

然后观察斜对角线的情况 。

把给的数拍扁成序列 。 出现次数多的先填，众数放在最前面 。

1. 填行为奇，列为偶的格子
2. 填行为奇，列为奇的格子
3. 填行为偶，列为奇的格子

这样填一定合法 。

Off by One

不会。

想到第一步转化了应该就不难 。

如果我们把能消除的点两两连边，这样是求无向图最大边独立集，而且边数是 O(n^2) ，寄 。

如果我们 点转边 ，问题背景就很熟悉了 。

直接跑生成树即可 。

One-Four Overload

构造题（x）
猜结论（v）

把无解判掉后，很容易猜到这题一定有解。

对于四个位置的情况，限制为相邻两点数字不同 。

然后就可以愉快地二分图染色了 。

可以证明没有奇环 。

证明并不困难 。 考虑欧拉回路 。

Johnny Solving

对于无向连通图。

自然而然想到跑 DFS 树。

如果叶节点深度 >=n/k ，那么输出路径。

否则至少有 k 个叶子结点 。考虑对每个叶子结点构造一个环 。

结合入度 >=3 可以做到 。

这题和 Pairs of Pairs 考的都是一个东西 。