1001: 字符串“水”題

時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB
提交:?210??解決:?39
[提交][狀態(tài)][討論版]

題目描述

給出一個(gè)長(zhǎng)度為 n 的字符串(1<=n<=100000)，求有多少個(gè)連續(xù)字串中所有的字母都出現(xiàn)了偶數(shù)次。?

輸入

第一行一個(gè)正整數(shù) T，表示數(shù)據(jù)組數(shù)(1 <= T <= 10)。?
接下來 T 行，每行有一個(gè)只包含小寫字母的字符串。?

輸出

每個(gè)答案輸出滿足要求字符串個(gè)數(shù)。每個(gè)答案占一行。

樣例輸入

3 a aabbcc abcabc

樣例輸出

0 6 1

提示

?

?

這道題挺不錯(cuò)的，

用二進(jìn)制的低0-25位分別保存'a'-'z'出現(xiàn)的次數(shù)，然后根據(jù)相同狀態(tài)統(tǒng)計(jì)，

見代碼，

1 #include <bits/stdc++.h> 2 using namespace std; 3 map<int,int>mmap; 4 char str[100010]; 5 int main () 6 { 7 int T; 8 scanf("%d",&T); 9 while(T--) { 10 mmap.clear(); 11 scanf("%s",str); 12 int len = strlen(str); 13 int state=0; 14 long long sum=0; 15 for(int i=0; i<len; i++) { 16 state^=(1<<(str[i]-'a')); 17 if(state==0) { 18 sum++; 19 } 20 sum+=mmap[state]; 21 mmap[state]++;//相同狀態(tài)出現(xiàn)次數(shù) 22 } 23 printf("%lld\n",sum); 24 } 25 return 0; 26 }

?

后來可能數(shù)據(jù)加強(qiáng)了，上面代碼超時(shí)了。

優(yōu)化一下，先哈希然后存map，

1 #include <bits/stdc++.h> 2 #define maxn 34567 3 4 using namespace std; 5 typedef long long LL; 6 7 char str[110000]; 8 map<int,int>sk[maxn]; 9 void solve() 10 { 11 for(int i=0;i<maxn;i++) 12 sk[i].clear(); 13 int len=strlen(str); 14 int ret=0; 15 LL ans=0; 16 sk[0][0]=1; 17 for(int i=0; i<len; i++) 18 { 19 int now=str[i]-'a'; 20 ret^=(1<<now); 21 ans+=sk[ret%maxn][ret]; 22 sk[ret%maxn][ret]++; 23 } 24 printf("%lld\n",ans); 25 } 26 27 int main() 28 { 29 int T; 30 scanf("%d%*c",&T); 31 while(T--) 32 { 33 scanf("%s",str); 34 solve(); 35 } 36 return 0; 37 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/bofengyu/p/6790545.html

總結(jié)

以上是生活随笔為你收集整理的1001 字符串“水”题（二进制，map，哈希）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。