题解：P10441 [JOISC 2024 Day4] 乒乓球
Otomachi_Una_
·
·
题解
【题目简述】
构造一个 n 个点，m 个三元环的竞赛图。
**【解题思路】**
经典结论：竞赛图三元环只和每个点的入度序列有关。
不难发现当入度序列为 $[0,1,\dots,n-1]$ 时没有三元环，当把一对 $(x,x+2)$ 调整为 $(x+1,x+1)$ 时会多一个三元环。
直接调整复杂度是 $\mathcal O(M)$ 的。可以考虑找一个最小的 $n_0\leq n$ 使得其最大三元环量不小于 $M$，在 $n_0$ 基础上调整，其余连成 DAG 即可。
时间复杂度：$\mathcal O(n^2)$。
**【参考代码】**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5005;
int n,d[MAXN];ll m;
bool ans[MAXN][MAXN];
ll max_reach(ll x){
ll r=x*((x-1)/2)*(x/2);
return (r-x*(x-1)*(x-2)/6)/2;
}
void solve(){
cin>>n>>m;
if(m>max_reach(n)){
cout<<"No\n";
return;
}
cout<<"Yes\n";
for(int i=1;i<=n;i++) d[i]=i-1;
for(int i=1;i<=n;i++) if(m<=max_reach(i)){
m=max_reach(i)-m;
if(i%2==1) for(int j=1;j<=i;j++) d[j]=(i-1)/2;
else for(int j=1;j<=i;j++) d[j]=i/2-(j<=i/2);
while(m){
for(int l=1,r=1;r<n;l=r+1){
r=l;
while(r<i&&d[r+1]==d[r]) r++;
int r0=r;
while(m>0&&l<r){
m--;
d[l++]--,d[r--]++;
}
r=r0;
}
}
break;
}
sort(d+1,d+n+1);
// for(int i=1;i<=n;i++) cout<<d[i]<<" \n"[i==n];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=0;
for(int i=n;i>=2;i--){
d[i]=i-1-d[i];
for(int l=i-1,r=i-1;;r=l-1){
l=r;
while(l>1&&d[l]==d[l-1]) l--;
for(int j=l;j<=r;j++){
if(d[i]>0) d[i]--,d[j]--,ans[j][i]=1;
else ans[i][j]=1;
}
if(l==1) break;
}
// if(d[i]) cerr<<"ERROR "<<i<<' '<<d[i]<<endl;
}
for(int i=2;i<=n;i++) for(int j=1;j<i;j++){
cout<<ans[i][j];
if(j==i-1) cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
int _;cin>>_;
while(_--) solve();
return 0;
}
```