Chess Tournament（思维题）

题目

Chess Tournament

问题描述

有$n$个人参加比赛，两两之间进行对决，每两个人之间都会进行一次比赛；
对决有三种结果：要么胜，要么败，要么平。

选手有两种策略：
第一种：全场不败，稳扎稳打；
第二种：但求一胜，败局不论。

在选手给出自己选择的策略后，问是否存在一种局面使得所有选手都满足自身策略。

若不存在，则输出"NO"；
若存在，则输出"YES"，并以$n?n$的矩阵输出结果。

$?$，表示自己与自己对决；
$+$，表示行序号代表的选手赢了列序号代表的选手；
$?$，表示行序号代表的选手输给了列序号代表的选手；
$=$，表示行序号代表的选手与列序号代表的选手打平；

分析

先分析两种策略，
策略一，表示对决结果只能为胜利或平局；
策略二，表示允许失败和平局，但至少赢一局。

对于采取策略一的选手来说，对决结果可以为胜利或平局，但为了不对采取策略二的选手造成影响，将他们的对局情况都安排为平局是最好的。

对于采取策略二的选手来说，他们与采取策略一的选手对决结果此时满足平局，所以他们的胜局必须要依靠同样采取策略二的选手：
当采取策略二的人数为0时，和和气气，大家都是平局，满足条件；
当采取策略二的人数只有一个人时，这位选手找不到同样采取策略二的对手，所以不存在；
当采取策略二的人数为两个人时，两个人之间只会对决一次，一战定胜负，无法双赢，从而必有一人无法满足策略二，所以不存在；
当采取策略二的人数大于二时，可以进行相互成全，让每个采取策略二的人都获得一次胜利（这也许就是演戏吧），满足条件。

之后我们按这个模拟一下即可，先将策略一的选手的情况的安排好，再处理选择策略二的选手，给他们安排好一次胜局后，就可以把他其余还没有结果的比赛都安排为负局。

代码

#include <bits/stdc++.h>
using namespace std;
int t;
int n;
string s;
char a[55];
char b[55][55];
int main(){
    cin>>t;while(t--){
    cin>>n;memset(b,0,sizeof b);int a1=0,a2=0;cin>>s;for(int i=1;i<=n;i++){
    a[i]=s[i-1]-'0';b[i][i]='X';if(a[i]==1)a1++;else a2++;}if(a2==2||a2==1){
    cout<<"NO"<<endl;continue;}cout<<"YES"<<endl;for(int i=1;i<=n;i++){
    if(a[i]==1){
    for(int j=1;j<=n;j++){
    if(j==i)continue;b[i][j]=b[j][i]='=';}}}for(int i=1;i<=n;i++){
    int ans=0;if(a[i]==2){
    for(int j=1;j<=n;j++){
    if(j==i)continue;else if(b[i][j]=='+'&&ans==0)ans=1;else if(!b[i][j]&&ans==0){
    b[i][j]='+';b[j][i]='-';ans=1;}else if(!b[i][j]&&ans==1){
    b[i][j]='-';b[j][i]='+';}}}}for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    cout<<b[i][j];}cout<<endl;}}return 0;
}