AGC006

AGC006D

非常有意思的一个题。

直接做复杂度是 $O(n^2)$ 的而且看不出什么优化空间。

“中位数”的题往往和二分答案有关,因为这样可以转化成区间内 $0/1$ 的个数。这个题,可以先二分答案,设二分出来的值是 $x$ ,我们尝试判断第一层的数是否 $\le x$ 。我们把所有 $\le x$ 的数设置为 $0$ ,把剩下的数设置为 $1$ 。不难发现这个序列在进行操作后得到的序列的 $01$ 含义是不变的。现在我们转化成了一个 $01$ 序列进行操作,最后堆顶的数是 $0$ 还是 $1$ 。

然后画个图手玩一下,会发现所有长度 $\ge 2$ 的连续段在往上的过程中必然会复读,而长度为 $1$ 的连续段必然会翻转。而在 $\ge 2$ 的连续段复读的过程中会和附近翻转的 $01$ 变得相同。而且,一个长度不少于 $2$ 的连续段一定会一直向左同化,直到遇到一个同样长度不小于 $2$ 的连续段。

现在问题就变得很简单了。考虑最中间这个格子最早会被谁同化,就是枚举它左边和右边看看第一个长度大于等于 $2$ 的连续段的距离。如果不会被同化,也就是说相邻互不相同,那么这个东西就会一直反色直到结束。

复杂度 $O(n\log n)$ 。

AGC006C

去年写的题。

大概就是考虑跳跃之后期望的变化,大概是个形如 $a_i = a_{i+1}+a_{i-1}-a_i$ 的东西。这是个经典的差分形式,差分后就是交换 $d_i,d_i+1$ 。于是现在问题就变成了给一个置换,求 $10^{18}$ 次后的序列长啥样,经典的快速幂。

AGC006E

一个感觉很可做的 E 。

首先,任意一列内部的三个数自始至终不会变,只会改变上下的顺序。所以我们给每列标号为最小数除以 $3$ 上取整,如果这列是颠倒的就标为负数,例如 $1,2,3$ 标为 $1$ ,$9,8,7$ 标为 $-3$ 。

于是现在我们相当于给定一个数组有正负,每次可以交换一对距离为 $2$ 的数同时给这两个数以及中间的数一起取反,最后需要变成 $1,2,3,\dots ,n$ 。

显然,我们应当对奇偶分开考虑,交换只会发生在奇数内部和偶数内部。

手玩一下五个数或七个数的情况,会发现当我们交换了 $i,j$ ,如果 $i,j$ 都是奇数,那么当 $|i-j| \equiv 1 \pmod 2$ 的时候这两个数会同时变号,并且可以任意选择一个 $[i,j]$ 内部的偶数位置变号。具体操作就是假定要变号的位置是 $k$ ,就先 $i \to k-1$ 再 $j \to k+1$ 然后交换 $i,j$ 再移动回去。

于是会发现一个奇妙的操作:可以让 $i,j$ 先操作一次再操作一次。于是我们可以让奇数或者偶数中的两个位置变换符号!

所以说,我们只需要关心奇数和偶数内部的负号的奇偶性。

由于这个操作的作用顺序是不重要的,我们可以先将上下分别通过交换排序,再通过这种操作来消去符号,也就是看奇数偶数内部的负号个数是否为奇数,若有一边为奇数就不行。所以现在对于交换操作,交换时 $i,j$ 得到的负号就没用了,只有另一边的负号有用。

现在还有一个问题在于如何排序来使上下尽量都是偶数。但是手玩一下发现,排序的时候交换次数的奇偶性是一定的。因为每次交换除了交换的两个元素中间的逆序对改变个数一定是 $2,-2$ 这种,所以交换次数的奇偶性就是逆序对的奇偶性。这个题中可以随便排序,每次把 $1,2,3,\dots ,n$ 归位或者按照置换来最少次数排序都一样的。

AGC006F

神仙题。

开始一看以为是什么三元环计数之类的,做了一下发现不太可做。因为这个东西会一直不断加边就很困难。没想到最后还是个结论题。。

考虑给整个图染色,染 $A,B,C$ 三种颜色。

然后结论:

  • 如果染色结束了,我们并没有用到全部的三种颜色。

    这是最显然的情况。图上根本不存在 $x \to y , y \to z$ ,自然不存在加边,所以边数保持不变。

  • 如果染色结束了,我们用到了全部的三种颜色,并且没有出现矛盾。

    结论是,任意两个 $A,B$ 点间,任意两个 $B,C$ 点间,任意两个 $C,A$ 点间都会连上边。

    考虑三个点 $x,y,z$ 分别的颜色是 $A,B,C$。考虑一个点 $v$ 与 $x,y,z$ 中任意一个相邻(这里的相邻是无向图上的)。显然我们必然可以通过连边,让 $v$ 与这三个点中的两个点相邻。然后再对于一个点 $w$ ,假定它和 $v,x,y,z$ 中有一个相邻,那么我们必然可以通过连边,让它与其中至少两个相邻。然后我们不管 $v$ ,就可以说明它和 $x,y,z$ 中至少有一个相邻。归纳下去,我们可以说明 $w$ 与其中两个点相邻。同理,我们可以说明连通块内任意一个点和其中两个点相邻。

  • 如果这张图不能用这三个颜色染色。这个时候整个连通块在一直操作下去后会变成一个完全图(包括自环的完全图)。

    手玩过都会发现,只要有自环,这个连通块必然就被整成完全图了。

    考虑发生冲突的一条边。它肯定在无向图的某个环上。如果不在,它是个桥,那么通过合理分配颜色它一定不会有冲突。考虑这个无向图的环,每次选择这个环上的 $x \to y , y \to z$ 这么两条边,如果不存在这样两个边,那么一定不会有冲突存在,然后整成 $x \to z$ ,然后这个环就会缩小,同时这个环仍然不能满足限制,因为会发现无论不满足限制的边是否被缩,这个环还是不满足限制的。一直这么进行下去,最后一定会得到一元环。

文章作者: yijan
文章链接: https://yijan.co/2020/11/18/agc006/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog