题目大意:
给你一个字符串s,s是一个01串,则t=ssss... 即为s的无限循环。
问在无限长的字符串t中,有多少个前缀满足 : 0的个数 - 1的个数==x (x给出)
思路:
这个题目我开始以为是一个模拟题,这个就让我的方向上出现了很大的错误,
我认为是模拟题,所以我想办法去模拟这个无限长的串,但没写出来。
后来查了题解才发现是一个数学题。
设bal(i) 表示前缀长度为 i 的0的个数 - 1的个数的值。
对于研究有限长的 s 串,可以发现有两种情况。
第一种就是 bal(n) == 0,也就是说s串0和1的个数相同,这个时候就判断一下是不是存在bal(i)==x
如果存在,那么就输出 -1
第二种情况是 bal(i)!=0 这个时候就是解一个方程 x==k*bal(n)+bal(i)
从头往后遍历 判断对于每一个bal(i) 是否存在一个非负数 x==k*bal(n)+bal(i)
为什么说只要遍历s串就可以了呢,t串可是包含了无数个s串的。
这个很简单,因为s串之后都只是s串的简单的重复,这个说明bal(i)可以拆成 bal(i-n)+bal(n)
只需要算s串即可,否则就会算重复了。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; char s[maxn]; int main(){ int t; scanf("%d",&t); while(t--){ int n,x; scanf("%d%d%s",&n,&x,s); int sum=0; for(int i=0;i<n;i++) { if(s[i]==‘0‘) sum++; else sum--; } int flag=0,ans=0,cur=0; for(int i=0;i<n;i++){ if(sum==0){ if(cur==x) flag=1; } else if(abs(x-cur)%sum==0){ if((x-cur)/sum>=0) ans++; } if(s[i]==‘0‘) cur++; else cur--; } if(flag) ans=-1; printf("%d\n",ans); } return 0; }
Educational Codeforces Round 81 (Rated for Div. 2)
原文:https://www.cnblogs.com/EchoZQN/p/12248967.html