题解 CF1487C 【Minimum Ties】

meyi · 2021-02-25 22:29:28 · 题解

令 x 为有胜负的局数， y 为平局局数，易得下列方程组：

\begin{array}{l} x+y=\frac{n(n-1)}{2} \\ 3x+2y=kn (k \in N^*) \end{array} \right.

对第二个方程的解释：有胜负的局数会为所有队的总分的和贡献 3 分，平局会贡献 2 分，而题目要求 n 支所有球队的积分完全相同，故总分为 n 的倍数。

解得

\begin{array}{l} x=(k-n+1)n \\ y=(\frac{3n-3}{2}-k)n (k\in N^*) \end{array} \right.

若 n 为奇数，则 k 显然取 \frac{3n-3}{2}，此时 \begin{array}{l} x=\frac{n(n-1)}{2} \\ y=0 \end{array} \right.

只需让每只队伍都赢 \frac{n-1}{2} 次即可。

若 n 为偶数，则 k 显然取 \frac{3n-4}{2}，此时 \begin{array}{l} x=\frac{n(n-2)}{2} \\ y=\frac{n}{2} \end{array} \right.

只需让每只队伍都赢 \frac{n-2}{2} 次，平局 1 次即可。

时间复杂度 O(tn^2)。

代码：

#include<cstdio>
#define ri register int
int n,t;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(ri i=1;i<n;++i){
            ri j=i+1;
            if(!(n&1)&&(i&1))++j,printf("0 ");
            for(;j<=n;++j)
                printf("%d ",(j-i)&1?-1:1);
        }   
        putchar(10);
    }
    return 0;
}