https://codeforces.com/contest/1487/problem/C
题目大意
给出 $n \ (\le 100)$ 只球队，两两各打一场比赛，输记 $0$ 分，平局记 $1$ 分，赢记 $3$ 分。已知在 $n (n - 1) / 2$ 场比赛后，所有球队比分相同，请构造出一个方案，使得平局尽量少。
简要题解
假设有 $w$ 个非平局和 $t$ 个平局则。$w + t = n (n - 1) / 2$
分数为 $3(n (n - 1) / 2 - t) + 2p$。因为所有队伍分数相等则，我们需要 $n | (3n(n - 1) / 2 - t)$。
当 $n$ 为奇数时，因为 $2 | n - 1$ 则 $n | (3n(n - 1) / 2)$，即 $t$ 可以等于 $0$。此时所有球队各胜负一半的场次，我们发现如下构造即可。这样每两行，对于后面的球队都各胜负一场，奇数行之前胜负是一致的，本行要处理新的偶数轮。偶数行之前多输一场，本行要处理奇数轮，正好多胜一场。每行过后，对应的本行的球队就打完了所有比赛。
2 3 4 5
1 1 -1 1 -1
2 1 -1 1
3 1 -1
4 1
$n$ 为偶数时，显然 $\frac{3n(n - 1)}{2n} = \frac{3(n - 1)}{2}$ 这不是一个整数，即我们需要 $p$。此时
$$ \frac{3n(n - 1)}{2} = \frac{3n^2}{2} - n - \frac{n}{2} = -\frac{n}{2} \mod n$$即至少 $t = \frac{n}{2}$。同上我们发现了这样一个构造。每两行，我们在他们之间打一个平局。
奇数行 $i$，我们先和 $i + 1$ 踢一场平局，之后有偶数轮，各胜负一场。 偶数行 $i + 1$，我们直接与上一行输赢相反的来一遍。
这样处理完当前对，总是当前行有一个平局，而其他局输赢相反。后续所有更大的 $j$ 总有相同的胜负场。
2 3 4 5 6
1 0 1 -1 1 -1
2 -1 1 -1 1
3 0 1 -1
4 -1 1
5 0
复杂度
$T$：$O(n)$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
/*
(n - 1)
n odd -> (n - 1) even, win half lose half is fine.
n even -> (n - 1) odd, every team at least have a tie
4
1 2, 1 3, 1 4, 2 3, 2 4, 3 4
0 1 -1 -1 1 0
2 3 4
1 0 1 -1
2 -1 1
3 0
2 3 4 5
1 1 -1 1 -1
2 1 -1 1
3 1 -1
4 1
2 3 4 5 6
1 0 1 -1 1 -1
2 -1 1 -1 1
3 0 1 -1
4 -1 1
5 0
*/
void solve() {
int n; cin >> n;
if (n & 1) {
for (int i = 0; i < n * (n - 1) / 2; i++) {
if (i & 1) {
cout << "-1";
} else {
cout << "1";
}
cout << (" \n"[i == n * (n - 1) / 2 - 1]);
}
} else {
for (int i = 0; i < n - 2; i++) {
if ((i & 1) == 0) cout << "0 ";
for (int j = i + ((i & 1) ? 1 : 2); j < n; j++) {
cout << (((i ^ j) & 1) ? -1 : 1) << ' ';
}
}
cout << "0\n";
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Pythagorean Triples - Educational Codeforces Round 104 (Rated for Div. 2)