学步园

张贴各种代码，仅供我来膜拜。。

先贴[TOJ]1070 Ouroboros Snake 的

1.宝哥的构造法，0.00s，在TOJ所有人的代码中排行第三

#include<cstdio><br /> #include<cstring><br /> int va[32800];<br /> bool hs[32800];<br /> int ca(int ans,int n){<br /> if(ans>n/2) ans-=n/2;<br /> if(!hs[ans*2]) {hs[ans*2]=1;return ans*2;}<br /> else {<br /> hs[ans*2+1]=1;<br /> return ans*2+1;<br /> }<br /> }<br /> int main(){<br /> int n,k,i,j,ans,t;<br /> while(scanf("%d%d",&n,&k)&&(n+k)){<br /> memset(va,-1,sizeof(va[0])*(1<<n));<br /> memset(hs,0,sizeof(hs[0])*(1<<n));<br /> va[0]=0;<br /> hs[0]=1;<br /> t=ans=1<<(n-1);<br /> for(i=(1<<n)-1,j=0;j<n;i--,j++){<br /> va[i]=ans;<br /> hs[ans]=1;<br /> ans+=(t>>1);<br /> t>>=1;<br /> }<br /> if(va[k]>-1) {printf("%d/n",va[k]);continue;}<br /> ans=0;<br /> for(i=1;i<=k;i++) ans=ca(ans,(1<<n));<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }<br />

2.我的欧拉回路法，改自我[TOJ]1416 Catenyms的代码
，1.99s，pku超时，排行最后一名。

#include<stdio.h><br /> #include<string.h><br /> #include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> #define MAXN 32770<br /> struct node{<br /> int a,b,num;<br /> }our[MAXN];<br /> int path[MAXN],n,t,k,temp;<br /> bool f[MAXN],flag[MAXN];<br /> int ans[16][MAXN];<br /> void find_path_d(int now,int& step){<br /> for (int i=0;i<temp;i++)<br /> if(our[i].a==now&&!f[i]){<br /> f[i]=1;<br /> find_path_d(our[i].b,step);<br /> path[step++]=i;<br /> }<br /> }<br /> void save(int cnt,int k){<br /> for(int i=cnt-1,j=0;i>=0;i--,j++) {ans[k][j]=our[path[i]].num;}//printf("%d ",our[path[cnt]].num);}<br /> //printf("/n");<br /> }<br /> void solve(){<br /> int i,j,cnt;<br /> temp=1<<15;<br /> for(j=0;j<temp;j++) our[j].num=j;<br /> for(i=1;i<16;i++){<br /> memset(f,0,sizeof(f));<br /> temp=1<<i;<br /> for(j=0;j<temp;j++){<br /> our[j].a=j>>1;<br /> our[j].b=j&(~(1<<(i-1)));<br /> //printf("num=%d/n",our[i].num);<br /> //printf(" a=%d ",our[i].a);print_bit(our[i].a);<br /> //printf(" b=%d ",our[i].b);print_bit(our[i].b);<br /> }cnt=0;<br /> find_path_d(0,cnt);<br /> save(cnt,i);<br /> }<br /> }<br /> /*<br /> void print_bit(int num){<br /> int i=0,list[MAXN];<br /> while(num){<br /> list[i++]=num%2;<br /> num/=2;<br /> }<br /> while(i--) printf("%d",list[i]);<br /> printf("/n");<br /> }*/<br /> int main(){<br /> int i,j;<br /> solve();<br /> while(scanf("%d%d",&n,&k),n||k){<br /> printf("%d/n",ans[n][k]);<br /> }<br /> //system("pause");<br /> return 0;<br /> }<br />

3.DFS法，下述强大解题报告所附代码改编而成，0.00s

#include<stdio.h><br /> #include<string.h><br /> #define MAXN 32770<br /> int ans[16][MAXN],n;<br /> int f[MAXN],flag;<br /> void dfs(int k,int num){<br /> int next;<br /> f[num]=1;<br /> ans[n][k]=num;<br /> next=(num<<1)%(1<<n);<br /> if(flag&&!f[next]) dfs(k+1,next);<br /> next=(num<<1)%(1<<n)+1;<br /> if(flag&&!f[next]) dfs(k+1,next);<br /> f[num]=0;<br /> if(k==(1<<n)-1) flag=0;<br /> }<br /> void solve(){<br /> int i;<br /> memset(ans,0,sizeof(0));<br /> for(i=1;i<16;i++){<br /> n=i;<br /> memset(f,0,sizeof(f[0])*(1<<n));<br /> flag=1;<br /> dfs(0,0);<br /> }<br /> }<br /> int main(){<br /> int i,j,k;<br /> solve();<br /> while(scanf("%d%d",&n,&k),n||k){<br /> printf("%d/n",ans[n][k]);<br /> }<br /> return 0;<br /> }<br />

4.最最强大的DFS+DP+欧拉回路法，虽然内存用得有点多，可是代码中体现的思想令我折服。。改编自Roba的代码，0.00s。

