no more constructions

Melo.VVちゃん · 2026-11-12 20:00:01 · 题解

构造一个 n 个点的竞赛图使其恰有 m 个三元环。

三元环要求三个点首尾相接，限制比较强，单步容斥转化为统计任意三个点不构成三元环的数量，记为 A，那么答案是 {n\choose3}-A。

如果三个点不构成三元环那么必定恰好存在一个点在这三个点的导出子图中出度为 2，于是 A=\sum_{i=1}^n{\operatorname{deg}_i\choose2}。

这个东西没有任何明显的性质，考虑观察一下 {n\choose3}-A 的上下界，首先显然有下界 0，具体构造考虑每个点只往编号更大的点连出边即可。

思考一下上界，体感是让点的出度尽量平均，原因是对于 x>y,({x\choose2}+{y\choose2})-({x-1\choose2}+{y+1\choose2})=x-1-y\ge 0，即如果存在 u,v 满足 \operatorname{deg}_u>\operatorname{deg}_v 且边 (u,v) 的方向是 u\to v，那么将这条边调整为反向之后三元环数不降。

具体构造

• 对于 n 是奇数可以做到每个点的出度都是 \frac{n-1}{2}，具体构造只需要将所有的点先放置成一个环，然后每个点按照顺时针方向向后 \frac{n-1}{2} 个点连出边即可做到，三元环数上界化简之后不难得到是 F_n=\frac{n(n^2-1)}{24}。
• 对于 n 是偶数的情况，最优显然是出度为 \frac{n}{2} 和 \frac{n-2}{2} 的点数分别为 \frac{n}{2}，构造的话考虑首先按照上一条的方法构造 n+1 个点的图，再将任意一个点和与他有关的边删去即可，此时上界是 F_n=\frac{n(n^2-4)}{24}。

接下来猜测对于任何小于等于上界的 m 都有可行解。

发现 {x+1\choose 2}+{x-1\choose2}-2{x\choose2}=1，即如果存在两个点出度相同，翻转连接他们的边可以使得三元环数恰好减一。

如果不存在任何两个的点的出度相同的话，那么度数序列必定是 0,1\cdots n-2,n-1，此时三元环数为 0，即如果存在三元环必定存在两个点出度相同，那么也必定有办法使三元环数恰好减一，结论成立。

考虑实现，先构造出上界的图，使用队列存储有至少两个点的出度，每个出度可以使用 vector 存储点的编号，单次只需要取出队头度数然后从相应的 vector 中取出两个点翻转之间的边即可，每次翻转造成的修改是 O(1) 的，于是得到了 O(n^3) 的做法。

复杂度比较高的原因是上界和 m 差的可能比较多，考虑先找到一个 t 满足 F_{t-1}<m\le F_t，然后从 t 个点的上界图开始往 m 构造，此时复杂度是 F_t-m<F_t-F_{t-1}=O(n^2)。

接下来考虑构造一个 n-t 个点的没有三元环的竞赛图，然后这 n-t 个点都往构造的 t 个点连出边即可保证补成一个 n 个点的竞赛图且不增加三元环数。

#include "bits/stdc++.h"
#define int long long 
#define f(i ,m ,n ,x) for (int i = (m) ,i##end = (n) ; i <= i##end ; i += (x))

const int N = 5077 ;
int q ,n ,m ,buc[N] ; bool e[N][N] ;

signed main (void) {
    std :: ios_base :: sync_with_stdio (false) ,
    std :: cin.tie (nullptr) ,std :: cout.tie (nullptr) ;

    auto Calc = [] (int n) {
        if (n & 1) return n * (n - 1) * (n + 1) / 24 ;
        else return n * (n - 2) * (n + 2) / 24 ;
    } ;

    int Q ; std :: cin >> Q ; while (Q --> 0) {
        std :: cin >> n >> m ; f (i ,1 ,n ,1) f (j ,1 ,n ,1) e[i][j] = e[j][i] = false ;
        std :: fill (buc ,buc + n + 1 ,0) ;
        int p = 1 ; while (Calc (p) < m) p++ ;
        if (p > n) { std :: cout << "No\n" ; continue ;} std :: cout << "Yes\n" ;
        static std :: queue < int > q ;
        std :: vector < std :: vector < int > > node(p) ;

        if (p & 1) {
            buc[p - 1 >> 1] = p ;
            if (p > 1) q.emplace (p - 1 >> 1) ;
            f (i ,1 ,p ,1) node[p - 1 >> 1].emplace_back (i) ;
            f (i ,1 ,p ,1) {
                int j = i ; while (true) {
                    j = j % p + 1 ; 
                    e[i][j] = true ,e[j][i] = false ;
                    if (j == (i + (p - 1 >> 1) - 1) % p + 1) break ;
                }
                while (j != i) {
                    j = j % p + 1 ;
                    e[i][j] = false ,e[j][i] = true ;
                }
            } 
        } else {
            buc[p >> 1] = buc[p - 2 >> 1] = p >> 1 ;
            if (p > 2) {
                q.emplace (p >> 1) ;
                q.emplace (p - 2 >> 1) ;
            }
            f (i ,1 ,p + 1 ,1) {
                int j = i ; while (true) {
                    j = j % (p + 1) + 1 ; 
                    e[i][j] = true ,e[j][i] = false ;
                    if (j == (i + (p >> 1) - 1) % (p + 1) + 1) break ;
                }
                while (j != i) {
                    j = j % (p + 1) + 1 ;
                    e[i][j] = false ,e[j][i] = true ;
                }
            } 
            f (i ,1 ,p >> 1 ,1) node[p >> 1].emplace_back (i) ;
            f (i ,(p >> 1) + 1 ,p ,1) node[p - 2 >> 1].emplace_back (i) ;
        }

        int M = Calc (p) ; while (!q.empty ()) {
            int cur = q.front () ; q.pop () ;
            while (M > m && buc[cur] >= 2) {
                M-- ,buc[cur] -= 2 ;
                if (++buc[cur + 1] == 2) q.emplace (cur + 1) ;
                if (cur - 1 && ++buc[cur - 1] == 2) q.emplace (cur - 1) ;
                int u = node[cur].back () ; node[cur].pop_back () ;
                int v = node[cur].back () ; node[cur].pop_back () ;
                if (!e[u][v]) std :: swap (u ,v) ;
                e[u][v] = false ,e[v][u] = true ;
                if (cur - 1) node[cur - 1].emplace_back (u) ;
                node[cur + 1].emplace_back (v) ;
            } if (M == m) break ;
        } while (!q.empty ()) q.pop () ;

        f (i ,p + 1 ,n - 1 ,1) f (j ,i + 1 ,n ,1) e[i][j] = true ,e[j][i] = false ;
        f (i ,p + 1 ,n ,1) f (j ,1 ,p ,1) e[i][j] = true ,e[j][i] = false ;
        f (i ,2 ,n ,1) {
            f (j ,1 ,i - 1 ,1) {
                if (e[i][j]) std :: cout << '1' ; else std :: cout << '0' ;
            } std :: cout << '\n' ;
        }
    }
}