Hoof Paper Scissors Minus One

题意

有 $N$ 种手势，题目给出任意两个手势之间的胜负关系。

每次询问给出 Elsie 的两个候选手势 s1, s2。Bessie 也要选择一个有序手势对 (L,R)，表示左蹄和右蹄各出一个手势。

看到四个手势后，双方都会从自己的两个手势中选一个真正出。要求统计有多少个有序对 (L,R) 可以让 Bessie 保证获胜。

这里“保证获胜”的关键含义是：Bessie 必须能选出自己的某一个手势，使它无论对上 Elsie 的 s1 还是 s2 都能赢。

思路

暴力想法

最直接的做法是对每次询问枚举 Bessie 的两个手势 (L,R)。

如果 L 能同时赢 s1 和 s2，或者 R 能同时赢 s1 和 s2，那么这个有序对合法。

这个暴力适合小数据和对拍：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:07
 * update_at: 2026-07-11 12:11
 */
// brute.cpp：小数据暴力解，直接枚举 Bessie 的两个有序手势。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
char win[MAXN][MAXN];

void read_input() {
    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') {
                win[i][j] = 1;
            } else if (c == 'L') {
                win[j][i] = 1;
            }
        }
    }
}

bool can_guarantee(int l, int r, int s1, int s2) {
    // Bessie 必须能选出同一个手势，同时打败 Elsie 的两个候选手势。
    if (win[l][s1] && win[l][s2]) {
        return true;
    }
    if (win[r][s1] && win[r][s2]) {
        return true;
    }
    return false;
}

long long brute_answer(int s1, int s2) {
    long long ans = 0;
    for (int l = 1; l <= n; l++) {
        for (int r = 1; r <= n; r++) {
            if (can_guarantee(l, r, s1, s2)) {
                ans++;
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    for (int i = 1; i <= m; i++) {
        int s1, s2;
        cin >> s1 >> s2;
        cout << brute_answer(s1, s2) << '\n';
    }

    return 0;
}

优化观察

对一次询问 (s1,s2)，先只考虑一个单手势 x。

如果：

text

1
2win[x][s1] = true
win[x][s2] = true

那么 x 就是一个“好手势”：Bessie 只要有这个手势，就可以选择它出，从而保证赢 Elsie 的两个候选手势。

设这样的好手势有 cnt 个。

Bessie 的有序对 (L,R) 一共有 $N^{2}$ 个。合法条件是：

text

1L 是好手势，或者 R 是好手势

反过来看，不合法的有序对必须满足：

text

1L 不是好手势，并且 R 也不是好手势

这样的有序对数量是 $(N-cnt)^2$ 。

所以答案为：

N^2 - (N-cnt)^2

每次询问只需要扫描一遍 $1 \dots N$ 求出 cnt，不用再枚举 $N^{2}$ 个有序对。

胜负表读入

输入只给出下三角：

如果第 i 行第 j 个字符是 W，说明 i 赢 j，记 win[i][j] = true。
如果是 L，说明 i 输给 j，也就是 j 赢 i，记 win[j][i] = true。
如果是 D，双方都不能赢，不需要记录。

对应的离散数学知识

这题的正解可以对应到三个很基础的离散数学概念：逻辑谓词、集合补集、乘法规则。

先定义一个逻辑谓词：

good(x) := win(x,s1) \land win(x,s2)

它表示手势 $x$ 能同时赢 Elsie 的两个候选手势。代码中统计的 cnt，就是满足 good(x) 的手势数量。

Bessie 选择的是有序对 $(L,R)$ 。这个有序对合法，当且仅当：

good(L) \lor good(R)

直接统计“至少一个成立”不如统计补集。非法情况是：

\lnot good(L) \land \lnot good(R)

也就是左蹄不是好手势，右蹄也不是好手势。

如果好手势有 cnt 个，那么非好手势有 $N-cnt$ 个。左蹄有 $N-cnt$ 种选法，右蹄也有 $N-cnt$ 种选法。根据组合数学中的乘法规则，非法有序对数量是：

(N-cnt)(N-cnt)=(N-cnt)^2

最后用总数减去补集：

N^2-(N-cnt)^2

所以这题的核心可以概括为：用逻辑谓词定义“好手势”，再用补集和乘法规则计算至少包含一个好手势的有序对数量。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:07
 * update_at: 2026-07-11 12:11
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;

int n, m;
char win[MAXN][MAXN]; // win[a][b] = 1 表示手势 a 能赢手势 b

void read_input() {
    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') {
                win[i][j] = 1;
            } else if (c == 'L') {
                win[j][i] = 1;
            }
        }
    }
}

long long calc_answer(int s1, int s2) {
    long long cnt = 0;
    for (int x = 1; x <= n; x++) {
        if (win[x][s1] && win[x][s2]) {
            cnt++;
        }
    }

    // 有 cnt 个单手势能同时赢 Elsie 的两只蹄子。
    // Bessie 的有序二元组只要至少包含一个这样的手势即可。
    return 1LL * n * n - 1LL * (n - cnt) * (n - cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    for (int i = 1; i <= m; i++) {
        int s1, s2;
        cin >> s1 >> s2;
        cout << calc_answer(s1, s2) << '\n';
    }

    return 0;
}

复杂度

读入胜负表需要 $O(N^2)$ 。

每次询问扫描所有手势，复杂度 $O(N)$ 。

总时间复杂度：

O(N^2 + NM)

空间复杂度：

O(N^2)

总结

这题的关键是不要直接枚举 Bessie 的两个手势，而是先找出“能同时赢 Elsie 两个手势”的单手势集合。

一旦好手势数量 cnt 确定，合法有序对数量就可以用补集一次算出：

N^2 - (N-cnt)^2

这类题常见转化是：先把二元选择压缩成“某个单点是否有用”，再用计数公式统计包含这个集合的有序对。