2016.6.10 深度优先搜索练习

1.1004 四子连棋

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

输入描述 Input Description

从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。

输出描述 Output Description

用最少的步数移动到目标棋局的步数。

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

  1 #define N 5
  2 #include<iostream>
  3 using namespace std;
  4 #include<cstdio>
  5 char jz[N][N];
  6 struct Q{
  7     int x,y;
  8 }q[2];
  9 int xx[]={1,-1,0,0};
 10 int yy[]={0,0,1,-1};
 11 long long sum=100;/*假设一个最大步数，一开始设定太大了，直接爆了栈空间*/
 12 int t=-1;
 13 bool check()
 14 {
 15     for(int i=1;i<=4;++i)
 16     {
 17         char s=jz[i][1];
 18         bool biaozhi=true;
 19         for(int j=2;j<=4;++j)
 20         {
 21             if(jz[i][j]!=s)
 22             {
 23                 biaozhi=false;
 24                 break;
 25              } 
 26         }
 27         if(biaozhi) return true;
 28     }
 29     for(int i=1;i<=4;++i)
 30     {
 31         char s=jz[1][i];
 32         bool biaozhi=true;
 33         for(int j=2;j<=4;++j)
 34         {
 35             if(jz[j][i]!=s)
 36             {
 37                 biaozhi=false;
 38                 break;
 39              } 
 40         }
 41         if(biaozhi) return true;
 42     }
 43     bool biaozhi=true;
 44     char s=jz[1][1];
 45     for(int i=2;i<=4;++i)
 46     {
 47         if(jz[i][i]!=s)
 48         {
 49             biaozhi=false;
 50             break;
 51         }
 52     }
 53     if(biaozhi) return true;
 54     biaozhi=true;
 55     s=jz[1][4];
 56     for(int i=2;i<=4;++i)
 57     {
 58         if(jz[i][5-i]!=s)
 59         {
 60             biaozhi=false;
 61             break;
 62         }
 63     }
 64     if(biaozhi) return true;
 65     return false;
 66 }
 67 void dfs(bool fla,long long bushu)
 68 {
 69     if(bushu>=sum) return;
 70     if(check())
 71     {
 72         sum=min(sum,bushu);
 73         return;
 74     }
 75     for(int i=0;i<2;++i)
 76     {
 77         for(int j=0;j<4;++j)
 78         {
 79             int x1=q[i].x+xx[j],y1=q[i].y+yy[j];
 80             if(x1>=1&&x1<=4&&y1>=1&&y1<=4)
 81             {
 82                 if(fla&&jz[x1][y1]=='W')
 83                 {
 84                   swap(jz[x1][y1],jz[q[i].x][q[i].y]);
 85                   swap(x1,q[i].x);
 86                   swap(y1,q[i].y);
 87                   dfs(!fla,bushu+1);
 88                   swap(jz[x1][y1],jz[q[i].x][q[i].y]);
 89                   swap(x1,q[i].x);
 90                   swap(y1,q[i].y);
 91                 }
 92                 if(!fla&&jz[x1][y1]=='B')
 93                 {
 94                   swap(jz[x1][y1],jz[q[i].x][q[i].y]);
 95                   swap(x1,q[i].x);
 96                   swap(y1,q[i].y);
 97                   dfs(!fla,bushu+1);
 98                   swap(jz[x1][y1],jz[q[i].x][q[i].y]);
 99                   swap(x1,q[i].x);
100                   swap(y1,q[i].y);
101                 }
102             }
103         }
104     }
105 }
106 int main()
107 {
108     for(int i=1;i<=4;++i)
109     {  
110         scanf("%s",jz[i]+1);
111         for(int j=1;j<=4;++j)
112         {
113             if(jz[i][j]=='O')
114             {
115               ++t;
116               q[t].x=i;q[t].y=j;
117             }
118         }
119     }
120     //swap(q[0],q[1]);
121     bool flag[]={true,false};
122        for(int j=0;j<2;++j)
123        dfs(flag[j],0);
124     cout<<sum<<endl;
125     return 0;
126 }

