题解 CF1867B XOR Palindromes

· · 题解

XOR Palindromes

题目大意

给出一个长度为 n 的 01 串(只含 0,1 的字符串) s。定义一个数 x 是好数，当仅当存在一个长度也为 n 的 01 串 l 使得对于所有的 s_i 被 s_i\oplus l_i 替换后得到的 01 串是一个回文串。

对于给出的一组 n,s ，你需要给出一个长度为 n+1 的 01 串 t ，t_i=1 当仅当 i 是一个好数。注意，t 从 0 开始编号

题目中 \oplus 表示异或。

回文串指正着读反着读都相同的字符串，比如 0110,01010,1111 都是回文串。

首先我们注意到，一个 s_i\oplus 0 不会改变 s_i 的大小，\oplus 1 相当于给 s_i 取反。

所以其实好数就是存在一种方案对 s 的不同位置修改 x 次之后 s 可以变成一个回文串。

首先我们可以想到 求出最少的修改次数 x_0，那么 n-x_0 也一定满足条件。因为修改 1 和修改 0 的方案是对称的：我们使用修改 x_0 次的方案修改后再对整个串取反，将与 x_0 的方案抵消的修改次数减去就是 n-x_i。这也意味着当 x<x0 或 x>n-x_0 时一定不满足条件。

其次我们可以想到，在上面 范围内的任意 x_k=2k+x_0 (k\in N) 也是可以成立 的。因为可以在花 x_0 的次数将 s 操作成回文串之后花偶数次操作 在两边对称修改 ，得到的还是回文串。

继续思考就会发现问题：如果 x_k 构造完回文串之后还要奇数次操作呢？

对于一个长度 n 为奇数的 s，因为它的对称中心刚好是 \frac {n} {2}+1 位，所以当我们构建完回文串还剩奇数次操作时，可以 对这个中心操作一次，转化为偶数次操作 的情况；但是 n 为偶数时无法进行这样的转化，也就无法对称操作，那么 x_k 就不是好数。

所以，我们可以按照如下方法判断：

首先求出将 s 修改为回文串所需要的最小次数 x_0:将 s 对折比较，找出不同位置数量即可。

然后对于一个整数 x 判断：

考场code:


#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int s[N];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        char tmp[N];
        scanf("%s",tmp);
        for(int i=0;i<n;i++)
        {
            s[i+1]=(int)(tmp[i]=='1');
        }
        int h1=0;
        for(int i=1;i<=n/2;i++)
            if(s[i]!=s[n-i+1]) h1++;
        if(n&1)//奇数
        {
            for(int i=0;i<=n;i++)
                if(h1<=i&&i<=n-h1) printf("1");
            else printf("0");
        }
        else {//偶数
            for(int i=0;i<=n;i++)
                if(h1<=i&&i<=n-h1&&(i&1)==(h1&1)) printf("1");
                else printf("0");
        }
        printf("\n");
    }
    return 0;
}