题解 CF1438D 【Powerful Ksenia】

· · 题解

Solution

构造题 , 应先从小情况看起 .

不妨设它们为 [ a ,b ,c ] , 操作一下 , 变成了 [ x , x ,x ] , x 是它们的异或和 . 好像就做完了 .

不妨设它们为 [ a , b , c , d ] , 把前三个操作一下 , 变成了 [ x , x , x , d ] , 好像没有结束 . 但我们假设最终状态 ( 假设能完成 ) 是 [ y , y , y , y] ,那么显然 , 异或和是 y \oplus y \oplus y \oplus y = 0 .

这时我们注意到 : 如果对一个序列进行一次操作 , 异或和将变为 ( 设原状态为 [a , b , c , ... , z ] , 我们对 a , b , c操作 ) : ( a \oplus b \oplus c) \oplus ( a \oplus b \oplus c) \oplus ( a \oplus b \oplus c) \oplus ... \oplus z = a \oplus b \oplus c \oplus ... \oplus z , 没有改变 .

所以 , 我们发现 : 对于一个偶数数列 , 它能变成全部一样的条件是 : 原序列异或和为 0 .

那么 , 回到开始 , 我们发现 : x \oplus x\oplus x \oplus d = 0 \Rightarrow x=d . 所以 , 我们知道 , 四个数只有前三个数和第四个数异或和相等 ( 其实也就是四个数异或和为 0 ) 时有解 , 否则无解 .

不妨设它们为 [ a , b , c , d , e] .

我们将前 3 个操作一下 ,变成 [ x ,x , x ,d ,e ] ; 再把后三个操作一下 ,变成 [ x ,x , y , y ,y ] ; 好像 y 更多一些 , 那我们把 x 变成 y : 将前两个和最后一个操作一下 ( x \oplus x \oplus y = y ) , 就全变成 y 了 .

受此启发 , 我们可以构造出一个方案 : 从 第 1 , 3 , 5 ... 个数出发 , 每次 3 个数操作一下 , 数列就可以变成 [ a , a , b , b , ... , z , z ,z ] 的情况 . 这时候我们把所有不是 z 的数都变成 z , 也就可以将第 1 和 2 , 3 和 4 , 5 和 6 ... 都和最后一个数操作一遍 , 我们就可以得到全是 z 的序列了 .

这样操作数量是多少呢 ? 分析一下 , 第一轮要操作 \frac{n-1}{2} 次 , 第二轮就是 \frac{n-3}{2} 次 , 加起来是 n-2 次 . 满足限制 .

code :

if(n&1) {
    printf("YES\n");
    printf("%d\n",n-1);
    for(int i=1;i<=n-2;i+=2) printf("%d %d %d\n",i,i+1,i+2);
    for(int i=1;i<=n-2;i+=2) printf("%d %d %d\n",i,i+1,n);
}

和奇数类比 , 我们也从 第 1 , 3 , 5 ... 个数出发 , 每次 3 个数操作一下 . 设原序列是 [a ,b ,c ,d ,e ,f ] , 那么就会变成 [ x ,x ,y ,y ,y , f ] , 和四个数的一样 , 只有 y =f 时才有解 ( 想一想为什么 ) , 此时不就成了 [ x,x,y,y,y,y] 了吗 ? 剩下的处理就一样了.

对于任意偶数 , 我们采取一样的策略 . 先看第一轮操作后倒数第二个数和最后一个数是否相等 , 不等就无解 .

如果相等 , 那么从 1 , 3 , ... ,(n-5) 开头的两个数都和最多的最后 4 个数不一样 ,分别把它们和最后一个数操作一下即可.

这样操作数量又是多少呢 ? 分析一下 , 第一轮要操作 \frac{n-2}{2} 次 , 第二轮就是 \frac{n-4}{2} 次 , 加起来是 n-3 次 . 也满足限制 .

code :

for(int i=1;i<=n-2;i+=2) a[i]=a[i+1]=a[i+2]=a[i]^a[i+1]^a[i+2];
if(a[n]!=a[n-1]) printf("NO");
else {
    printf("YES\n%d\n",n-3);
    for(int i=1;i<=n-2;i+=2) printf("%d %d %d\n",i,i+1,i+2);
    for(int i=1;i<=n-4;i+=2) printf("%d %d %d\n",i,i+1,n);
}

总结

这给我们提供了一个做构造题的好方法 : 从小情况起 , 类比出大情况 .

另外 , 异或又许多美妙的性质(比如同一个数异或两次为 0 ) , 对我们做题有很大帮助 .