Codeforces Round 897 (Div. 2) - B. XOR Palindromes - 思维

B. XOR Palindromes

问题转换为：给定一个长度为n的字符串（只含有0或1），我们对它进行0次，1次，2次……n次翻转，使得它能成为一个回文串。如果进行i次翻转后能够成为回文串，则在第i个位置输出1，否则输出0。
最终结果是长度为n+1的字符串（只含有0或1）。

通过尝试几个样例可以发现，最终输出的结果是对称的。所以我们只需要得到前（n/2）字符即可，因为后面的字符和前面对应位置上的一样。

首先我们得到原始字符串s中不匹配的对数m，即最少需要m次翻转就可以把s变为回文串（最终输出的串第m个位置上的值一定为1）。
1、那么我们可以知道，如果翻转的次数小于m，无论如何都不可能使得s变为回文串，所以[0,m)位置上的值为0
2、分为n为奇数或者偶数
如果n为奇数，那么从[m,n/2]位置上的所有值都为1，因为：
(1)已知第m个位置上的值一定为1；
(2)第m+1位置上的值也一定为1，因为n是奇数，中间的那个字符是单独的，没有任何字符和它进行配对（也即无论它翻转或者不翻转，都不影响s是否为回文串）。那么可以在(1)的基础上翻转中间的这个字符，那么s仍然是回文串。
(3)m+2（注意此时的m+2需要小于n/2）呢？因为翻转m个已经是回文串了，翻转m+2个也一定是回文串，因为我们只需要在m的基础上再翻转两个相同的即可。
(4)m+3同理。
如果n是偶数，那么从[m,n/2]位置上的所有值一定是1和0交替出现的，因为我们没有像n为奇数时的中间字串（能够无论怎么翻转都不影响s是否为回文串）
3、之后我们已经得到的前n/2个值 复制给 下标为[n/2+1,n]的值即可得到最终要输出的结果数组
代码中有注释
AC代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define sf(x) scanf("%d", &x);
#define de(x) cout << x << " ";
#define Pu puts("");
const int N = 1e5 + 9;
int a[N];
char s[N];
int n, m, ans;
void solve() {
    cin >> n;
    scanf("%s", s);
    m = 0;
    for (int i = 0; i <= (n / 2) - 1; i++) {
        // 找不匹配的对数
        if (s[i] != s[n - (i + 1)])
            m++;
    }
    for (int i = 0; i < m; i++) {
        a[i] = 0;
    }  // 在没有达到m个之前，肯定不能是回文数
    if (n % 2 == 1) {
        for (int i = m; i <= (n / 2); i++) {
            a[i] = 1;  // 如果n为奇数，那么从s形成回文串时起到（n/2）
        }              // 一定都为1
    } else {
        int flag = 1;                         // 如果n为偶数，那么从s形成回文串时起到（n/2）
        for (int i = m; i <= (n / 2); i++) {  // 1和0一定交替出现
            if (flag == 1) {
                a[i] = 1;
                flag = 0;
            } else {
                a[i] = 0;
                flag = 1;
            }
        }
    }
    for (int i = (n / 2) + 1; i <= n; i++) {
        a[i] = a[n - i];  // 因为是对称，我们直接把前段的值赋值给后段
    }
    for (int i = 0; i <= n; i++) {
        printf("%d", a[i]);
    }
    Pu;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58