AGC041E Balancing Network

pufanyi

发布于：Mar 11, 2020

有 $n$ 条线 $m$ 个平衡器，从左往右第 $i$ 个平衡器连接了 $x_i,y_i$ 条电线（ $1\le x_i<y_i\le n$ ），每个平衡器都有一个状态：向上或向下。考虑一个令牌，从最左边的某一条导线开始，如果在第 $i$ 个位置，如果他在 $x_i$ 导线上且平衡器状态向下，那么就到 $y_i$ ，同理如果在 $y_i$ 且状态向上，则到 $x_i$ 。记 $k_i$ 表示令牌从导线 $i$ 开始到无穷远处是他在哪条导线上。

让你构造两种解，每种解用一个字符串表示，表示每个平衡器的状态。第一组解要求所有的 $k_i$ 相等，第二组接要求至少有两个 $k_i$ 不相等。无解输出 $-1$ 。

数据范围 $2\le n\le 5\times 10^4,\,1\le m\le 10^5$ 。

一道有趣的构造题。

首先我们考虑构造第一组解。我们考虑从后往前做，枚举 $t$ 判断是否有一组解使得最终所有 $k_i=t$ 。令 $f_{i,j}$ 表示仅有最后 $i$ 个平衡器时，第 $j$ 条线上的令牌是否到了 $t$ 。考虑在最前面加一个平衡器。发现其实就是 $f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_j}\vee f_{i,y_{n-i}}$ 。因为只要有一条线上可以到达 $t$ ，我们可以将两条线上的令牌都导到这条线上。

考虑上面的做法将第一维滚掉之后是 $\mathcal{O}(m)$ 的，于是我们得到了一个 $\mathcal{O}(nm)$ 的算法。考虑优化，我们令 $g_{i,j,t}$ 表示最后 $i$ 个，第 $j$ 条线是否能到达 $t$ 。我们考虑转移就是 $g_{i+1,x_{n-i},t}=g_{i+1,y_{n-i},t}=g_{i,x_{n-i},t}\vee g_{i,y_{n-i},t}$ 。不难发现这个东西可以用 bitset 进行优化。常数 $\frac{1}{64}$ ，可以过。

然后考虑构造，这就简单了，直接沿着一个有解的 $t$ ，继续做一遍上面的 dp 即可。

然后考虑第二问，首先我们发现之后当 $n=2$ 的时候才会发生无解。其余时刻都不会，至于为什么，我们考虑一下的构造方法。

仍然考虑倒着做， $f_{i,j}$ 表示加入最后的 $i$ 个平衡器，第 $j$ 根线上的令牌现在在哪儿。

我们考虑加入一个令牌，那只会有两种状态： $f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_{n-i}}$ 或是 $f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,y_{n-i}}$ 。而最终的目的是让至少有两个 $f$ 值是不相等的。那么我们考虑 $g_{i,j}$ 表示 $f_{i,k}=j$ 的数量。这样我们只要比较两个 $f$ 的 $g$ ，看看那个多，让多的给少的一个。考虑到 $n>2$ ，每次将一个 $g$ 加 $1$ ，一个 $g$ 减 $1$ 。不难发现一定有两个 $g$ 是大于 $0$ 的。于是一定有一种方案合法。