题解：P12022 [USACO25OPEN] Hoof Paper Scissors Minus One

Lazy_tag_ · 2025-04-05 19:39:53 · 题解

Bessie 和 Elsie 在玩一个变种的石头剪刀布游戏。她们各自出两个手势，然后选择其中一个进行对决。Bessie 需要确保无论 Elsie 选择哪一个手势，自己都能选择一个手势击败对方。题目要求计算 Bessie 有多少种手势组合满足这一条件。

首先读取手势胜负关系表，构建每个手势能击败的所有手势的集合。

对于每个查询，找到能同时击败 Elsie 两个手势的集合 C。Bessie 的两个手势中至少有一个属于 C 时，才能确保胜利。

计算属于 C 的手势数目 cnt，有效组合数为 cnt \times (2 \times N - cnt)，其中 N 为手势总数。

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3001;
bitset<MAXN> b[MAXN];

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= i; ++j) {
            char c = s[j-1];
            if (c == 'W') {
                b[j].set(i); // i输给j
            } else if (c == 'L') {
                b[i].set(j); // j输给i
            }
        }
    }

    while (M--) {
        int s1, s2;
        cin >> s1 >> s2;
        auto ans = b[s1] & b[s2];
        int cnt = ans.count();
        cout << cnt * (2LL * N - cnt) << '\n';
    }

    return 0;
}