CF1867B XOR Palindromes

One_JuRuo · 2023-09-12 10:28:21 · 题解

思路

题目问的是改 i 位，能不能让原串变成回文串，其中 0\le i \le n。

首先，我们可以统计前后对称位置不一样的对数，记为 k，那么至少也得改 k 次，假设剩下前后对称位置一样的有 m 对（如果 n 为奇数，则最中间的一位不计入 m），那么在 k 次的基础上，可以增加偶数次，即把两个对称位置一样的都改了，最多可以改到 m 次，即 k,k+2,k+4 \cdots k+m\times2。

还需要考虑 n 为奇数的时候，最中间的一位可以改或不改，所以能成功地有 k,k+1,k+2\cdots k+m\times2+1。

实现可以用一个数组记录答案，但是千万不要用 memset，因为如果用 memset 的话，就会 TLE，不要问我为什么知道（痛苦面具）。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,len,d,bd,ans[100005];
char ch[100005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%s",&n,ch+1),d=bd=0;
        for(int i=0;i<=n;++i) ans[i]=0;
        for(int i=1;i*2<=n;++i)
        {
            if(ch[i]==ch[n+1-i]) ++d;
            else ++bd;
        }
        for(int i=0;i<=d;++i)
        {
            ans[bd+i*2]=1;
            if(n%2) ans[bd+i*2+1]=1;
        }
        for(int i=0;i<=n;++i) printf("%d",ans[i]);
        puts("");
    }
    return 0;
}