2024 年第十五届蓝桥杯 C/C++ B组国赛题解

前言

一直在想是否要写这篇题解，但最后还是打算整理帮助有需要的人，因为到现在没看到有人正经写过一篇题解。 这篇题解包含标准答案，最后几题同样给出暴力做法。 另外这些是赛后回顾代码，可能存在赛时代码正确，此处代码存在瑕疵的问题。关于解释有问题的欢迎喷。

实测最后三题都只拿暴力分的话 国一 是稳稳前排；身边数据，约莫再丢一整题分（20），大概 国一 后排。身边有不少有水平的选手，但是先天对 OI 赛制不适没能拿到好成绩，当然真有水平的选手也不会在意这点得失；另外就是太追逐正解，导致该拿到的分没有拿到，拿我个人举例，这是我第二次参加蓝桥杯，去年因为太较真拿了国二。这次本来没有打算较真附上正解，但最后想着想着就都写了正解，希望对你有帮助。

A 题：合法密码

枚举 check 一下就好，个人认为答案应该是 400，不少人答案是 618 还是对题意理解不一样。我觉得 618 的题意理解也算合理的。

// A: 合法密码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

bool check(const string &s, int l, int r) {
    if (r - l + 1 < 8 or 16 < r - l + 1)
        return false;
    bool has_digit = false, has_character = false;
    for (int i = l; i <= r; i++) {
        if ('0' <= s[i] and s[i] <= '9') {
            has_digit = true;
        } else if ('A' <= s[i] and s[i] <= 'Z' or 'a' <= s[i] and s[i] <= 'z') {
            ;  // has_character = true;  // 这种做法算出来会是 618
        } else {
            has_character = true;
        }
    }
    return has_digit and has_character;
}

void solve() {
    string s = "kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";
    const int n = s.size();

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (check(s, i, j))
                cnt++;
    cout << cnt << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

B 题：选数概率

这应该算是一个简单数学题吧，$P=\frac{2ab}{(a+b+c)(a+b+c-1)}$。令 $S=a+b+c$，可以发现 $S(S-1)$ 这样的分母并不多。找到一个这样的 $S$ 然后枚举一下 $a,b,c$ 即可，如果对于这个 $S$ 找不到一个解，那就尝试更大的 $S$。事实上第一个 $S$ 就是有解。

答案是 55,94,56。不用代码直接手算也可以做。

// B: 选数概率
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
    const int f1 = 2585, f2 = 2632, f3 = 1540, m = 10455;
    // p12=f1/m, p23=f2/m, p13=f3/m
    int s = 1;
    while (true) {
        s++;
        if (s * (s - 1) % m)
            continue;
        const int k = s * (s - 1) / m;
        for (int a = 1; a < s; a++) {
            for (int b = 1; b < s - a; b++) {
                int c = s - a - b;
                if (2 * a * b == f1 * k and 2 * b * c == f2 * k and 2 * a * c == f3 * k) {
                    cout << a << ',' << b << ',' << c << endl;
                    return;
                }
            }
        }
    }
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

C 题：蚂蚁开会

记录所有直线经过的整点，放到 map 里，然后你会发现所有出现大于等于 2 次的都是计数点。

时间复杂度 $O(nA\log_2nA)$，map 带个 log。时间卡的说实话有点紧，毕竟 $nA$ 有 5e6，但实在想不到更好的解法，应该是正解了。emmm… 我不确定但好像空间也有点紧张。

用 unordered_map 或者离线 (基数) 排序会快些，如果愿意写后者完全不用担心时空。

// C: 蚂蚁开会
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
    map<pair<int, int>, int> M;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y, xx, yy;
        cin >> x >> y >> xx >> yy;
        const int g = __gcd(abs(xx - x), abs(yy - y));
        const int a = (xx - x) / g, b = (yy - y) / g;
        int nx = x, ny = y;
        while (nx != xx or ny != yy) {
            M[{nx, ny}]++;
            nx += a;
            ny += b;
        }
        M[{nx, ny}]++;
    }
    int cnt = 0;
    for (const auto &p : M)
        if (p.second >= 2)
            cnt++;
    cout << cnt << endl;
}

