Find Q

Accepts: 392 Submissions: 780 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others) 問題描述 Byteasar迷戀上了'q'這個字母。在他眼前有一個小寫字母組成的字符串SSS，他想找出SSS的所有僅包含字母'q'的連續子串。但是這個字符串實在是太長了，你能寫個程序幫助他嗎？ 輸入描述 輸入的第一行包含一個正整數T(1≤T≤10)T(1\leq T\leq10)T(1≤T≤10)，表示測試數據的組數。 對于每組數據，包含一行一個小寫字母組成字符串SSS，保證SSS的長度不超過100000100000100000。 輸出描述 對于每組數據，輸出一行一個整數，即僅包含字母'q'的連續子串的個數。 輸入樣例 2 qoder quailtyqqq 輸出樣例 1 7

題解:尺取法直接上就好了,要注意數據范圍 long long #pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100005; char str[N]; int main() {freopen("a.txt","r",stdin);int tcase;scanf("%d",&tcase);while(tcase--){scanf("%s",str+1);int len = strlen(str+1);LL l = 1,r = 1;long long cnt = 0;while(l<=len){while(l<=len&&str[l]!='q') l++;r = l;while(r<=len&&str[r]=='q'){r++;}if(r>l){cnt+=(r-l)*(r-l+1)/2;}l = r;}printf("%lld\n",cnt);}return 0; }

Abelian Period

Accepts: 288 Submissions: 984 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others) 問題描述 設SSS是一個數字串，定義函數occ(S,x)occ(S,x)occ(S,x)表示SSS中數字xxx的出現次數。 例如：S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1。 如果對于任意的iii，都有occ(u,i)=occ(w,i)occ(u,i)=occ(w,i)occ(u,i)=occ(w,i)，那么我們認為數字串uuu和www匹配。 例如：(1,2,2,1,3)≈(1,3,2,1,2)(1,2,2,1,3)\approx(1,3,2,1,2)(1,2,2,1,3)≈(1,3,2,1,2)。 對于一個數字串SSS和一個正整數kkk，如果SSS可以分成若干個長度為kkk的連續子串，且這些子串兩兩匹配，那么我們稱kkk是串SSS的一個完全阿貝爾周期。 給定一個數字串SSS，請找出它所有的完全阿貝爾周期。 輸入描述 輸入的第一行包含一個正整數T(1≤T≤10)T(1\leq T\leq10)T(1≤T≤10)，表示測試數據的組數。 對于每組數據，第一行包含一個正整數n(n≤100000)n(n\leq 100000)n(n≤100000)，表示數字串的長度。 第二行包含nnn個正整數S1,S2,S3,...,Sn(1≤Si≤n)S_1,S_2,S_3,...,S_n(1\leq S_i\leq n)S?1??,S?2??,S?3??,...,S?n??(1≤S?i??≤n)，表示這個數字串。 輸出描述 對于每組數據，輸出一行若干個整數，從小到大輸出所有合法的kkk。 輸入樣例 2 6 5 4 4 4 5 4 8 6 5 6 5 6 5 5 6 輸出樣例 3 6 2 4 8

題解:保存異或前綴異或和 ,k一定是 n的因子,所以枚舉的 k不會很多.然后每隔k個比一下當前的異或和和前面異或和的異或值是否為0的就行了. #pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100005; LL a[N],sum[N]; int factor[N],ans[N]; int main() {int tcase;scanf("%d",&tcase);while(tcase--){int n;scanf("%d",&n);memset(sum,0,sizeof(sum));for(int i=1; i<=n; i++){scanf("%I64d",&a[i]);sum[i] = sum[i-1]^a[i];}int id = 0,m = n;factor[id++] = 1;for(int i=2; i*i<=n; i++){if(n%i==0){if(i*i==n) factor[id++] = i;else{factor[id++] = n/i;factor[id++] = i;}}}factor[id++] = n;sort(factor,factor+id);int cnt = 0;bool flag = false;for(int j=0; j<id; j++){bool flag = false;int k = factor[j];for(int i=2*k; i<=n; i+=k){LL pre = sum[i]^sum[i-k],nxt;if(i>=2*k) nxt = sum[i-k]^sum[i-2*k];else nxt = sum[i-k];if((pre^nxt)!=0) {flag = true;break;}}if(!flag) ans[cnt++] = k;}flag = true;for(int i=0;i<cnt;i++){if(!flag) printf(" %d",ans[i]);else printf("%d",ans[i]);flag = false;}printf("\n");}return 0; }

?

轉載于:https://www.cnblogs.com/liyinggang/p/5926459.html

總結

以上是生活随笔為你收集整理的BestCoder #88(1001 1002)的全部內容，希望文章能夠幫你解決所遇到的問題。

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