自动搬运

查看原文

来自洛谷，原作者为

	CSP_S_2023_T2 时代的灰尘落在个人头上，就是一座山，但总有人愿意成为移山的愚公

搬运于2025-08-24 23:12:11，当前版本为作者最后更新于2025-04-07 16:01:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

容易发现：如果 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;  //完结撒花
}