2.1008 选数

2002年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
　　　　3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
　　现在，要求你计算出和为素数共有多少种。
　　例如上例，只有一种的和为素数：3＋7＋19＝29）。

输入描述 Input Description

　键盘输入，格式为：
　　n , k （1<=n<=20，k＜n）
　　x1,x2，…,xn （1<=xi<=5000000）

输出描述 Output Description

屏幕输出，格式为：
　　一个整数（满足条件的种数）。

样例输入 Sample Input

4 3
3 7 12 19

样例输出 Sample Output

数据范围及提示 Data Size & Hint

（1<=n<=20，k＜n）
（1<=xi<=5000000）

 1 /*顺便复习Miller_rabin算法*/
 2 #define N 21
 3 #include<iostream>
 4 using namespace std;
 5 #include<cstdio>
 6 #include<cstdlib>
 7 #include<ctime>
 8 typedef long long ll;
 9 int a[N],n,k;
10 ll ans=0;
11 void input()
12 {
13     scanf("%d%d",&n,&k);
14     for(ll i=1;i<=n;++i)
15       scanf("%d",&a[i]);
16 }
17 ll quick_mod(ll a,ll b,ll c)
18 {
19     ll ans=1;
20     a%=c;
21     while(b)
22     {
23         if(b&1)
24         {
25             b--;
26             ans=(ans*a)%c;;
27         }
28         a=(a*a)%c;
29         b>>=1;
30     }
31     return ans;
32 }
33 bool Miller_rabin(ll n)
34 {
35     if(n==2) return true;
36     if(n<=1||!(n&1)) return false;
37     ll u=n-1,t=0;
38     while(!(u&1))
39     {
40         u>>=1;
41         t++;
42     }
43     for(ll i=1;i<=10;++i)
44     {
45         ll x=rand()%(n-1)+1;
46         x=quick_mod(x,u,n);
47         for(ll j=0;j<t;++j)
48         {
49             ll y=quick_mod(x,2,n);
50             if(y==1&&x!=1&&x!=n-1)
51               return false;
52             x=y;
53         }
54         if(x!=1) return false;
55     }
56     return true;
57 }
58 void dfs(ll xh,ll sum,ll djg)
59 {
60     if(djg==k)
61     {
62         if(Miller_rabin(sum))
63           ans++;
64         return;
65     }
66     if(n-xh<k-djg) return;
67     for(ll i=1;i<=n;++i)
68     {
69         if(xh+i<=n) dfs(xh+i,sum+a[xh+i],djg+1);
70         else break;
71     }
72 }
73 int main()
74 {
75     srand(time(0));
76     input();
77     for(ll i=1;i<=n-k+1;++i)
78     {
79         dfs(i,a[i],1);
80     }
81     cout<<ans<<endl;
82     return 0;
83 }

3.1005 生日礼物

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

9月12日是小松的朋友小寒的生日。小松知道小寒特别喜欢蝴蝶，所以决定折蝴蝶作为给小寒的生日礼物。他来到了PK大学最大的一家地下超市，在超市里，小松找到了n种可以用来折纸的本子。每种类型的本子里有若干不同颜色的纸若干张，当然同种类型的本子一定是完全一样的，而不同种类型的本子不一定完全不一样。他统计了一下，这里总共有n种不同类型的可以用来折纸的本子，每种本子各有bi本，所有的纸中有m种颜色是小寒所喜欢的颜色。小松希望他折的每种颜色的蝴蝶的数目是一样的。换句话说，小松必须折m*k只蝴蝶，其中k代表每种颜色蝴蝶的数目，这个数由小松自己来决定。但是小松又不能浪费纸，也就是说他买的本子中，只要是小寒喜欢的颜色的纸都要被折成蝴蝶。于是问题来了，每种类型的本子应该各买多少本，才能折出这m*k只蝴蝶呢？当然，由于小松是个很懒的人，他希望折的蝴蝶数目越少越好，只要表达了心意就可以了（也就是不能1只也不折）。而如果小松总共必须折1000只以上的蝴蝶才能满足要求，那么他就宁愿换一种礼物的方案了。

