自动搬运

查看原文

来自洛谷，原作者为

	icypenguin **

搬运于2025-08-24 21:16:02，当前版本为作者最后更新于2024-02-20 16:55:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

视频题解