【例65.1】 循环比赛

解题思路

编号先从0开始，第d天选手i的对手为i XOR d，最后加1输出。表的第0列为自身编号，d=1～N-1才是真正赛程。

正确性说明

d≠0时i XOR d≠i且(i XOR d) XOR d=i，配对互相对应无轮空；d遍历非零N位内值时对手遍历除自身外所有人，因此每对恰赛一次。

易错点

按样例输出N×N完整表，第一列不是比赛对手。

复杂度

时间O(N²)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M;
    cin >> M;
    int N = 1 << M;
    for (int i = 0; i < N; i++) {
        for (int d = 0; d < N; d++) {
            if (d)
                cout << " ";
            cout << (i ^ d) + 1;
        }
        cout << "\n";
    }
    return 0;
}