AtCoder Beginner Contest 381 A~C

IronMen · 2025-01-10 21:59:35 · 题解

A - 11/22 String

洛谷链接

AtCoder链接

题目

本问题中 11/22 字符串的定义与问题 C 和 E 中的定义相同。

满足以下所有条件的字符串 T 称为 11/22 字符串：

从 1 到 (\frac{|T|+1}{2}-1) 的字符都是 1。
第 (\frac{|T|+1}{2}) 个字符是 /。
从 (\frac{|T|+1}{2}+1) 到 |T| 的字符都是 2。

例如，11/22、111/222 和 / 是 11/22 字符串，但 1122、1/222、11/222、22/11 和 /2/2/211 则不是。

给定长度为 N 的字符串 S 由 1、2 和 / 组成，请判断 S 是否是 11/22 字符串。

代码

#include <bits/stdc++.h>

using namespace std;

int t;
string s;

int main()
{
    scanf("%d", &t);
    cin >> s;
    if (t % 2 == 0 || s[(t + 1) / 2 - 1] != '/')
        goto it;
    for (int i = 0; i < (t + 1) / 2 - 1; i ++ )
    {
        if (s[i] != '1')
            goto  it;
    }
    for (int i = (t + 1) / 2; i < (int)s.length(); i ++ )
    {
        if (s[i] != '2')
            goto it;
    }
    puts("Yes");
    return 0;
it:
    puts("No");
    return 0;
}

B - 1122 String

洛谷链接

AtCoder链接

题目

当且仅当字符串 T 满足以下三个条件时，它才被称为 1122 字符串：

对于满足 1 \le i \le \frac{|T|}{2} 的每个整数 i，T 的第 (2i-1) 个和第 2i 个字符都相等。
每个字符在 T 中出现的次数正好是 0 或 2。也就是说，T 中包含的每个字符在 T 中恰好出现两次。

给定一个由小写英文字母组成的字符串 S，如果 S 是一个 1122 字符串，则打印 Yes，否则打印 No。

思路

只需检查给定字符串是否满足 1122 字符串的三个条件即可。

第三个条件可以以任何方式重新表述，例如，只要满足第一个和第二个条件，我们就可以使用这种重新表述的条件。这里，S_i 表示 S 的第 i 个字符。

对于 S 的每个字符 S_i，S 中恰好有两个元素与之重合。也就是说，对于介于 1 和 |S| 之间的所有整数 i，恰好有两个索引 j 与之重合。(1 \le j \le |S|) 与 S_i=S_j 重合。

原解的复杂度为 O(\lvert S \rvert+C)。这里，C 是 S 中可能使用的不同字符数；这次是 C=26。在重新表述的条件中，天真的实现可能会花费 O(\lvert S \rvert^2) 时间，但在我们的例子中是 \lvert S \rvert \le 100，这是可以接受的。因此，可以用任何方法检查该条件，问题也就迎刃而解了。

代码

#include <bits/stdc++.h>

using namespace std;

int n, cnt[26];
string s;

int main()
{
    cin >> s;
    n = s.length();
    if (s.length() % 2 == 1)
    {
        puts("No");
        return 0;
    }
    for (int i = 0; i < (n / 2); i ++ )
    {
        if (s[2 * i] != s[2 * i + 1])
        {
            puts("No");
            return 0;
        }
    }
    for (int i = 0; i < n; i ++ )
        cnt[s[i] - 'a'] ++;
    for (int i = 0; i < 26; i ++ )
    {
        if ((cnt[i] != 0) && (cnt[i] != 2))
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

C - 11/22 Substring

洛谷链接

AtCoder链接

题目

满足以下所有条件的字符串 T 称为 11/22 字符串：

从 1 到 (\frac{|T|+1}{2}-1) 的字符都是 1。
第 (\frac{|T|+1}{2}) 个字符是 /。
第 (\frac{|T|+1}{2}+1) 个到第 |T| 个字符都是 2。

例如，11/22、111/222 和 / 是 11/22 字符串，但 1122、1/222、11/222、22/11 和 /2/2/211 则不是。

给定长度为 N 的字符串 S 由 1、2 和 / 组成，其中 S 包含至少一个 /。

请找出长度为 11/22 的 S 的连续子串的最大长度。

思路

模拟。先枚举找到 /，再向两边枚举，判断此时的字串是不是 11/22 字符串。如果是，就更新答案。

代码

#include <bits/stdc++.h>

using namespace std;

int n, ans, sum;
char a[200010];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] == '/')
        {
            sum = 1;
            for (int j = i - 1, k = i + 1; j >= 1 && k <= n; j --, k ++ )
            {
                if (a[j] == '1' && a[k] == '2')
                    sum += 2;
                else
                    break;
            }
            ans = max(ans, sum);
        }
    }
    cout << ans << '\n';
    return 0;
}