P5441

Aryper · 2021-09-14 00:06:59 · 个人记录

【XR-2】伤痕

构造题。

然后我们可以看到非核心的选法只有三种，一种是一个点三条都是出边无入边，一种是除了第一种外一个点都是三条入边无出边，一种是两条没有公共点的无向边，其中一个边没有一条边能指向另一条边。

然后就有了神奇的构造。可以大概地想到，使对于某一个点，它的纯出边和纯入边尽量均衡，另外就是无向边连稍长的边。

所以说我们设 p=\dfrac{n-1}{2}。

那么我们构造一个 n 边形，对于点 i，顺时针连 p-1 个出边，然后连一条无向边，没了。

最后我们发现这个构造可以使第二种和第三种的非核心选法全部不存在。于是：

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e2;

ll n,ans;

ll e[N+5][N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();

    if(n!=1) {

        ans=n*(n-3)*(n*n+6*n-31)/48;

        writeln(ans);

        for(ll i=1;i<=n;i++) {
            for(ll j=1;j<=(n-3)/2;j++) {
                e[i][(i+j-1)%n+1]=1;
            }
            e[i][(i+(n-1)/2-1)%n+1]=1;e[(i+(n-1)/2-1)%n+1][i]=1;
        }

        for(ll i=1;i<=n;i++) {
            for(ll j=1;j<=n;j++) {
                write(e[i][j]);putchar(' ');
            }
            putchar('\n');
        }
    }
    else {
        writeln(0);writeln(0);
    }

    return 0;
}