解题思路:
假设输入字符串为 S
① 题目关键点在于 s′ = s ⊕ rev(s) 可以字符串 s 进行一次该公式反转，然后再前后拼接 01 ，生成目标字符串 S
那么该公式反转到底有什么用呢？根据异或定义，两个位不相同返回1，相同返回0，假设 n 为字符串s的长度
当 s'[i] = 1 时，s与rev(s)对应的位不相同，即 s[i] != s[n-i-1]
当 s'[i] = 0 时，s与rev(s)对应的位相同， 即 s[i] == s[n-i-1]
==> 根据上述情况，可以得到另一个结论
当 s[i] != s[n-i-1] 时 s'[i] = 1，s'[n-i-1] = 1
当 s[i] == s[n-i-1] 时 s'[i] = 0，s'[n-i-1] = 0
因此可以发现 s' 必为一个回文字符串
特殊情况，当 s' 长度为奇数时，s 长度也为奇数，s 和 rev(s) 最中间的值必定相同，所以 s' 最中间的值肯定为 0
② 通过①得到 s' 必为一个回文字符串又有何用呢？举个例子，假如 s' = 1111：
那么原s可以为 1010 0101 1100 0011，可以发现无论哪种情况 1 的个数都变成了二分之一
因此通过 s′ = s ⊕ rev(s) 公式转换，可以使需要1的个数减少二分之一
③ 根据①、②结论，题目可以转化为在 S 中找到一个 回文子字符串，且该回文子字符串中含有 1 的个数最多。
可以根据中心扩展方法，枚举S中所有位，以该位为中心，左右扩展得到该位得最长 回文字符串
当然普通得中心扩展方法肯定达不到100%ac，因为时间复杂度为 O(n2)，因此需要马拉车算法（Manacher）, 这是一个经典算法，时间复杂度为O(n)，这里就不详细赘述了，找相关视频讲解更加直观，自行百度了解。
参考代码:
#include <bits/stdc++.h> using namespace std; int main() { // # 马拉车算法 // # 字符串扩展，每个字母间插入'0'，解决奇偶长度回文问题 // s = '0' + '0'.join(list(s)) + '0'
vector<char> s; char w; while ((w = getchar())!=EOF) { s.push_back('0'); s.push_back(w); } s.push_back('0');
int l = 0,r = 0; int n = s.size();
// # 每个字母的臂长 vector<int> m(n,0);
// # 初始化，第0个字母臂长肯定是0，即自己 // # m[0] = 0
// ''' // ddabacabac // l ir // 2345678 // m[li] = 1 // '''
// 前缀和优化 vector<int> pre(n+1,0); if (s[0] == '1') { pre[1] = 1; }
int li; for (int i = 1;i < n;i++) { if (s[i] == '1') { pre[i+1] = pre[i] + 1; } else { pre[i+1] = pre[i]; }
// # 在臂长范围中 if (i < r) { // # 镜像i位置 li = l - (i - l); // # 根据回文对称性，获取已知最短臂长 m[i] = min(r-i,m[li]); }
// # 暴力扩展 while (i+m[i]+1 < n and i-m[i]-1 >= 0 and s[i+m[i]+1] == s[i-m[i]-1]) { m[i] += 1; }
// # lr-box更新 if (i + m[i] > r) { l = i; r = i + m[i]; } }
int res = pre[n];
for (int i=0;i<n;i++) { // # 奇数回文中点不能为 1 if (s[i] == '1') continue;
l = i - m[i]; r = i + m[i];
// [0,l) + [l,r] / 2 + [r+1,n] // [l,r] 为回文子字符串，因此 1 个数减半 res = min(res,pre[l] + (pre[r+1] - pre[l]) / 2 + pre[n] - pre[r+1]); }
cout << res;
} |
0.0分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复