signed main() {
#ifdef LOCAL
    cout << "LOCAL" << endl;
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

D 题：立定跳远

可以发现答案满足单调性，意思是如果 $A$ 是可行解，则所有大于等于 $A$ 的值都是可行解。

因此可以二分答案，假设一个解 $x$，然后 $O(n)$ 检测其是否可行。总时间复杂度 $O(n\log_2A)$。

这里需要注意一些细节，毕竟是 OI 赛制嘛：

• 第 15 行中每个加一减一想清楚是否需要。
• 第 15 行要与 0 取 max，想清楚题意 $a_i \ge a_{i-1}$。
• 第 27 行 $l$ 和 $r$ 的边界，$r$ 大多了没事。因为 $a_i>0$，$l$ 最小取 1 即可，取 0 要小心除零错误。

// D: 立定跳远
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

int n, m;
int a[MAX];

bool check(int x) {
    int cnt = 0, pre = 0;
    for (int i = 0; i < n; i++) {
        cnt += max<int>((a[i] - pre + x - 1) / x - 1, 0);
        pre = a[i];
    }
    return cnt <= m + 1;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int l = 1, r = 1e8;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

E 题：最小字符串

贪心，双指针。让第二个字符串 $t$ 中的每个字符出现在第一个严格大于它的 $s$ 的字符前即可。然后可以发现对 $t$ 进行排序后可以用双指针线性的解决这个问题。

这里需要注意的是必须要严格大于，即 $t[j] < s[i]$，感谢🙏一位知友提出的问题。

不多说直接看代码吧。时间复杂度 $O(n+m\log_2m)$。

// E: 最小字符串
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    sort(t.begin(), t.end());

    int i = 0, j = 0;
    string res;
    while (i < n or j < m) {
        if (j == m or i < n and s[i] <= t[j]) {  // s[i] < t[j] 是错误的
            res += s[i++];
        } else {
            res += t[j++];
        }
    }

    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

F 题：数位翻转

稍微需要多想一下，不知道你有没有看出来是动态规划。贪心什么都是有问题的，就不列举了。

设置 $dp$ 数组 $dp[i][j][0/1]$。其中 $dp[i][j][0]$ 表示第 $i$ 位不翻转时，恰好前 $i$ 位共有 $j$ 位翻转的最优情况；响应的 $dp[i][j][1]$ 表示翻转。想清楚为什么这么设置 $dp$ 数组后状态转移是水到渠成的：

$$\begin{array}{ll} dp[i][j][0] = \max\left\{\begin{array}{l} dp[i-1][j][0], \\ dp[i-1][j][1] \end{array}\right. & + a[i], \\ dp[i][j][1] = \max\left\{\begin{array}{l} dp[i-1][j-1][0], \\ dp[i][j][1] \end{array}\right. & + f[i] \\ \end{array}$$

时间复杂度 $O(n^2+n\log_2A)$ 或 $O(n^2\log_2A)$。

// F: 数位翻转
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 1e3+5;
const int INF = 0x3f3f3f3f3f3f3f3fll;

int f(int x) {
    int res = 0;
    while (x) {
        res = res << 1 | x & 1;
        x >>= 1;
    }
    return res;
}

int a[MAX];
int dp[MAX][MAX][2];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int j = 0; j <= m; j++) {
        dp[0][j][0] = -INF - 1;
        dp[0][j][1] = -INF - 1;
    }
    dp[0][0][0] = 0;

    for (int i = 1; i <= n; i++) {
        const int ff = f(a[i]);
        dp[i][0][0] = dp[i - 1][0][0] + a[i];
        dp[i][0][1] = -INF - 1;
        for (int j = 1; j <= m; j++) {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i];
            dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + ff;
        }
    }

    int res = 0;
    for (int j = 0; j <= m; j++) {
        res = max(res, max(dp[n][j][0], dp[n][j][1]));
    }
    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

G 题：数星星

有多少人不会求逆元？

在一棵树上数有多少个星星结构，且这个星星节点数属于 $[L,~R]$ ？设节点 $x$ 的度为 $deg(x)$，则以这个点为中心的有效星星为 $\sum_{i=L-1}^{R-1}\binom{deg(x)}{i}$（括号表示组合数），所以总数是：

$$\sum_{x=1}^{n}\sum_{i=L-1}^{R-1}\binom{deg(x)}{i} \pmod{1e9+7}$$

比上一题简单吧，但是组合数怎么求？这不是板子嘛，没学过逆元那没办法。

时间复杂度 $O(n\log_2n)$，使用线性递推求逆元可以做到 $O(n)$。因为 $\sum_{x=1}^{n}{deg(x)}=2n-2$，求和次数是 $O(n)$ 的。

// 数星星
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;
const int MOD = 1e9+7;

inline int quick_pow(int b, int e) {
    int res = 1;
    while (e) {
        if (e & 1)
            res = res * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return res;
}
inline int inv(int x) { return quick_pow(x, MOD - 2); }

int fac[MAX];
int inf[MAX];
void load_C(int n) {
    fac[0] = 1;
    inf[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inf[i] = inf[i - 1] * inv(i) % MOD;
    }
}
inline int C(int n, int m) {
    if (m < 0 or m > n)
        return 0;
    return fac[n] * inf[m] % MOD * inf[n - m] % MOD;
}

int deg[MAX];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    int l, r;
    cin >> l >> r;
    l--, r--;
    
    int res = 0;
    for (int x = 1; x <= n; x++) {
        for (int i = l; i <= r; i++) {
            res += C(deg[x], i);
        }
    }
    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    load_C(MAX - 1);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

H 题：套手镯

赛时暴力解法：

$O(n^3)$ 的解法都能写吧，这道题占 $50\%$ 的分数很划得来。

首先可以将所有手镯看成正方形，这是等价的。然后可以确定套圈的一个角一定可以属于所有正方形的边的交点，这样的交点的数量是 $n^2$ 个，然后对每个可能的情况 $O(n)$ check。

// H: 套手镯
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 1e3+5;

int n, w, h;
struct Circle {
    int x, y, r;
} c[MAX];

int work() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cnt = 0;
            int sx = c[i].x - c[i].r, sy = c[j].y - c[j].r;
            int ex = sx + w, ey = sy + h;
            for (int k = 0; k < n; k++) {
                if (sx <= c[k].x - c[k].r and c[k].x + c[k].r <= ex and sy <= c[k].y - c[k].r and c[k].y + c[k].r <= ey) {
                    cnt++;
                }
            }
            res = max(res, cnt);
        }
    }
    return res;
}

