AtCoder ABC418 D XNOR Operation
link
题意
给定一个长度为 \(n\) 的 01 串 \(s\)，每次可以选择相邻的两个位置。如果两个位置字符相同，把它们缩成 \(1\)，否则缩成 \(0\)。求 \(s\) 中有多少个子串经过操作可以变成 \(1\)。\(1\leq n\leq 2\times 10^5\)。
题解
动态规划。令 \(f_{i,0/1}\) 表示以 \(i\) 结尾且最终变为 \(0/1\) 的子串个数。当 \(s_i=1\) 时，显然 \(f_{i,0}=f_{i-1,0},f_{i,1}=f_{i-1,1}+1\)。当 \(s_i=0\) 则有 \(f_{i,0}=f_{i-1,1}+1,f_{i,1}=f_{i-1,0}\)。而最终答案就是 \(\sum f_{i,1}\)。复杂度 \(O(n)\)。aclink。
代码
#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)using namespace std;
const int N=2e5+5;void solve();
int n,f[N][2];
i64 ans;
char s[N];signed main(){int Test=1;
// scanf("%d",&Test);while(Test--) solve();return 0;
}void solve(){scanf("%d%s",&n,s+1);L(i,1,n,1){if(s[i]=='1'){f[i][1]=f[i-1][1]+1;f[i][0]=f[i-1][0];}else{f[i][1]=f[i-1][0];f[i][0]=f[i-1][1]+1;}ans+=f[i][1];}printf("%lld\n",ans);
}