【算法作业】 循环赛问题 分治算法

题目：

设有N个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表

（1）每个选手必须与其他n-1个选手各赛一次

（2）每个选手一天只能赛一次

（3）当n 是偶数，循环赛进行n-1天，当n是奇数，循环赛进行n天。

思路分析：

如果n是奇数，其实就等于n+1种情况下将第n+1号选手轮空。所以只要考虑n是偶数的情况。用分治的思想来做，转换成n/2的子问题。考虑两种情况：

一、n/2为偶数。这种情况比较简单。例如n=4时。

        1 2 3 4

        2 1 4 3

        3 4 1 2

        4 3 2 1

可由n=2的子问题推出。

              1 2               1 2 3 4

              2 1               2 1 4 3

1 2         3 4               3 4 1 2

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

第一次变换下半部分=上半部分+n/2,第二次沿对角线对称。

二、n/2为奇数。由于n/2是奇数，子问题考虑n/2+1的情况。怎么由n/2+1的情况推出n的情况？

例如n=6时。先考虑它的子问题n=4时

        1 2 3 4

        2 1 4 3

        3 4 1 2

        4 3 2 1

由于四号选手是非法的所以：

       1 2 3 0

       2 1 0 3

       3 0 1 2

 同理推出

      1 2 3 0

      2 1 0 3

      3 0 1 2

      4 5 6 0

      5 4 0 6

      6 0 4 5

对第四列（第三天），只有一号选手和四号选手没比赛，那就让他们比。推出

      1 2 3 4

      2 1 5 3

      3 6 1 2

      4 5 6 1

      5 4 2 6

      6 3 4 5

之后的两天，考虑为比过的两位选手比赛就行了。比赛的顺序按未比赛的后几个选手顺序取模。例如前三天出现了 4那后两天为5 6。前三天出现了 5后两天为 6 4。

如此处理即可得到

      1 2 3 4 5 6

      2 1 5 3 6 4

      3 6 1 2 4 5

      4 5 6 1 2 3

      5 4 2 6 3 1

      6 3 4 5 1 2

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>

using namespace std;

int mp[1100][1100];

void dfs(int n)
{
    if(n==1)
    {
        mp[1][1]=1;
        return ;
    }
    if(n&1) n++;
    int t=n/2;
    dfs(t);
    for(int i=1;i<=t;i++)
        for(int j=1;j<=t+1;j++)
        {
            if(mp[i][j]>t)
            {
                mp[i+t][j]=i;
                mp[i][j]=i+t;
                int c=i+t+1;
                for(int k=t+2;(t&1)&&k<=n;k++,c++)
                {
                    if(c==i+t)  c++;
                    if(c>n) c-=n/2;
                    mp[i][k]=c;
                    mp[c][k]=i;
                }
            }
            else
            {
                mp[i+t][j]=mp[i][j]+t;
                if((t%2==0)||t==1)
                {
                    mp[i+t][j+t]=mp[i][j];
                    mp[i][j+t]=mp[i+t][j];
                }
            }
        }
}


int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(mp,0,sizeof(mp));
        if(n&1) dfs(n+1);
            else    dfs(n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n+(n&1);j++)
            {
                cout<<(mp[i][j]>n?0:mp[i][j]);
                cout<<(j==1?": ":" ");
            }
            cout<<endl;
        }
        cout<<endl;
    }
}