首页 > 其他 > 详细

Educational Codeforces Round 81 (Rated for Div. 2)

时间:2020-02-01 17:22:13      阅读:69      评论:0      收藏:0      [点我收藏+]

B. Infinite Prefixes

题目大意:

给你一个字符串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;
}
B

 

Educational Codeforces Round 81 (Rated for Div. 2)

原文:https://www.cnblogs.com/EchoZQN/p/12248967.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!