Java教程

关于一类可逆图上变换问题的总结

本文主要是介绍关于一类可逆图上变换问题的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

最近多校补题的时候连着做了两个题,发现它们的内核惊人地相似,所以写一篇来总结一下(可能是久违的复活文)。
想看结论可以直接看结尾

----------------------------------------------------

2021暑期多校解题报告
0tree
题意:给出一棵带有点权a(非负整数)和边权e(整数)的树,可以做若干次如下的操作:选择两个不同的结点x, y和一个非负整数w,将x, y的点权各自异或w,将x->y路径上的边权依次+w, -w, +w, ..., (路径长度为偶数以-w结尾,奇数以+w结尾),问是否可以在4n次操作以内将所有的点权和边权变为0。可以的话输出方案。
n<=10000,点权和边权的绝对值在1e9以内。

分析:
1. 首先,单独考虑异或操作,可以将问题转变为:对于一棵树,每次同时将任意两个结点的权值异或w,问是否可以将整棵树的权值变为0。
不难发现这个时候树的结构没有起到任何作用,和相同的问题在序列上的效果是一样的。#可以发现当且仅当所有结点的权值a异或和为0的时候,可以在O(N)的规模下将所有结点的权值变为0#(选取一个点为参考点,依次将它和其他任意点i同时异或上点i的权值)。因为同时异或两个点,所以所有点的权值异或和是不变的,故当把除参考点以外的所有点权值变为0之后,如果所有点的疑惑合为0,那么参考点的权值也应该为0,否则不存在方法可以让所有的点权值为0。
2. 考虑关于边权的操作,显然直接按照题目描述的操作来说过于复杂了,一次操作涉及到的对象太多,不利于我们思考问题。于是考虑简化操作,将边权转化为点权,即令一个点的和点权b等于与它相连的所有边权的和。
接下来我们证明,#所有边权等于0等价于所有和点权b等于0#:
假设当和点权为0的时候,存在边权不为0。显然我们可以发现,如果叶子结点的点权等于0,那么其父边的边权一定为0,又因为父亲的和点权为0,那么父亲的父边为0......如此,递归地证明了必要性;
假设边权全部为0,那么显然和点权b为0,证明了充分性。
那么,问题转化为是否可以让所有点的和点权为0。注意到,当x->y链长为奇数的时候,x+w, y+w;链长为偶数的时候,x+w, y-w,因此操作按链长的奇偶性分类。基于这一点想到给树分层(二分染色)。可以发现每次操作相当于是重新分配了同色层的b,对于异色层则是同时增大了权值。于是我们可以注意到,和点权可以全部为0等价于和点权的和小于等于0且奇偶层的sumb相等(参考1中参考点的做法证明这个想法)。
3. 现在分开地考虑了两个问题,考虑将两个问题合并起来。我们考虑先将所有的点权a变为0,现在问题变为:在不改变a的情况下,如何让所有的b变为0。
考虑不改变a的条件。由于是异或操作,因此只要异或两次就不会改变a。那假设在将所有的b变为0的过程中保证这个条件,就是考虑将忽略a的情况下只需要进行一次的操作|b|拆分成两个2 * |b|/2,于是我们要求b的值一定要是一个偶数。
注意到本题的操作分别是异或和求和,当他们的一个参数(w)相同的时候,会注意到结果的奇偶性变化是同步的(w为奇,改变奇偶,w为偶,奇偶不变)。因此可以发现所有点a b奇偶性一致是可以让所有点权和边权为0的必要条件。在这个基础上,可以发现当所有的a都为0的时候,因为a与b的奇偶性一致,那么b必然为偶数。因此就可以将一个操作正确地拆分成两个相同的操作了。

综上,可以将所有的点权和边权同时归零等价于三个条件:
1. 所有点权a异或和为0。
2. 两色层各自和点权b的和<=0,并且相等。
3. 每个点上a与b的奇偶性相同。
输出方案的时候,对于奇偶层各自选取一个参考点,先把所有的点依次与自己所在层的参考点成对操作,然后操作两个参考点。重复两次即可,可以在3n次以内完成。


