B3935 [语言月赛 202402] 数字串 题解

· · 题解

Source & Knowledge

2024 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

出题人题解。

题目大意

给定一个串，还有 n + 1 个可供匹配的串，第 i(0 \leq i \leq n) 个串是一个 1 和 i 个 0 无限交替构成的，问这个串能否匹配上至少其中的一个可供匹配的串。

题目分析

本题考查对字符串、数组、循环结构的运用。

首先我们通过阅读 n 个字符的方式读入这个串，并把其存在数组中，并将字符 0 转换为数字 0，字符 1 转换为数字 1。

仔细观察题面发现，该问题就是判断这个串相邻 1 之间的距离是否全部相同，并且相邻 1 之间的距离不超过 n。如果相邻 1 之间的距离超过了 n，直接输出 No，进入下一次询问。其他情况，若这个串没有 1，则判断它的长度是否大于 n，如果大于 n，则输出 No，如果小于等于 n，则输出 Yes。当这个串有 1 个 1 的时候，这个串的前缀 0 不超过 n，并且这个串的后缀 0 的数量不超过 n，则是合法的，输出 Yes，否则输出 No。当这个串有大于等于 2 个 1 的时候，这个串的前缀 0 的数量不超过相邻 1 之间的间隔，并且这个串的后缀 0 的数量不超过相邻 1 之间的间隔，则是合法的，输出 Yes，否则输出 No。

用分支结构实现这些判断即可。

cin >> t;
while (t--){
    long long n, m;
    cin >> n >> m;
    ll cnt = 0;
    for (long long i = 1; i <= m; i++){
        char c;
        cin >> c;
        a[i] = c - '0';
        if (a[i] == 1){
            w[++cnt] = i;
        }
    }
    if (cnt == 0){
        if (m > n){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
        continue;
    }
    if (cnt == 1){
        if (w[1] - 1 > n || (m - w[1] > n)){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
        continue;
    }
    ll len = w[2] - w[1] - 1;
    if (len > n){
        cout << "No" << endl;
        continue;
    }
    if (w[1] - 1 > len){
        cout << "No" << endl;
        continue;
    }
    bool flg = true;
    for (long long i = 3; i <= cnt; i++){
        if (w[i] - w[i - 1] - 1 != len){
            cout << "No" << endl;
            flg = false;
            break;
        }
    }
    if (!flg){
        continue;
    }
    if (m - w[cnt] > len){
        cout << "No" << endl;
        continue;
    }
    if (flg){
        cout << "Yes" << endl;
    }
}

视频题解