题解：P10441 [JOIST 2024] 乒乓球 / Table Tennis

· · 题解

补充一下如何根据入度序列 \mathcal{O}(n^2) 构造竞赛图。

前面的部分可以看其他题解，基本上就是找到最小的子图使得三元环数量超过 m 然后每次操作减少一个三元环。

确定度数序列（升序排序）之后考虑从左到右构造边，每次确定和前面的连边情况。

考虑构造过程，我们最终目标是使所有 \deg_i 清零，则每次我们有两种连边，若 i\to j 则令 \deg_i 减少，否则令 \deg_j 减少。

由于每一对 (i,j) 之间只有一次机会，所以我们的目标是令目前所有 \deg 基本平均。

所以每次把前面所有点按照剩余的 \deg 排序之后，逐个确定连边方向：

排序部分可以换成桶排序做到线性，总复杂度 \mathcal{O}(n^2)。

#include "bits/stdc++.h"
using namespace std;
typedef long long ll1;
const int N=5005;
#define pii pair<int,int>
#define mkp make_pair
ll1 C2(ll1 x){return x*(x-1)/2;}
ll1 calc(ll1 n){
    if(n<3)return 0; 
    ll1 res=n*(n-1)*(n-2)/6;
    ll1 d=(n-1)/2;
    ll1 cd1=(n*(n-1)/2)-(d*n);
    ll1 cd=n-cd1;
    res-=cd*C2(d)+cd1*C2(d+1);
    return res;
}
int n;ll1 K;
int cnt[N],deg[N];
int g[N][N];
int b[N],c[N];
int stk[N*N*2],top=0;
void work(){
    scanf("%d%lld",&n,&K);
    ll1 m=1;
    while(calc(m)<K&&m<=n)m++;
    for(int i=0;i<=n;i++)cnt[i]=deg[i]=0;
    if(m>n){printf("No\n");return;}

    ll1 k=1ll*m*(m-1)*(m-2)/6;
    ll1 d=1ll*(m-1)/2;
    ll1 cd1=(1ll*m*(m-1)/2)-1ll*d*m;
    ll1 cd=1ll*m-cd1;
    k-=1ll*cd*C2(d)+1ll*cd1*C2(d+1);
    k-=K;
    cnt[d]=cd,cnt[d+1]=cd1;
    top=0;
    if(cnt[d]>1)stk[++top]=d;
    if(cnt[d+1]>1)stk[++top]=d+1;
    while(k--){
        int x=stk[top--];
        cnt[x]-=2;
        cnt[x-1]++,cnt[x+1]++;
        if(cnt[x]>1)stk[++top]=x;
        if(cnt[x-1]==2)stk[++top]=x-1;
        if(cnt[x+1]==2)stk[++top]=x+1;
    }
    m=0;
    for(int i=0;i<=n;i++)
        while(cnt[i]--)deg[++m]=i;
    for(int i=1+m;i<=n;i++)deg[i]=i-1;
    sort(deg+1,deg+1+n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        g[i][j]=-1;
    int lst=0,sm=0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=n;x++)c[x]=0;
        for(int j=1;j<i;j++)c[deg[j]]++;
        for(int x=1;x<=n;x++)c[x]+=c[x-1];
        for(int j=1;j<i;j++)b[c[deg[j]]--]=j;
        for(int j=1;j<=i-1;j++){
            int u=b[j];
            if(deg[u]>=deg[i])g[i][u]=1,deg[u]--;
            else g[i][u]=0,deg[i]--;
        }
    }
    printf("Yes\n");
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            printf("%d",g[i][j]);
        printf("\n");
    }
}
int main(){
    int T=0;scanf("%d",&T);
    while(T--)work();
    return 0;
}
/*
- - 海狸 i 草死了海狸 j，海狸 j 草死了海狸 k，海狸 k 又草死了海狸 i。
- - 海狸 i 草死了海狸 k，海狸 k 草死了海狸 j，海狸 j 又草死了海狸 i。
- - 海狸 i 草死了海狸 k，海狸 k 草死了海狸 j，海狸 j 又草死了海狸 i。
- - 海狸 i 草死了海狸 k，海狸 k 草死了海狸 j，海狸 j 又草死了海狸 i。
*/