1423n

BubbleSquare Tokens 神仙构造题。 首先，我们令所有点初始都没有放币，所有边上都放了一个币。则此时每个点的权值即为它的度数。 然后，我们考虑从小到大计算每个点的权值。对于每个点 \(i\)，我们枚举它所有相邻且编号比它小的点，假如该点上没有币，就把币从连接两点的边上移到另一端的点上 ......

先将无向图转为一个 DAG，直接从大点向小点连边就可以。 考虑增量构造，假设当前已经构造完了集合 ${1,2,\cdots,i-1}$，他们满足有边的点权值不同。现在我们加入第 $i$ 个点。那么枚举他的出边，将出点按点权分为两类。如果我们最初令所有边权都为 $1$，那么当前点的出边边权也都为 $1 ......

CF1423N BubbleSquare Tokens 有一个很经典的思路。发现直接不好做，因为改边会影响一对点，所以考虑钦定操作顺序，按编号从小到大做，使得已经操作过的点的 token 不会改变。这样做最大的好处在于每次只用仅仅考虑当前操作点的 token 是否与相邻已操作的点的 token 一致 ......