void solve() {
    cin >> n >> w >> h;
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
    }

    int res = work();
    swap(w, h);
    res = max(res, work());

    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

赛后解法：

首先我们可以将数据离散化处理。然后对于 $x$ 轴使用双指针维护在区间 $[l,~r]$ 内 $x$ 坐标合法索引，使用 $vis$ 数组标记，注意这时候只保证区间 $x$ 的最大最小值差（极差） 小于等于 $w$，但并未保证任何 $y$。对于上面的每个状态，再次使用双指针 $[l',~r']$ 维护在 $y$ 坐标上的合法索引，只是此时忽略无 vis 标记的索引，因此此时区间维护的合法索引同时满足 $x$ 和 $y$ 的约束，此时得到的就是一种情况的计数，求它们的最大值即可。

在下面的代码中，第一维的处理为 workX 函数，第二维的处理为 workY 函数。可以看到 workX 调用 workY，workY 的区别只是多了一个 vis 的判定。总时间复杂度 $O(n^2)$。

// H: 套手镯
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e3+5;

int n, w, h;
struct Circle {
    int x, y, r;
} c[MAX];

pair<int, int> Mx[MAX];  // {value, index}
int cntMx = 0;
pair<int, int> My[MAX];  // {value, index}
int cntMy = 0;

