AGC006D

题意：给出一个长度为 的排列。构造一个 层金字塔，最底层是该排列，其他层的数字按如下方式生成：方格 中填写的整数，是方格 正下方，左下方和右下方方格中所写整数的中位数。。

现在请求出第一层的数字。

看到题之后一眼二分答案，然后找性质失败。

事实证明当时做的时候还是太浮躁了。如果二分答案完了之后，有两个连续的 或两个连续的 ，那么它们肯定不会被别的东西给抹掉，只有可能因为到达边界而自行消除。

所以我们找到距离中点最近的相邻的一对 即可。

事实上，不会出现最近的 和最近的 离中点距离相同的情况，读者可以自证。

如果找不到，说明原序列一定是 相间，判断是容易的。

AGC006E

题意：给出 行 列的初始矩阵，第 行第 列的数为 。

我们有一个这样的操作：选择一个 的子矩阵，将这个子矩阵旋转 （具体见下面的图）。

现在给出一个 行 列的矩阵，问能否若干次操作使初始矩阵变成目标矩阵。

没有找到什么基本性质。/kk

首先，每一列的状态只可能是 或者 之类的，连续三个递增或递减的数。因为每次操作只会颠倒某些列，并移动某些列的位置。先把这个判掉。

那么每一列的状态就可以编码成一个数 ，一次操作相当于让 变成它们的相反数，并交换 。目标是让 。

我们发现奇数位置和偶数位置是相对独立的。如果交换了两个奇数位置，那么奇数位置的负号个数的奇偶性不会改变，而偶数位置的会改变 。

而为了让绝对值从小到大排序，我们对奇数位置的交换次数必须和奇数位置的逆序对数同奇偶。

那么这就说明：奇数位置的逆序对数和偶数位置的负号个数，奇偶性应该是相同的。同理，偶数位置的逆序对数和奇数位置的负号个数的奇偶性应该是相同的。

这是一个必要条件。充分性的话，因为我们能用若干次操作把 和 同时变成它们的相反数，并不改变其他数，所以先按绝对值进行排序，然后用这种操作把负号都做掉即可。

这个“若干次操作”可以参看洛谷题解。

AGC006F

题意：给出一张有向图 。

不断重复如下操作：取出三个点 ，如果 有边， 有边， 没有边，那么连边 。

请计算没有边可以添加的时候的边数。

做的时候在手玩树形图，看出来了跟层有关，但根本想不到如何推广。

首先对每个连通块单独考虑，然后尝试三染色。

这个三染色是怎么染色呢，我们希望对于边 ，都有 ，所以我们连边 ，，然后进行 dfs 即可。

考虑三染色失败了怎么办，这个时候任意两点之间都会有连边，答案为点数的平方，证明就是考虑 dfs 树上一条使其失败的返祖边。

如果成功了，但三种颜色没有用满，那么不会出现 这种东西，故答案为原先的边数。

否则可以猜出答案为 ，即异色点之间有单向边。接下来考虑证明。

肯定存在一条链 满足 。

归纳构造，假设图 已经满足上述结论，考虑新加入一条边 的情况。

接下来设 表示 的点的集合。

由于 ，所以 。

由于 ，所以 。

可以发现无法存在其他的边，得证。

因为 是本质相同的， 和 也是本质相同的，故其他情况不再赘述。

直接算答案即可。属于是想到了“染色”就能做大部分甚至做完的题。