当前位置: 代码迷 >> 综合 >> JakeLin-[蓝桥杯][算法训练VIP]比赛安排-题解
  详细解决方案

JakeLin-[蓝桥杯][算法训练VIP]比赛安排-题解

热度:102   发布时间:2023-11-13 15:29:16.0

题目描述

设有有2^n(n<=6)个球队进行单循环比赛,计划在2^n–1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2^n–1天内每个队都与不同的对手比赛。 

输入

共一行,输入n的数值。 

输出

共(2^n  –  1)行,第i行输出第i天的比赛安排。 
格式为:<i> A-B C-D 其中i是天数,A,B分别为比赛双方的编号,每行共2n-1个比赛场次。 

样例输入

2 

样例输出

<1>1-2 3-4
<2>1-3 2-4
<3>1-4 2-3 

原题链接:[蓝桥杯][算法训练VIP]比赛安排

思路:
以n=3为例,总共8个人,7天,那么第一列必是1和另外七个人打。
后面的还没打过的两两一组,但是注意如果他们俩前些日子打过了,就不要安排他们一起打了,所以用到viss数组记录谁跟谁打过
【采用链表遍历的思想,但是这里直接判断】

两个vis数组变量说明:

名称 作用
vis[100] 贯穿一行,vis[j]表示这一天中j已经打过了,请不要再安排他
viss[100] 贯穿整个程序,viss[i][j] 表示“i-j”已经打过了,下面请不要再把他们安排在一起

 附代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int vis[100];
int viss[100][100];
int main(){int n;cin>>n;int per = pow(2,n);int day = pow(2,n)-1;for(int i=1;i<=day;i++){memset(vis,0,sizeof(vis));    cout<<"<"<<i<<">";int p=1;while(p<=per){  if(vis[p]==1){  //找出第一个还没打过的pp++;continue;}int tmp=p;for(int q=p+1;q<=per;q++){ //判断谁和p打:找出qif(vis[q]==0 && viss[p][q]==0){  //如果他们之前没打过vis[p]=vis[q]=viss[p][q]=1;cout<<p<<"-"<<q<<" ";p=tmp+1;   //判断下一个人pbreak;}}}cout<<endl;}return 0;
}