#include<iostream><br /> #include<cstring><br /> #include<cstdio><br /> #define MAXN 1 << 15<br /> using namespace std;<br /> int pns;<br /> int ans[16][MAXN];<br /> int mp[16][MAXN][2],tk[MAXN];<br /> void build(int k)<br /> {<br /> int i,tmp;<br /> for(i=0;i< (1<<k);i++)<br /> {<br /> tmp=(i & ((1<< (k-1))-1));<br /> mp[k][i][0]=tmp<<1;<br /> mp[k][i][1]=mp[k][i][0]+1;<br /> }<br /> }<br /> void dfs(int k,int p)<br /> {<br /> if(tk[mp[k][p][0]]==0){<br /> tk[mp[k][p][0]]=1;<br /> dfs(k,mp[k][p][0]);<br /> ans[k][pns++]=mp[k][p][0];<br /> }<br /> if(tk[mp[k][p][1]]==0){<br /> tk[mp[k][p][1]]=1;<br /> dfs(k,mp[k][p][1]);<br /> ans[k][pns++]=mp[k][p][1];<br /> }<br /> }<br /> void init()<br /> {<br /> int i;<br /> for(i=1;i<=15;i++)<br /> {<br /> memset(tk,0,sizeof(tk));<br /> pns=0;<br /> tk[0]=1;<br /> build(i);<br /> dfs(i,0);<br /> ans[i][pns++]=0;<br /> }<br /> }<br /> int main()<br /> {<br /> int i;<br /> init();<br /> int n,k;<br /> while(scanf("%d %d",&n,&k) && ( n || k))<br /> {<br /> int kk=1<<n;<br /> printf("%d/n",ans[n][kk-k-1]);<br /> }<br /> return 0;<br /> }<br />

这里有篇1070的强大的解题报告：http://hi.baidu.com/zab08/blog/item/914d6a89944952bb0f2444c4.html

然后是【TOJ】3381  DeBruijin

做法与1070类似的，或者就是从那改编而成？

1.我改编自上述代码3，00.02s

#include<stdio.h><br /> #include<string.h><br /> #include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> #define MAXN 5000<br /> int ans[12][MAXN],n;<br /> bool f[MAXN],flag;<br /> void dfs(int k,int num){<br /> int next;<br /> f[num]=1;<br /> ans[n][k]=num;<br /> next=(num<<1)%(1<<n);<br /> if(flag&&!f[next]) dfs(k+1,next);<br /> next=(num<<1)%(1<<n)+1;<br /> if(flag&&!f[next]) dfs(k+1,next);<br /> f[num]=0;<br /> if(k==(1<<n)-1) flag=0;<br /> }<br /> void solve(){<br /> int i;<br /> memset(ans,0,sizeof(0));<br /> for(i=1;i<12;i++){<br /> n=i;<br /> memset(f,0,sizeof(f[0])*(1<<n));<br /> flag=1;<br /> dfs(0,0);<br /> }<br /> }<br /> int main(){<br /> int i,j,k;<br /> solve();<br /> while(scanf("%d",&k)!=EOF){<br /> printf("%d ",1<<k);<br /> for(i=0;i<k;i++) printf("0");<br /> for(i=1;i<(1<<k)-(k-1);i++) printf("%d",ans[k][i]&1);<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />

2.kobe改编自Roba的，与上面4类似
，0.00s

#include<iostream><br /> #include<cstring><br /> #include<cstdio><br /> #include<map><br /> #define MAXN 1 << 11<br /> using namespace std;<br /> int pns;<br /> int tk[MAXN];<br /> int ans[MAXN];<br /> int mat[MAXN][2];<br /> void build(int n)<br /> {<br /> int i,j;<br /> int tmp;<br /> for(i=0;i<(1<<n);i++)<br /> {<br /> tmp=(i & ((1<<(n-1))-1));<br /> mat[i][0]=tmp<<1;<br /> mat[i][1]=mat[i][0]+1;<br /> }<br /> }<br /> void dfs(int p)<br /> {<br /> if(tk[mat[p][0]]==0){<br /> tk[mat[p][0]]=1;<br /> dfs(mat[p][0]);<br /> ans[pns++]=mat[p][0];<br /> }<br /> if(tk[mat[p][1]]==0){<br /> tk[mat[p][1]]=1;<br /> dfs(mat[p][1]);<br /> ans[pns++]=mat[p][1];<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> int k;<br /> int i;<br /> memset(tk,0,sizeof(tk));<br /> build(n);<br /> pns=0;<br /> tk[0]=1;<br /> dfs(0);<br /> ans[pns++]=0;<br /> printf("%d ",1<<n);<br /> for(i=0;i<n;i++)<br /> printf("0");<br /> for(i=pns-2;i>n-2;i--)<br /> {<br /> k=(1&(ans[i]));<br /> k=k+'0';<br /> printf("%c",k);<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />