首页 > 其他 > 详细

Codeforces Round #743 (Div. 2)题解

时间:2021-09-24 19:29:34      阅读:42      评论:0      收藏:0      [点我收藏+]

A,B,C过得还算艰险,主要是昨天cf炸的有点厉害....一直在打第四题的时候,才知道B,C错了,又得回去调...

D. Xor of 3

简化题意:给定一个长度为n的0/1序列,每次可以将连续的三个数变成他们异或后的值,问是否存在一种构造方案使得操作次数<=n,并且使得序列中的所有元素都为0.
首先想到的就是将所有的情况罗列下来:
000 -> 111, 110 -> 000, 100 -> 111 (111-> 111)
首先发现只有110 -> 000能把1变成0,之后能发现只要0后面有偶数个连续的1,就都能把他们变成0,比如01111,需要两次就能把他们都变成0.再来看000->111的作用,似乎可以改变1的个数,倘若我们有一定数量的0,我们可以采用这个操作,使得变成的三个1和后面的1结合构成偶数个1,这样的话我们就能推知,只要我们有一个连续的四个0,那么遇到单独的1我们也能将它变成0.例如00001,我们可以先变成01111,之后再用两次就行了。那么我们就尽量找着连续的四个零,只要找到一个,整个序列就都可以变成0了。至于操作100->111,可以看到1的个数从1变成了3,奇偶并没发生变化,似乎没什么用。如何找到连续的0呢,我们从每一个0出发,根据110->000向左右扩展即可。

Codeforces Round #743 (Div. 2)题解

原文:https://www.cnblogs.com/gcfer/p/15310820.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!