AT_abc381_c [ABC381C] 11/22 Substring 题解

Snowflake_Fairy · 2024-11-23 10:54:43 · 题解

前言

2024/11/22 星期五是我的生日。

Atcoder 很良心地把 A\sim F 的题目全都命名为 11/22 或者 1122，详见。

时隔几个月，又一次排名接近 1000（实际排名 1006，还吃了 7 发罚时）。

题目大意

此问题中的 11/22 字符串的定义与题目 A 和 C 的定义相同。

如果字符串 T 满足以下所有条件，那么称 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/22， 11/2222， 22/11 和 //2/2/211 都不是。

给你一个长度为 N 且只包含 1， 2， / 的字符串 S。

请你找到 S 中是 11/22 字符串的 （连续的） 子串的最大长度。

解题思路

我们遍历这个字符串，只要一遇到 /，就从这个地方同时向两边搜索，直到某一边超出了这个字符串的范围或者不满足左端点为 1，右端点为 0 为止，然后更新答案。

平均时间复杂度为 \mathcal{O}(n)。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int len, ans = 0;
    string a;
    cin >> len >> a;
    a = " " + a;
    for (int i = 1; i <= a.size(); i++) {
        if (a[i] == '/') {
            int l = i - 1, r = i + 1;
            while (l > 0 && r <= a.size()) {
                if (a[l] == '1' && a[r] == '2') {
                    l--, r++;
                } else {
                    l++, r--;
                    break;
                } 
            }
            if (l == 0) {
                l++, r--;
            }
            ans = max(ans, r - l + 1);
        }
    }
    cout << ans;
    return 0;
}