首页 > 代码库 > Problem H. The Fence

Problem H. The Fence

/**
题目:Problem H. The Fence
链接:https://vjudge.net/problem/Gym-101090H
题意:给定一个字符串,只有0或者1;
问:假如两个不同的1之间的0,1数量是k的倍数(包括0倍)则输出这两个1的位置;
思路:%k;直到遇到两个相同的余数,说明之间的01数量为k的倍数。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int vis[N];
char s[N];
int main(){
    int k;
    cin>>k;
    scanf("%s",s+1);
    int len = strlen(s + 1);
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= len;i++){
        if(s[i] == 1){
            if(vis[(i + k -1)%k]){
                    printf("%d %d\n",vis[(k - 1 + i)%k],i);
                    return 0;
            }
            vis[i%k] = i;
        }
    }
    printf("0 0\n");
    return 0;
}

 

Problem H. The Fence