输入描述 Input Description

输入的第一行包含2个整数n（1≤n≤8），m（1≤m≤10）。表示有n种不同类型的本子和m种小寒喜欢的颜色。接下来一个n*m的矩阵。第i行第j列的整数aij表示在第i种类型的本子中包含小寒喜欢的颜色j的纸有aij（1≤aij≤100）张。再接下来的一排n个整数b1到bn，表示每种颜色的本子在超市中有多少本（1≤bi≤5）。

输出描述 Output Description

输出包含一个整数，表示小松最少需要折的蝴蝶数目，如果该数目超过1000，则输出”alternative!”。（由于可能存在多种买本子的方案，所以这里就不要求输出具体方案了）

样例输入 Sample Input

2 3

2 1 2

4 8 4

5 5

样例输出 Sample Output

  1 #define N 11
  2 #include<iostream>
  3 using namespace std;
  4 #include<cstdio>
  5 int b[N],jz[N][N],n,m,a[N];
  6 int flag=false;
  7 void input()
  8 {
  9     scanf("%d%d",&n,&m);
 10     for(int i=1;i<=n;++i)
 11       for(int j=1;j<=m;++j)
 12       scanf("%d",&jz[i][j]);
 13     for(int i=1;i<=n;++i)
 14     scanf("%d",&b[i]);
 15 }
 16 bool check(int xz)
 17 {
 18     for(int j=1;j<=m;++j)
 19       if(a[j]!=xz) return false;
 20     return true;
 21 }
 22 void dfs(int k,int xz)
 23 {
 24     if(check(xz))
 25     {
 26         flag=true;
 27         return;
 28     }
 29     if(k==n) return;
 30     for(int i=k+1;i<=n;++i)
 31     {
 32         int j;
 33         int fla=false;
 34       for(int l=0;l<=b[i];l++)
 35       {
 36           for(j=1;j<=m;++j)
 37         {
 38             a[j]+=l*jz[i][j];
 39             if(a[j]>xz)
 40             {
 41                 fla=true;
 42                 break;
 43             }
 44         }
 45         if(fla)
 46         {
 47             for(int g=1;g<=j;++g)
 48                  a[g]-=l*jz[i][g];
 49                break;
 50         }
 51         dfs(i,xz);
 52         if(flag) return; 
 53         for(j=1;j<=m;++j)
 54         {
 55             a[j]-=jz[i][j]*l;
 56         }
 57       }
 58     }
 59 }
 60 int main()
 61 {
 62     input();
 63     int k;
 64     for(k=1;;++k)
 65     {
 66       int fla=false;
 67       for(int i=1;i<=n;++i)
 68       {
 69           int j;
 70       for(int l=0;l<=b[i];l++)
 71 /*枚举从0开始表示这个本子可以买，也可以不买*/
 72       {
 73           for(j=1;j<=m;++j)
 74         {
 75             a[j]+=l*jz[i][j];
 76             if(a[j]>k)
 77             {
 78                 fla=true;
 79                 break;
 80             }
 81         }
 82         if(fla)
 83         {
 84             for(int g=1;g<=j;++g)
 85                  a[g]-=l*jz[i][g];
 86                break;
 87         }
 88         dfs(i,k);
 89         for(j=1;j<=m;++j)
 90         {
 91             a[j]-=jz[i][j]*l;
 92         }
 93        }
 94       }
 95         if(k*m>1000)
 96         {
 97              printf("alternative!
");
 98              return 0;
 99         }
100         if(flag) break;
101     }
102     printf("%d
",m*k);
103     return 0;
104 }