Description

There are two sequences({Ai},{Bi}) of length N.
Your goal is to minimize the times of operations that turning A into B.You can repeatly perform the following operations：
1.Let the XOR of all elements in A be X
2.Replace a arbitrary element in A with X
 Especially,if it is impossible to turn A into B,output “-1”
 N<=10^5,Ai,Bi<=2^30
 

Analysis

let a[0] be a[1] xor a[2] xor …. xor a[n],and so as b[0],and then it is simple to judge -1
the operation equal to swap a[0] and a[i]
After considering some simple cases,we notice that the procedure corresponds permutations,which mind us using graph to solve it.
Conclusion:If the connected component(including k vertex) including a[0],then ans+=k else ans+=k+1
Obviously if a[i]=b[i] we will never change it,else we link an edge from a[i] to b[i].
Since the in-degree equals to the out-degree for any vertex,every component constitute a Eulerian circuit.So we prove the conclusion above.
Now the problem is simple:Only need to count the number of connected component in the graph by union-find sets.

最后

以上就是冷艳蜡烛为你收集整理的【AGC 016 D】XOR ReplaceDescriptionAnalysis的全部内容，希望文章能够帮你解决【AGC 016 D】XOR ReplaceDescriptionAnalysis所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。