int res = 0;
bool vis[MAX];

void workY() {
    int cnt = 0;
    int r = 0, ri = My[r].second;
    for (int l = 0; l < cntMy; l++) {
        if (l == 0 or My[l - 1].first < My[l].first) {
            while (r < cntMy and My[r].first <= My[l].first + h) {
                if (vis[ri] and My[r].first > c[ri].y and My[l].first <= c[ri].y - c[ri].r and c[ri].y + c[ri].r <= My[l].first + h) {
                    cnt++;
                }
                r++, ri = My[r].second;
            }
            res = max(res, cnt);
        }
        int li = My[l].second;
        if (vis[li] and My[l].first < c[li].y and My[l].first <= c[li].y - c[li].r and c[li].y + c[li].r <= My[l].first + h) {
            cnt--;
        }
    }
}

void workX() {
    int r = 0, ri = Mx[r].second;
    for (int l = 0; l < cntMx; l++) {
        if (l == 0 or Mx[l - 1].first < Mx[l].first) {
            while (r < cntMx and Mx[r].first <= Mx[l].first + w) {
                if (Mx[r].first > c[ri].x and Mx[l].first <= c[ri].x - c[ri].r and c[ri].x + c[ri].r <= Mx[l].first + w) {
                    vis[ri] = true;
                }
                r++, ri = Mx[r].second;
            }
            workY();
        }
        int li = Mx[l].second;
        if (Mx[l].first < c[li].x and Mx[l].first <= c[li].x - c[li].r and c[li].x + c[li].r <= Mx[l].first + w) {
            vis[li] = false;
        }
    }
}

void solve() {
    cin >> n >> w >> h;
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
        Mx[cntMx++] = {c[i].x - c[i].r, i};
        Mx[cntMx++] = {c[i].x + c[i].r, i};
        My[cntMy++] = {c[i].y - c[i].r, i};
        My[cntMy++] = {c[i].y + c[i].r, i};
    }
    sort(Mx, Mx + cntMx);
    sort(My, My + cntMy);

    workX();
    swap(w, h);
    workX();

    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

I 题：跳石头

玄学剪枝：

大致思路就是玄学剪枝骗分，实在想不到什么靠谱的做法。

我的做法就是对每个可能为答案的点做搜索做完，那每个点搜索的复杂度是 $O(n)$，当然去掉搜索重复点不然就 $O(2^n)$ 了。然后发现被搜索到的点不用再搜索了，例如从 $1$ 开始搜到了 $1,2,4,7,8$ 那这些点都不用再搜了，随机条件下可以过滤掉大量点。室友还帮忙测了如果数据是在 $c_i \le 4e4$ 随机的，跑得飞快；如果数据实在 $c_i \le 100$ 这样的小数值随机的，大概本地 $6s$。

// I: 跳石头
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 4e4+5;

int c[MAX];
bool vis[MAX];
int col[MAX];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) 
            continue;
        vis[i] = true;
        set<int> S;
        queue<int> que;
        que.push(i);
        while (not que.empty()) {
            int x = que.front();
            que.pop();
            if (col[x] == i) 
                continue;
            col[x] = i;
            S.insert(c[x]);
            if (x * 2 <= n) 
                que.push(x * 2);
            if (x + c[x] <= n) 
                que.push(x + c[x]);
        }
        res = max<int>(res, S.size());
    }

    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

应该是正解：

好像一个 bitset 就搞定了，刚开始看人说 bitset 还没意识过来… 仔细算了下内存，bitset 可以把所有状态存下，大概 $200MB$。也不用暴搜剪枝什么奇技淫巧，大概后面脑子都糊了。

