Python3 解法, 执行用时: 601ms, 内存消耗: 5112K, 提交时间: 2022-07-10 18:41:16

def rec(n,m):
    if m >= n:
        return 1
    elif m == 1:
        return n
    else:
        return rec(n-1,m-1)+rec(n-1,m)
    

c3 = [rec(i, 3) for i in range(0, 72)]
c4 = [rec(i, 4) for i in range(0, 72)]


lst = []
def sz(a):
  if len(a) == 0:
    return 0
  return a[0] + len(a) - 1

d = 1
s = set()

def dfs(x):
  if sz(lst) > 75:
    return 
  if x == 0:
    # s.add(d)
    # raise Exception
    # print(2)

    n = lst[0]
    m = 0
    edge = []
    for i in range(1, n + 1):
      for j in range(i + 1, n + 1):
        edge.append([i, j])
    for k in lst[1:]:
      n += 1
      for i in range(1, k + 1):
        edge.append([i, n])
    m = len(edge)
    print('{} {}'.format(n, m))
    for i, j in edge:
      print('{} {}'.format(i, j))
    exit(0)

  if sz(lst) == 0:
    for i in range(len(c4) - 1, 3, -1):
      if x < c4[i]:
        continue
      lst.append(i)
      dfs(x - c4[i])
      lst.pop()
  else:
    for i in range(lst[-1], 2, -1):
      if x < c3[i]:
        continue
      lst.append(i)
      dfs(x - c3[i])
      lst.pop()


T = int(input())
dfs(T)

C++ 解法, 执行用时: 25ms, 内存消耗: 484K, 提交时间: 2021-10-08 14:59:27

#include<iostream>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<(int)b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#include<queue>
using namespace std;
typedef int64_t ll;
const int maxn=1e3+9;
int C4[maxn],C3[maxn],k,cpgn;
int deg[9];
void dfs(int v,int d,int num){
	if(d==5||v==0){
		if(v) return;
		typedef pair<int,int> pii;
		vector<pii> ans;
		for(int i=1;i<=cpgn;i++) for(int j=1;j<i;j++)
			ans.push_back({i,j});
		for(int i=0;i<d;i++){
			for(int j=1;j<=deg[i];j++) ans.push_back({71+i,j});
		}
		printf("75 %d\n",(int)ans.size());
		for(auto [u,v]:ans) printf("%d %d\n",u,v);
		exit(0);
	}
	for(int i=1;i<=num;i++){
		if(C3[i]>v) break;
		deg[d]=i;
		dfs(v-C3[i],d+1,i);
	}
}
int main(){
	for(int i=2;i<=80;i++){
		C4[i]=i*(i-1)*(i-2)*(i-3)/24;
		C3[i]=i*(i-1)*(i-2)/6;
	}
	scanf("%d",&k);
	for(cpgn=2;C4[cpgn+1]<=k&&cpgn<70;cpgn++) ;
	k-=C4[cpgn];
	dfs(k,0,cpgn);
	exit(1);
}

C++14(g++5.4) 解法, 执行用时: 210ms, 内存消耗: 133724K, 提交时间: 2018-08-10 18:25:24

#include <bits/stdc++.h>

int a[9999],b[9999],c4[99],c3[99],n,m,K,i,j,k,g,A;
short r[71][500001],f[71][500001];

int main(){
	c4[4]=1;
	for(i=5;i<71;i++)
		c4[i]=c4[i-1]*i/(i-4);
	c3[3]=1;
	for(i=4;i<71;i++)
		c3[i]=c3[i-1]*i/(i-3);
	r[2][0]=-1;
	for(i=3;i<71;i++)
		for(memcpy(r[i],r[i-1],sizeof r[i]),memcpy(f[i],f[i-1],sizeof f[i]),j=0;j<500001;j++)
			if(r[i][j]&&(k=j+c3[i])<500001&&(g=f[i][j]+1)<71&&(!r[i][k]||g<f[i][k]))
				r[i][k]=i,f[i][k]=g;
	scanf("%d",&K);
	for(A=70;A>3;A--)
		if((k=K-c4[A])>=0&&r[A][k]&&A+f[A][k]<76){
			for(n=A,i=2;i<=A;i++)
				for(j=1;j<i;j++)
					m++,a[m]=i,b[m]=j;
			while(k)
				for(n++,g=r[A][k],k-=c3[g],i=1;i<=g;i++)
					m++,a[m]=n,b[m]=i;
			printf("%d %d\n",n,m);
			while(m--)
				printf("%d %d\n",a[m+1],b[m+1]);
			break;
		}
	return 0;
}