Codeforces 451D Count Good Substring 规律+DP

题意:当融合s中连续相同字符后,s'为回文 则s合法 例如"aabba" 融合后 "aba" 给出string s,只包含字符a,b,|s|<=1e5,问s有多少个长度为偶/奇数的合法子串? 方法1: 设dp[i][0/1] 以i结尾,长度为偶/奇数的合法子串个数. 明显s[i]=s[i-1]时, dp[i][0]=dp[i-1][1] 因为只有'a','b'两种字符 最后a结尾的回文肯定为 a,aba,ababa,abababa  当s[i]!=s[i-1]时 形式为XXXba 找到'a'字符前一个'a'出现位置 pre[i]结尾有多少个回文,i也有多少个(i能和其融合变回文)

则dp[i][0]+=dp[pre[i]][(i-pre[i])%2?1:0]

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const ll mod=1e9+7; ll n,m,pre[N]; ll dp[N][2]; string s; int main() { cin.tie(0); ios::sync_with_stdio(false); while(cin>>s) { ll pa=-1,pb=-1; memset(dp,0,sizeof(dp)); for(int i=0;s[i];i++) { if(s[i]=='a') pre[i]=pa,pa=i; else pre[i]=pb,pb=i; } for(int i=0;s[i];i++) { dp[i][1]=1; if(pre[i]==-1) continue; int len=i-pre[i]; dp[i][0]+=dp[pre[i]][len%2?1:0]; dp[i][1]+=dp[pre[i]][len%2?0:1]; } ll odd=0,even=0; for(int i=0;s[i];i++) odd+=dp[i][1],even+=dp[i][0]; cout<<even<<' '<<odd<<endl; } return 0; } 方法2:只要头尾两个下标对应字符相等,融合后的string 肯定为回文 i.e:a..b 中间任意,融合后只能为bab -> ababa  若当前结尾下标为奇数,前面偶数位置有多少个,(odd-even+1)长度为偶数的就有多少个,其余情况类似..

#include <bits/stdc++.h> using namespace std; typedef long long ll; const double eps=1e-10; const int inf=0x3f3f3f3f; const int N=2e5+20; char s[N]; int main() { while(scanf("%s",s+1)!=EOF) { ll pa=0,pb=0,qa=0,qb=0; ll odd=0,even=0; for(int i=1;s[i];i++) { if(i%2) { if(s[i]=='a') pa++,even+=qa,odd+=pa; else pb++,even+=qb,odd+=pb; } else { if(s[i]=='a') qa++,even+=pa,odd+=qa; else qb++,even+=pb,odd+=qb; //cout<<qb<<' '<<endl; } } cout<<even<<' '<<odd<<endl; } return 0; }