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

· · 题解

思路

首先，如果一个点 u 有两条出边分别指向 i,j 的话，那么 u,i,j 构不成三元环，这个是显然的。

我们总共可能的三元环数量是 \dbinom{n}{3}，然后根据上面的东西，若第 i 个点的出度是 d_i，则这个竞赛图的三元环数量是 \dbinom{n}{3}-\displaystyle\sum_{i=1}^{n}\dbinom{d_i}{2}。

这个东西的最小值可以取到 0，此时只需要让所有边都从小指到大即可。考虑最大值，首先 d_i 之和是一定的，为边数。我们需要让原式最大即让减号后面的东西最小，显然把 d_i 取得尽量平均会达到最小。于是我们能 O(1) 算出一张 n 个点的竞赛图最多有几个三元环。

我们希望让这个图少一些三元环，那么能不能通过修改一些东西让这个图减少恰好一个三元环呢？事实上是可以的，就是你考虑如果一条边连接了两个 d 相同的点，那么你把这条边反向，事实上会恰好减少一个三元环，同时这两个 d 一个加一，一个减一。且有在这张图没有三元环之前我们总能找到这样的一条边（因为这是竞赛图）。

但是你发现，我要减少的边的数量可能是 O(n^3) 的，然后复杂度就炸掉了。

仔细考虑一下，发现一张竞赛图我增加一个点，至多增加 O(n^2) 个三元环，那么你只需要找到一个最小的 n，使得 n 个点的竞赛图可以凑出 m 个三元环，剩下的点直接从小到大连就是没有贡献的。

于是我们只需要减少 O(n^2) 个三元环。把 d 从大到小排序，然后对于每个 i，从后往前尝试连边即可。这样做会优先减少出度较大的点的出度，这样做是正确的。感性理解一下就是，如果你一直不减出度较大的，那可能到它的时候点不够了，然后就爆炸了。

我们需要动态维护 d，并支持从小到大取出。一个直观的做法是上堆维护，复杂度是 O(n^2\log n)，卡卡常可以过。但是你注意到你每次会对一个前缀的 d 减去一，所以你记录一下这个前缀的长度，然后归并一下就行了。这样做是 O(n^2) 的。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned int
#define N 5005
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define inf 2e18
using namespace std;
int Tc=1;
ll n,m;
bool st[N][N];
ll C(int n,int m){
    if(n<m)return 0;
    if(m==2)return 1ll*n*(n-1)/2;
    return 1ll*n*(n-1)/2*(n-2)/3;
}
ll f(int n){
    ll res=C(n,3);
    res-=1ll*n*C((n-1)/2,2);
    if(n%2==0)res-=1ll*(n/2)*(C(n/2,2)-C((n-1)/2,2));
    return res;
}
int d[N];
pii g[N],h[N];
void solve(int cs){
    if(!cs)return;
    cin>>n>>m;
    if(f(n)<m){
        cout<<"No\n";
        return;
    }
    for(int i=1;i<=n;i++){
        d[i]=0;
        for(int j=1;j<=n;j++){
            st[i][j]=0;
        }
    }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        if(f(i)<m)continue;
        m=f(i)-m;
        for(int j=1;j<=i;j++){
            d[j]=(i-1)/2;
            if(i%2==0&&j<=i/2)d[j]++;
        }
        for(int j=1;j<=n;j++){
            d[j]+=min(n-i,n-j);
        }
        while(m){
            for(int l=1,r=1;l<=i;){
                r=l;
                while(r<i&&d[r+1]==d[r])r++;
                int tmp=r;
                while(l<r&&m>0){
                    m--;
                    d[l]--;d[r]++;
                    l++;r--;
                }
                r=tmp;
                l=r+1;
            }
        }
        break;
    }
    sort(d+1,d+n+1,greater<int>());
    // for(int i=1;i<=n;i++){
    //     cerr<<d[i]<<' ';
    // }
    // cerr<<'\n';
    for(int i=1;i<=n;i++){
        g[i]={d[i],i};
    }
    for(int k=1;k<=n;k++){
        int i=g[k].y;
        int fj=n;
        for(int j=n;j>k;j--){
            auto t=g[j];
            if(!d[i]){
                d[t.y]--;
                g[j].x--;
                st[t.y][i]=1;
            }
            else{
                fj=j-1;
                d[i]--;
                st[i][t.y]=1;
            }
        }
        int l=k+1,r=fj+1,cur=k;
        // cerr<<"dududu "<<l<<' '<<r<<'\n';
        while(l<=fj&&r<=n){
            if(g[l].x>=g[r].x){
                h[++cur]=g[l++];
            }
            else{
                h[++cur]=g[r++];
            }
        }
        while(l<=fj)h[++cur]=g[l++];
        while(r<=n)h[++cur]=g[r++];
        for(int j=k+1;j<=n;j++){
            g[j]=h[j];
            // cerr<<g[j].x<<' ';
        }
        // cerr<<'\n';
    }
    // for(int i=1;i<=n;i++){
    //     cerr<<d[i]<<' ';
    // }
    // cerr<<'\n';
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            cout<<st[i][j];
        }
        cout<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // init();
    cin>>Tc;
    for(int cs=1;cs<=Tc;cs++){
        solve(cs);
    }
    // cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
    // cerr<<((&ed)-(&st))/1048576.0<<'\n';
    return 0;
}