題目鏈接：http://codeforces.com/contest/1295/problem/B
題目：給定由0,1組成的字串s，長度為n，定義t = sssssss.....一個無限長的字串，
題目定義一個平衡值x,取t的任意前綴Q，如果Q滿足cnt(0,q) - cnt(1,q) = x，即Q中0
的個數-1的個數= x，說明當前的Q是滿足題意得一個前綴，問滿足x的前綴有多少個，
如果x = ∞，則輸出-1.
input
6 10
010010
題目給定說q的長度為28，30，32是平衡前綴，
0100100100100100100100100100
可以看出cnt(0) = 19，cnt(1) = 9，cnt(0)-cnt(1) = 10 = x.
我們也就清楚了題目的意思，
那么我們該怎么優化呢，其實這個題目還是需要一些技巧和規律，
思路：給定了一個串s，有限串q從t中截取無非是x倍的s加上s的一種前綴，
想到這，那我們就應該成s串入手，cnt(0,q) - cnt(1,q)說明是0，1的前綴個數相差，
那么我們先把s的"cnt(0,q) - cnt(1,q)"前綴和求出來tot[1~n]，那么我們需要想，什么時候滿足-1的情況，即有無窮個平衡前綴，我們可以發現，“有限串q從t中截取無非是x倍的s加上s的一種前綴”，如果tot[n] != 0,那么關于q的"cnt(0,q) - cnt(1,q)"為 m*tot[n] + tot[now]（now是s一種前綴的最后一位），這樣不斷的積累，一定不會得出無限前綴的答案，那如果tot[0]的時候呢，我們發現關于q的"cnt(0,q) - cnt(1,q)"為 m*tot[n] + tot[now] -> m*0+tot[now]，說明q可以有不同長度的無限個tot[now]，如果tot[now] = x，那就滿足無限前綴了，
有限前綴從關于q的"cnt(0,q) - cnt(1,q)"為 m*tot[n] + tot[now]可以很好求出：
m*tot[n]+tot[now] = x，就是一種平衡前綴了，我的基本思想是這樣，別的還請思考或者參考代碼，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <string> 5 #include <cstring> 6 using namespace std; 7 8 int tot[101000]; 9 string str; 10 int l,x; 11 12 void show(){ 13 for(int i = 1;i <= l; ++i){ 14 cout << tot[i] << ' '; 15 }cout << endl; 16 } 17 18 int main(){ 19 20 21 int T; 22 cin >> T; 23 while(T--){ 24 cin >> l >> x >> str; 25 //s的"cnt(0,q) - cnt(1,q)"前綴和求出來tot[1~n] 26 for(int i = 0; i < l; ++i){ 27 if(str[i] == '0') tot[i+1] = tot[i] +1; 28 else tot[i+1] = tot[i] -1; 29 } 30 //show(); 31 int ans = 0; 32 if(x == 0) ans = 1;//這是一個細節，空串也是一種情況， 33 //那么cnt(0,q) - cnt(1,q) = 0 34 if(tot[l] == 0){ 35 for(int i = 1; i <= l; ++i){ 36 if(tot[i] == x){ 37 ans = -1; break;//無窮 38 } 39 } 40 } 41 else{ 42 int v,mod; 43 for(int i = 1; i <= l; ++i){ 44 //這里有個細節問題 可能 x-tot[i] >0 tot[l] <0， 45 //雖然可能mod = 0，可是v其實就是幾個s，mod就是s的前綴， 46 //那么v不能是負數 比如 3/-1 = -3 ...... 0 ， 47 int v = (x-tot[i])/tot[l]; //整數 48 int mod = (x-tot[i])%tot[l]; //余數 49 if(!mod && v >= 0) 50 ++ans; 51 } 52 } 53 //cout << "--------------------||||" <<ans << endl; 54 cout << ans << endl; 55 } 56 57 return 0; 58 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/96506.html
標籤：其他
下一篇：Educational Codeforces Round 81 (Rated for Div. 2) C. Obtain The String