1 条题解
-
1
#define pii pair<int, int> #define int long long void solve() { int n; cin >> n; string s; cin >> s; int need = 0; int mx = n; for(int i = 0; i < s.size() / 2; i++){ if(s[i] != s[n - i - 1]){ need++; mx--; } } string ans(n + 1, '0'); if(n&1){ for(int i = need; i <= mx; i++) ans[i] = '1'; } else{ for(int i = need; i <= mx; i+=2)ans[i] = '1'; } cout << ans << endl; }-
morgen
@ 2025-11-26 18:31:45
异或可以将每一位的 1 变成 0 (异或 1)，0 变成 1（异或 1），也可以让这位数保持不变（异或 0），也就是它可以任意改变二进制数中的任意几位数字。
因此题目可以转化为：对于一个数 i，需要计算出是否能改变二进制数 s 中的任意 i 个数字使它变为一个回文（二进制）数。
那我们先从 s 中的
1入手。如果一个二进制字符串是回文串，那么左右的1都是对称的（第 i(0≤i<n) 个1都对应第 n−i 个1），当一个二进制数前后的1不对应时，它就不是一个回文串。例如
1010001，第 2 个位置的1和第 4 个位置的0不对称。如果要将它构造成一个回文串，至少需要修改的数字的个数 sum 就是左右不对称的数对数量，因为你至少要把每一个不对称的数对的其中一个数字改成和另一边的数字相等，才能达到左右数字对称。 还拿
1010001来举例，最少应将第 4 个位置的0改为1才能使它变成一个回文数。- 对于一个偶数位的二进制数，修改完不对称的数位后，可以将其他的对称的数对都改成另一个数字，一对数中有两个数字，因此 sum+2,sum+4… 也都是答案，直到 sum 超过对称的数对中数字的总数。
- 对于一个奇数位的二进制数，因为数对可能存在只有一个数的情况，那么这也算是对称，所以可能的 sum 的开始和结束条件和偶数位的一样，但是答案是逐次加 1 的。
-
- 1