power station of art
题意:现有一种图(不保证连通),点有编号,点上有数字和颜色(R, B),可以进行任意次操作:选择一条边<u, v>交换u, v上面的数字,如果u, v上面的颜色相同,那么翻转颜色;如果颜色不同,那么不变化。现在有两张结构一样的图(即点集边集相同,但是点上的数字和颜色不同),问是否可以通过若干次操作(可以不操作),使得两张图完全一样?输出YES或者NO。

分析:
依旧分开考虑两种操作:
1. 对于交换数字,可以发现只要两张图连通分量点上值的集合相同,那么就可以使得两张图相同。显然这是充要条件。
2. 对于交换颜色,题目中的操作依然显得有一点晦涩。因此等价地理解题意:将两个点的颜色交换,然后翻转。这样就统一了问题。
注意到这是一个二色的问题,对于图我们联想到二分图,因此我们按照二分图来讨论问题。
2.1.如果连通分量是二分图。可以发现当交换两个点的时候,集合的颜色(w/h)和点的颜色(r/b)是同时变化的。考虑一个不变量------颜色的异或始终不会发生变化。那么显然,两张图中的(number, pointcolor^graphcolor)二元组的集合应该完全相同,两张图上的点形成一个单射。这显然是一个充要条件。
2.2.如果连通分量不是二分图,这意味着图中至少含有一个奇环。考虑这个奇环可以做什么------可以固定上面所有点的数字,而使得两个相邻点的颜色发生变化(1按次序交换到n,再与2交换,然后2反向地交换回1的旁边)。
同时,注意到一个必要条件------两张图连通分量上的颜色数量的奇偶性必须相同(因为无论操作是那种情况颜色数量的奇偶性都不会改变)。
这意味着,利用奇环的这个性质可以让环上所有点同时变成我想要的颜色(先挨个变化,剩下最后两点的时候,以为颜色的奇偶性是相同的,因此一定可以操作过去)。
在满足两个必要条件的情况下,考虑这样一种策略:对两张图上的点做一一映射。如果一个点不在任何的简单奇环里面,我们就让它换到奇环和它在的块连通的那个点,把它变成想要的颜色,然后处理其他的点,使得它在自然到达它映射的点的时候变成自己想要的颜色。然后再通过奇环的特殊性调整环上的值和颜色(如果觉得不好理解那就把图简化成基环树,就很好理解了)。
这样,我们证明了非二分图只要满足两个必要条件即可完成目标。

综上,可以将两个图变得相同,等价于:
1. 所有连通分量对应的点上数值集合相同。
2. 所有的连通分量:
2.1. 是二分图,则(数值,pointcolor^graphcolor)二元组集合相同。
2.2. 不是二分图,则r/b两色数量的奇偶性对应相同。


总结:
回过头来看两题,可以发现它们在表面上完全不相关,但是仔细思考可以发现它们的内核惊人地相似:

  1. 对图的两个点进行操作
  2. 操作可逆
  3. 操作同时修改两种属性,形成约束
  4. 操作的效果和奇偶相关

根据2,容易想到寻找操作中的不变量。因为操作可逆,如果不变量相同,那么这两种情况就形成了等价类。第一题中的向参考点简化,第二题中二分图部分的处理都运用到了这一点。
根据3,我们在思考时可以考虑是否存在一种方案,使得保持一个属性不变的同时改变另一个属性。第一题中最后b的归零,第二题中奇环部分性质都运用到了这一点。
根据4,图的奇偶性可以考虑到二分图。根据二分图将问题进行分类,往往可以让问题变得易于思考。二分图本身有非常好的性质,而非二分图又有奇环,因此可以很好地考虑问题。

同时,在补这两个题的过程中,注意到对于一张图上的操作不好思考的时候,可以考虑更强的树/基环树上的操作。这样问题变得更加见解,而且如果命题在强环境(注意树这样的环境是强是弱要根据问题来判断)下成立,那么在弱环境的图上就一定成立。
而且在问题看起来复杂的时候,可以通过一些简单的转化把问题转化成简单易懂的版本。统一性可以更好的帮助我们解决问题。

这篇关于关于一类可逆图上变换问题的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!