当前位置：首页 > article >正文

P6120 [USACO17JAN] Hoof, Paper, Scissor S

article 2025/1/30 13:08:33

难度：普及/提高−；

题意：

石头、剪刀、布游戏，先给出 $n$ 轮已经知道的其中一人的对局情况，例如样例：

5
P - 布
P - 布
H - 石头
P - 布
S - 剪刀

另外一人，只允许修改一次机会的情况下，求最多可以赢的局面数量。

分析：

题意理解了，我感觉就是很简单，可以用双指针做，也可以用前缀和分开两段来做。这里讲述前缀和分两段的分别统计贡献的方式来做。

根据题意可知，手势一旦确定为 $x$ ，那么只允许在后面第 $k$ 次发生了修改为 $y$ ，那么贡献(胜利的局数)就是 $k[x]_{1 \sim x} \ + \ k[y]_{x \sim n}$ ，其中 $k$ 数组可以用前缀和来完成。

参考代码：

#include <bits/stdc++.h>
#define ll long long

const int N = 100050;
int h[N], s[N], p[N], n;

int mx(int a, int b) // 为了让代码看起来简短一些
{
    if (a > b)
        return a;
    return b;
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1], s[i] = s[i - 1], p[i] = p[i - 1];
        char ch;
        std::cin >> ch;
        if (ch == 'H')
            h[i]++;
        if (ch == 'S')
            s[i]++;
        if (ch == 'P')
            p[i]++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) // [1-i], [i+1,n] 找出区间内最长的两段
        ans = mx(ans, mx(h[i], mx(s[i], p[i])) + mx(h[n] - h[i], mx(s[n] - s[i], p[n] - p[i])));
    std::cout << ans << '\n';
    return 0;
}