UVA-1609_uva1609-CSDN博客

本文链接：https://blog.csdn.net/weixin_43312327/article/details/86680287

本文介绍了一种比赛配对算法的实现，通过将参赛者分为“黑队”和“白队”，并经过四个阶段的匹配过程，确保每轮比赛都有公平且随机的配对。算法首先基于初始条件将选手分为可能胜利的“白队”和可能失败的“黑队”，然后通过一系列匹配策略，包括白队打黑队、黑队内部对决及随机分配，来完成整个比赛的配对。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

这个题就是纯构造，一旦找到“黑队”和“白队”的概念，就有一定的思路了。
后面就是构造四个阶段。每一个阶段的原则就是尽量让白队打黑队，然后让黑队内部打，最后随机分配。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1024+5;
char table[maxn][maxn];

int main(void){
    int n;
    while(scanf("%d",&n)==1){
        vector <int> win,lose;
        for(int i=1;i<=n;i++){
            scanf("%s",table[i]+1);
        }
        for(int j=2;j<=n;j++){
            if(table[1][j]=='1') win.push_back(j);
            else lose.push_back(j);
        }
        //win代表1可以y赢，lose代表1会输。
        //lose是黑子

        int ct = n;
        while(ct>1){
            vector<int> win2,lose2,nextt;

            for(int i=0;i<lose.size();i++){
                int tlose=lose[i];
                bool match=false;
                for(int j=0;j<win.size();j++){
                    if(win[j]==0) continue;
                    int twin=win[j];
                    if(table[twin][tlose]=='1'){
                        printf("%d %d\n",twin,tlose);
                        win2.push_back(twin);
                        win[j]=0;
                        match=true;
                        break;
                    }
                }
                if(!match) nextt.push_back(tlose);
            }

            bool first=true;
            for(int i=0;i<win.size();i++){
                int twin=win[i];
                if(win[i]){
                    if(first){
                        first=false;
                        printf("1 %d\n",win[i]);
                    }
                    else{
                        nextt.push_back(twin);
                    }
                }
            }


            for(int i=0;i<nextt.size();i+=2){
                printf("%d %d\n",nextt[i],nextt[i+1]);
                int keep = nextt[i];
                if(table[nextt[i+1]][keep]=='1') keep=nextt[i+1];
                if(table[1][keep]=='1') win2.push_back(keep);
                else lose2.push_back(keep);
            }


            win=win2;
            lose=lose2;
            ct>>=1;
        }
    }
    return 0;
}