Home > Old Blog Posts > USACO 1.5.4 Checker Challenge

USACO 1.5.4 Checker Challenge


这题我偷懒了,直接用M67牛教导的位运算。

但此牛故意留了一个空:还得输出前3个解呢

于是很多人就去再写一个新的dfs,找出3个解……

其实不用这样大大滴。

仔细分析位运算的dfs,设置了一个变量记录最右边的一个1,这就是当前所摆的位置,那么只要把这个位置存储

下来就行了,具体见程序。

代码:

/*
ID: dementr1
PROG: checker
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“checker.in”);
ofstream fout(“checker.out”);
int upperlim,sum=0,counter=0,list[100000][14],N;
int log(int n)
{
int tmp=1,num=1;
while(tmp!=n)
{
tmp*=2;
num++;
}
return num;
}
void test(int row,int ld,int rd,int a[],int nn)
{
int pos,p,loger;
if(row!=upperlim)
{
pos=(upperlim)&(~(row|ld|rd));
while(pos!=0)
{
p=pos&(-pos);
pos=pos-p;
loger=log(p);
a[nn]=loger;
test(row+p,(ld+p)<< 1,(rd+p) >> 1,a,nn+1);
}
}
else
{
sum++;
for(int i=0;i<N;i++)
list[counter][i]=a[i];
counter++;
}
}
int main()
{
int a[14]={},i,j;
fin>>N;
upperlim=(1<<N)-1;
test(0,0,0,a,0);
for(i=0;i<3;i++)
{
for(j=0;j<N-1;j++) fout<<list[i][j]<<” “;
fout<<list[i][j]<<endl;
}
fout<<sum<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: