代码
比这篇新的文章:
checker.bitset.cpp
比这篇旧的文章: checker.final.cpp
作者: xpycc, 点击228次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: checker.final.cpp
checker.combine.cpp
语言: C++, 标签: 无 2008/08/22发布 3个月前更新作者: xpycc, 点击228次, 评论(0), 收藏者(0)
C++语言: checker.combine.cpp
01 /*
02 ID:xpycc1
03 PROG:checker
04 LANG:C++
05 */
06
07 #include<fstream>
08 #define maxn 13
09 using namespace std;
10 ifstream fin("checker.in");
11 ofstream fout("checker.out");
12
13 int n,op,opd,sum=0,res[maxn],gx,gy,g1,g2,gx0,g10,g20;
14
15 void find(){
16 int i;
17 for(i=0;i<n-1;++i)
18 fout<<res[i]<<" ";
19 fout<<res[n-1]<<endl;
20 }
21
22 void solve(int x,int k1,int k2,int y){
23 int pos=~(x|k1|k2),p,i;
24 if(x==op){
25 ++sum;
26 find();
27 return;
28 }
29 for(i=p=1;p<op;p<<=1,++i)
30 if(pos&p){
31 if(sum<3) res[y]=i;
32 solve(x+p,(k1+p)<<1,(k2+p)>>1,y+1);
33 if(sum==3) return;
34 }
35 }
36
37 void solve(int x,int k1,int k2){
38 int pos=op&~(x|k1|k2),p;
39 if(x==op){
40 ++sum;
41 return;
42 }
43 while(pos){
44 p=pos&-pos; pos-=p;
45 solve(x+p,(k1+p)<<1,(k2+p)>>1);
46 }
47 }
48
49 void solve0(int x,int k1,int k2,int y){
50 int pos=op&~(x|k1|k2),p;
51 if(x==op){
52 ++sum;
53 return;
54 }
55 if(y==opd+1 || y==gy){
56 solve0(x,k1<<1,k2>>1,y+1);
57 return;
58 }
59 while(pos){
60 p=pos&-pos; pos-=p;
61 solve0(x+p,(k1+p)<<1,(k2+p)>>1,y+1);
62 }
63 }
64
65 int main(){
66 int i,j;
67 fin>>n;
68 op=(1<<n)-1;
69
70 solve(0,0,0,0); //0:OK 1:used
71
72 sum=0;
73 if(n&1){
74 opd=n>>1; gx=1<<opd;
75 for(i=2;i<=opd;++i){ //i行,d列
76 g2=gx<<(i-1); g1=gx>>(i-1); gy=i;
77 for(j=1;j<i;++j){ //d行,j列
78 gx0=1<<(n-j); g10=gx0>>opd; g20=gx0<<opd;
79 solve0(gx+gx0,g1+g10,g2+g20,1);
80 }
81 }
82 sum<<=3; gy=opd+1;
83 solve0(gx,1,1<<(n-1),1);
84 }else{
85 opd=(1<<(n>>1))-1;
86 for(i=1;i<opd;i<<=1) //half
87 solve(i,i<<1,i>>1);
88 sum<<=1;
89 }
90
91 fout<<sum<<endl;
92 return 0;
93 }
02 ID:xpycc1
03 PROG:checker
04 LANG:C++
05 */
06
07 #include<fstream>
08 #define maxn 13
09 using namespace std;
10 ifstream fin("checker.in");
11 ofstream fout("checker.out");
12
13 int n,op,opd,sum=0,res[maxn],gx,gy,g1,g2,gx0,g10,g20;
14
15 void find(){
16 int i;
17 for(i=0;i<n-1;++i)
18 fout<<res[i]<<" ";
19 fout<<res[n-1]<<endl;
20 }
21
22 void solve(int x,int k1,int k2,int y){
23 int pos=~(x|k1|k2),p,i;
24 if(x==op){
25 ++sum;
26 find();
27 return;
28 }
29 for(i=p=1;p<op;p<<=1,++i)
30 if(pos&p){
31 if(sum<3) res[y]=i;
32 solve(x+p,(k1+p)<<1,(k2+p)>>1,y+1);
33 if(sum==3) return;
34 }
35 }
36
37 void solve(int x,int k1,int k2){
38 int pos=op&~(x|k1|k2),p;
39 if(x==op){
40 ++sum;
41 return;
42 }
43 while(pos){
44 p=pos&-pos; pos-=p;
45 solve(x+p,(k1+p)<<1,(k2+p)>>1);
46 }
47 }
48
49 void solve0(int x,int k1,int k2,int y){
50 int pos=op&~(x|k1|k2),p;
51 if(x==op){
52 ++sum;
53 return;
54 }
55 if(y==opd+1 || y==gy){
56 solve0(x,k1<<1,k2>>1,y+1);
57 return;
58 }
59 while(pos){
60 p=pos&-pos; pos-=p;
61 solve0(x+p,(k1+p)<<1,(k2+p)>>1,y+1);
62 }
63 }
64
65 int main(){
66 int i,j;
67 fin>>n;
68 op=(1<<n)-1;
69
70 solve(0,0,0,0); //0:OK 1:used
71
72 sum=0;
73 if(n&1){
74 opd=n>>1; gx=1<<opd;
75 for(i=2;i<=opd;++i){ //i行,d列
76 g2=gx<<(i-1); g1=gx>>(i-1); gy=i;
77 for(j=1;j<i;++j){ //d行,j列
78 gx0=1<<(n-j); g10=gx0>>opd; g20=gx0<<opd;
79 solve0(gx+gx0,g1+g10,g2+g20,1);
80 }
81 }
82 sum<<=3; gy=opd+1;
83 solve0(gx,1,1<<(n-1),1);
84 }else{
85 opd=(1<<(n>>1))-1;
86 for(i=1;i<opd;i<<=1) //half
87 solve(i,i<<1,i>>1);
88 sum<<=1;
89 }
90
91 fout<<sum<<endl;
92 return 0;
93 }
所有评论，共0条：( 我也来说两句)