首页 > 代码库 > POJ 3139 Life Forms
POJ 3139 Life Forms
枚举。
看了这个方法:$http://www.cppblog.com/shiming413/archive/2008/12/21/29671.html$
将数字归类的地方不能用$vector$,会超时。$vector$换成数组就可以过,类似于邻接表。
因为题目给出的$16$个数字都是不同的,所以时间复杂度相对还比较低。
下面这组数据是极限数据,我的跑了$3800$$ms$。但测试数据中不会出现这样的数据。
$5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}int a[20],b[20];LL h[(1<<16)+10];struct X{ int b, nx;}e[50000];int g[11000],k;void add(int a,int b){ e[k].b=b; e[k].nx=g[a]; g[a]=k++;}int main(){ int cas=1; while(~scanf("%d",&a[0])) { if(a[0]==0) break; for(int i=1;i<=15;i++) scanf("%d",&a[i]); k=0; memset(g,-1,sizeof g); for(int i=0;i<(1<<16);i++) { int t=i,cnt=0; for(int j=0;j<16;j++) if(i&(1<<j)) b[cnt++]=j; if(cnt!=4) continue; sort(b,b+4); do { add(4*a[b[0]]+3*a[b[1]]+2*a[b[2]]+1*a[b[3]],i); }while(next_permutation(b,b+4)); } memset(h,0,sizeof h); for(int i=1;i<=10500;i++) { for(int j=g[i];j!=-1;j=e[j].nx) { for(int d=e[j].nx;d!=-1;d=e[d].nx) { int f1=e[d].b,f2=e[j].b; if(f1&f2) continue; h[f1^f2]++; } } } LL ans=0; for(int i=0;i<(1<<16);i++) { int t=i,cnt=0; for(int j=0;j<16;j++) if(i&(1<<j)) cnt++; if(cnt!=8) continue; ans=ans+h[i]*h[(1<<16)-1-i]; } printf("Case %d: %lld\n",cas++,ans/2); } return 0;}
POJ 3139 Life Forms
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。