时间复杂度：$O(\frac{n^2}{64})$，空间复杂度：$O(\frac{n^2}{8})$。

// I: 跳石头
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 4e4+5;

int c[MAX];
bitset<MAX> bits[MAX];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    int res = 0;
    for (int i = n; i >= 1; i--) {
        bits[i][c[i]] = 1;
        if (i * 2 <= n) 
            bits[i] |= bits[i * 2];
        if (i + c[i] <= n) 
            bits[i] |= bits[i + c[i]];
        res = max<int>(res, bits[i].count());
    }
    
    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

J 题：最长回文前后缀

贪心然后二分哈希。

先贪心的掐头去尾，把能匹配的匹配上了；然后读剩余的串再枚举掐掉多少的头（或者尾），对剩余部分二分哈希找到最长回文。

时间复杂度：$O(n\log_2n)$。感觉有希望线性解法，但是本人水平有限。

关于暴力做法就把二分哈希替换为顺序比较即可。事实上因为我哈希经常默错而且一对神秘数字的哈希不好调，赛时时间不太够就直接暴力了。反正无所谓了，前面感觉都挺稳的就随心骗了。

// J: 最长回文前后缀
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 5e5+5;
const int H1 = 131, H2 = 13331, M1 = 1000000007, M2 = 998244353;

typedef int HashCode;
#define mm1(x, m) ((x) % (m))
#define mm2(x, m) (((x) % (m) + (m)) % (m))

int h1[MAX], p1[MAX];
int h2[MAX], p2[MAX];
int g1[MAX];
int g2[MAX];

int hash_init = []() {
    p1[0] = 1;
    p2[0] = 1;
    for (int i = 1; i < MAX; i++) {
        p1[i] = mm1(p1[i - 1] * H1, M1);
        p2[i] = mm1(p2[i - 1] * H2, M2);
    }
    return 0;
}();

inline void hash_it(const char *s, int n) {
    h1[0] = 0;
    h2[0] = 0;
    for (int i = 0; i < n; i++) {
        h1[i + 1] = mm1(h1[i] * H1 + s[i], M1);
        h2[i + 1] = mm1(h2[i] * H2 + s[i], M2);
    }
    g1[n + 1] = 0;
    g2[n + 1] = 0;
    for (int i = n - 1; i >= 0; i--) {
        g1[i + 1] = mm1(g1[i + 2] * H1 + s[i], M1);
        g2[i + 1] = mm1(g2[i + 2] * H2 + s[i], M2);
    }
}

template <bool reverse = false>
inline HashCode hash_sub(int l, int r) {
    if (reverse) {
        int s1 = mm2(g1[l + 1] - g1[r + 2] * p1[r - l + 1], M1);
        int s2 = mm2(g2[l + 1] - g2[r + 2] * p2[r - l + 1], M2);
        return s1 << 32 | s2;
    }
    int s1 = mm2(h1[r + 1] - h1[l] * p1[r - l + 1], M1);
    int s2 = mm2(h2[r + 1] - h2[l] * p2[r - l + 1], M2);
    return s1 << 32 | s2;
}

int work(const char *s, int n) {
    int i = 0, j = n - 1;
    while (i < j and s[i] == s[j]) i++, j--;

    int res = 0;
    hash_it(s, n);
    for (int k = i; k <= j; k++) {
        int l = 1, r = (j - k + 1) / 2;
        while (l <= r) {
            int m = (l + r) / 2;
            if (hash_sub(k, k + m - 1) == hash_sub<true>(j - m + 1, j)) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        res = max(res, i + r);
    }

    return res;
}

void solve() {
    string s;
    cin >> s;
    const int n = s.size();

    int res = work(s.c_str(), n);
    reverse(s.begin(), s.end());
    res = max(res, work(s.c_str(), n));

    cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

OK！结束。