这道题的意思是给你一个01串， 定义这串的优美值为连续相同的数字的平方和， 现在可以改变这些串中一个字符， 问你优美值最大是多少？ 我们可以预处理出d1[i]i左边和str[i]相同的字符个数， d2[i]i右边和str[i]相同的字符个数， 对于一个i， 我们可以进行如下分类， i周围的两个元素和i都不相同， 有一个相同， 两个都相同， 按照这个规律扫一遍即可得出答案， 代码如下：
#include <bits/stdc++.h>using namespace std; typedef long long LL; char str[100000 + 100]; int d1[100000+100], d2[100000 + 100];LL n2(LL a) {return a*a; }int main() {int T;scanf("%d", &T);int kase = 0;while(T--){scanf("%s", str+1);int len = strlen(str+1);memset(d1, 0, sizeof(d1));memset(d2, 0, sizeof(d2));LL res = 0;for(int i=1; i<=len; i++){if(i>1 && str[i]!=str[i-1]){res += (LL)d1[i-1]*(LL)d1[i-1];d1[i] = 1;}else d1[i] = d1[i-1]+1;}res += (LL)d1[len]*(LL)d1[len];for(int i=len; i>=1; i--){if(i<len && str[i]!=str[i+1])d2[i] = 1;else d2[i] = d2[i+1] + 1;}LL ans;LL ansres = res;str[0]='3', str[len+1]='3';for(int i=1; i<=len; i++){if(str[i]==str[i+1] && str[i]==str[i-1]){ans = res-n2(d1[i]+d2[i]-1)+n2(d1[i]-1)+n2(d2[i]-1)+1;ansres = max(ansres, ans);}if(str[i]==str[i+1] && str[i]!=str[i-1]){ans = res-n2(d2[i])-n2(d1[i-1])+n2(d1[i-1]+1)+n2(d2[i]-1);ansres = max(ansres, ans);}if(str[i]!=str[i+1] && str[i]==str[i-1]){ans = res-n2(d1[i])-n2(d2[i+1])+n2(d1[i]-1)+n2(d2[i+1]+1);ansres = max(ansres, ans);}if(str[i]!=str[i-1] && str[i]!=str[i+1]){ans = res-n2(d1[i-1])-n2(d2[i+1])-1+n2(d1[i-1]+d2[i+1]+1);ansres = max(ansres, ans);}}printf("Case #%d: %lld\n", ++kase, ansres);}return 0; }
