正題

題目鏈接:https://jzoj.net/senior/#main/show/3798

---

題目大意

長度為$n$的字符串，求有多少個子串中$ABC$數量相等。

---

解題思路

方法好像很巧妙，用$S_{i,A/B/C}$表示到第$i$個時$A/B/C$的數量。

然后$$S_{r,A}?S_{l,A}=S_{r,B}?S_{l,B}=S_{r,C}?S_{l,C}$$
$$S_{r,A}?S_{l,A}=S_{r,B}?S_{l,B},S_{r,A}?S_{l,A}=S_{r,C}?S_{l,C}$$
$$?$$
$$S_{r,A}?S_{r,B}=S_{l,A}?S_{l,B},S_{r,A}?S_{r,C}=S_{l,A}?S_{l,C}$$
定義$cn{t}_i=(S_{r,A}?S_{r,B})?N+(S_{r,A}?S_{r,C})$然后看有多少個相同的就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10; long long n,sum[N][3],cnt[N],ans; char s[N]; int main() {scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++){sum[i][0]=sum[i-1][0];sum[i][1]=sum[i-1][1];sum[i][2]=sum[i-1][2];if(s[i]<='C')sum[i][s[i]-'A']++;cnt[i]=(sum[i][2]-sum[i][1])*N+sum[i][1]-sum[i][0];}sort(cnt,cnt+1+n);for(int i=0,j=0;j+1<=n;i=++j){while(j<n&&cnt[i]==cnt[j+1]) j++;ans+=1ll*(j-i+1)*(j-i)/2ll;}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj3798-[NOIP2014模拟8.22]临洮巨人【前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。