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

· · 题解

思路

容易发现：如果 Bessie 要确保战胜 Elsie，当且仅当 Bessie 出的手势组合中至少有一个手势能够同时战胜 Elsie 手势组合中的所有手势。

不然，无论 Bessie 出哪个手势，Elsie 总有至少一个手势满足 Bessie 不能战胜 Elsie。

所以，对于 Elsie 计划出的每一个手势组合 (L,R)，我们需要枚举能同时战胜 L 和 R 的手势个数，记为 ans。

每一个能够同时战胜 L 和 R 的手势，都可以与所有手势进行搭配。注意到 (L,R) 和 (R,L) 算两种组合，所以满足要求的手势组合数量为 ans \times n \times 2。

但是，任意两个（可以相同）满足要求的手势的组合，都被统计了两次，所以答案应该减去 ans \times ans。

综上，答案即为 ans \times (n \times 2-ans)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
bool a[3005][3005];   //胜：1 败或平：0 
string s;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=i;j++){
            if(s[j-1]=='W') a[i][j]=1;      //i 能战胜 j
            if(s[j-1]=='L') a[j][i]=1;      //j 能战胜 i
        }
    }
    while(m--){
        cin>>l>>r;
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i][l]&&a[i][r]) ans++;     //统计能同时战胜 L 和 R 的手势个数
        }
        cout<<ans*(n*2-ans)<<'\n';          //输出答案
    }
    return 0;  //完结撒花
}