B3935[语言月赛202402]数字串

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

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

这题给定

t

组数据，每组给出

n, m, s

三个量，分别表示序列号、字符串长度以及字符串，总结下来字符串只有三种可能

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

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

当字符串只有一个1时，应该枚举1左右两边0的个数，判断是否合规（

<=n

）;如下说明图：

CPP

字符串：0001000
n : 2
答案：No
//将“0001000”分成a，b两部分
000 1 000
---   ---
 a     b
//统计0的个数
a = 3;
b = 3;
//判断是否合规
a > n && b > n
//因为不合规，所以答案为：
cout << "No" << endl;

代码实现如下：

CPP

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的个数，当全部相等，且左右两边小于区间内的值，则满足条件，如说明图：

CPP

字符串：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;

代码如下：

CPP

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了，如说明图：

CPP

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

这段比前面都简单吧，代码如下：

CPP

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

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

完整代码如下：

CPP

#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;
        }
    }
}

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

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

再见咯～

B3935[语言月赛202402]数字串

文章操作

相关推荐

评论

B3935[语言月赛202402]数字串