Counting 4-Cliques 牛客网多校

本文主要是介绍Counting 4-Cliques 牛客网多校，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.nowcoder.com/acm/contest/145/E

给定k 构造一个包含k个四阶完全子图的图

打表找规律可得 70阶完全图中四阶完全子图的数量略微小于1e6 所以再用剩下的五个点来凑 数量上可以满足1e6

找最大的p阶完全图 其四阶完全子图的数量小于等于k 四个for循环来枚举剩下的五个点 如何凑出k即可

#include <bits/stdc++.h>
using namespace std;int c3[100],c4[100];
int book[1000010],u[1000010],v[1000010];
int k,n,m;void init()
{int i,j;c3[3]=1;for(i=4;i<=75;i++){c3[i]=(i*c3[i-1])/(i-3);}memset(book,-1,sizeof(book));book[0]=0;for(i=3;i<=70;i++){book[c3[i]]=i;}c4[4]=1;for(i=5;i<=75;i++){c4[i]=(i*c4[i-1])/(i-4);}
}int main()
{int i,j,p,a,b,c,d,e,tot,flag;init();scanf("%d",&k);for(i=4;i<=70;i++){if(c4[i]<=k) p=i;else break;}k-=c4[p];flag=0;for(a=2;a<=70;a++){for(b=2;b<=70;b++){for(c=2;c<=70;c++){for(d=2;d<=70;d++){if(c3[a]+c3[b]+c3[c]+c3[d]<=k&&book[k-(c3[a]+c3[b]+c3[c]+c3[d])]!=-1){e=book[k-(c3[a]+c3[b]+c3[c]+c3[d])];flag=1;break;}}if(flag) break;}if(flag) break;}if(flag) break;}tot=0;for(i=1;i<=p;i++){for(j=i+1;j<=p;j++){tot++;u[tot]=i,v[tot]=j;}}for(i=1;a!=2&&i<=a;i++){tot++;u[tot]=i,v[tot]=71;}for(i=1;b!=2&&i<=b;i++){tot++;u[tot]=i,v[tot]=72;}for(i=1;c!=2&&i<=c;i++){tot++;u[tot]=i,v[tot]=73;}for(i=1;d!=2&&i<=d;i++){tot++;u[tot]=i,v[tot]=74;}for(i=1;i<=e;i++){tot++;u[tot]=i,v[tot]=75;}printf("%d %d\n",75,tot);for(i=1;i<=tot;i++){printf("%d %d\n",u[i],v[i]);}return 0;
}

 

这篇关于Counting 4-Cliques 牛客网多校的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---