B3935[语言月赛202402]数字串

Mia_zxt · 2025-06-12 22:40:05 · 题解

本蒟蒻是第一次写题解，麻烦各位dalao见谅OTZ

这题难度为普及-，中心为字符串入门，没有掌握的同学可以再巩固巩固

这题给定t组数据，每组给出n, m, s三个量，分别表示序列号、字符串长度以及字符串，总结下来字符串只有三种可能

字符串只有一个数字1
字符串有多个数字1
字符串没有数字1。

我们一一来解决一下这三个问题：

[ ] 当字符串只有一个1时，应该枚举1左右两边0的个数，判断是否合规（<=n）;如下说明图：

字符串：0001000 n : 2 答案：No //将“0001000”分成a，b两部分 000 1 000

a b //统计0的个数 a = 3; b = 3; //判断是否合规 a > n && b > n //因为不合规，所以答案为： cout << "No" << endl; 代码实现如下：

bool checka(string s, int m, int n){//检查唯一一个1的左右两边是否合规
    int a = 0;
    for (int i = 0; i < m; i ++ ){
        if (s[i] == '1'){
            if (a > n) return 0;
            a = 0;
        }
        else a ++ ;
    }
    if (a > n) return 0;
    return 1;
}

[ ] 当有多个1时，需枚举每一个1到最近一个1之间0的个数，当全部相等，且左右两边小于区间内的值，则满足条件，如说明图：

字符串：0101000 n：2 答案：No //将字符串“0101000”分成a， b， c三部分 0101000

a b c //统计0的个数 a = 1 b = 1 c = 3 //判断是否合规 a <= b && b <= n && c >= b //因为不合规，所以答案为： cout << "No" << endl; 代码如下：

bool checkb(string s, int m, int n){//检查有多个1每个区间是否合规
    int  a[100010] = {0}, d = 0;
    for (int i = 0; i < m; i ++ ){
        if (s[i] == '1') d ++ ;
        else a[d] ++ ;
    }
    if (s[m - 1] == '0') d ++ ;
    for (int i = 1; i < d - 2; i ++ ){
        if (a[i] != a[i + 1]) return 0;
    }
    if (a[0] <= a[1] && a[d - 1] <= a[1] && a[1] <= n) return 1;
    return 0;
}

[ ] 当字符串中没有1时，直接判断长度是否<=n就ok了，如说明图：

字符串：00000 n：5 m：5 答案：Yes //因字符串没有1，说明全是0（很明显吧），这样就表明字符串内共有m个0，所以判断m是否<=n m <= n //所以答案为： cout << "Yes" << endl; 这段比前面都简单吧，代码如下：

bool checkc(string s, int m, int n){
    if (m <= n) return 1;
    return 0;
}

欧克，到这里思路就已经讲完了，请有动手能力的人自己重构一下代码，脑子懂了手没懂的可以继续往下看

完整代码如下：

#include <iostream>
using namespace std;
int n, m, t;
string s;
int check1(string s, int l){//检查1的个数
    int sum = 0;
    for (int i = 0; i < l; i ++ ){
        if (s[i] == '1') sum ++ ;
    }
    return sum;
}
bool checka(string s, int m, int n){//检查唯一一个1的左右两边是否合规
    int a = 0;
    for (int i = 0; i < m; i ++ ){
        if (s[i] == '1'){
            if (a > n) return 0;
            a = 0;
        }
        else a ++ ;
    }
    if (a > n) return 0;
    return 1;
}
bool checkb(string s, int m, int n){//检查有多个1每个区间是否合规
    int  a[100010] = {0}, d = 0;
    for (int i = 0; i < m; i ++ ){
        if (s[i] == '1') d ++ ;
        else a[d] ++ ;
    }
    if (s[m - 1] == '0') d ++ ;
    for (int i = 1; i < d - 2; i ++ ){
        if (a[i] != a[i + 1]) return 0;
    }
    if (a[0] <= a[1] && a[d - 1] <= a[1] && a[1] <= n) return 1;
    return 0;
}
bool checkc(string s, int m, int n){
    if (m <= n) return 1;
    return 0;
}
int main(){
    cin >> t;
    while (t -- ){
        cin >> n >> m >> s;
        if (check1(s, m) == 1){//一个1
            if (checka(s, m, n)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else if (check1(s, m) > 1){//多个1
            if (checkb(s, m, n)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else{//没有1
            if (checkc(s, m, n)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

如果还没看懂的话，可以多看几遍

各位看了蒟蒻的代码后有什么简化建议可以告诉作者，非常感谢你看到了这里，欢迎互关，我是第一次发题解，若有没读懂的，可以在评论区问，~我会尽量讲明白~

再见咯～