一、枚举

1、完美立方

/* 	完美立方a^3=b^3+c^3+d^3// a大于b c d// b<c<d*/
#include <iostream>  int main()
{int a,b,c,d; int N = 24;//scanf("%d", &N );for(a=2; a<=N; a++ )           //a的范围 [2,N]{for(b=2; b<a; b++){        //b的范围[2,a-1]for(c=b; c<a; c++){    //c的范围[b,a-1]for(d=c; d<a; d++){//d的范围[c,a-1]if(a*a*a==b*b*b+c*c*c+d*d*d)printf("Cube = %d,\tTriple = (%d,%d,%d)\n",a,b,c,d);}}}}	return 0;
}

2、生理周期

/* 	生理周期p 23  e 28  i 331、d 之后的日子 k，从k=d+1开始计算，到0 == (k-p)% 232、再到0==(k-e)%28，每次递增 23，因为应满足上面的条件3、再到0==(k-i)%33，每次递增23*28k直到21252
*/
#include <iostream>  
//#define N 21252int main()
{	//freopen("D:\\test.txt","r",stdin);int p,e,i,d,k,caseNo = 0; //caseNo记录第几次while( std::cin >> p >> e >> i >>d && p!=-1 ){++caseNo;for(k=d+1; (k-p)%23; k++ );  //k++  		//找体力高分for(; (k-e)%28; k+=23 );     //k+=23        //找情商高分//同时是体力高分for(; (k-i)%33; k+=23*28 );  //k+=23*28     //找智力高分//同时是体力、情商高分（最小公倍数）std::cout << "Case " << caseNo << ": the next triple peak occures in " <<k-d << "days.\n";}return 0;
}
/*  
输入样例：
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1  
*/

测验与作业

1、特殊密码锁

#include <iostream>  
#include <cstdio>
using namespace std;  void Flip(string &str,int i)
{if (str[i]=='1')str[i]='0';else str[i]='1';
}
int main()
{string str1="",str2="";cin>>str1>>str2;int cnt=0; for(int i =str1.length()-1;i>=0;i--){if(str1[i]!=str2[i]){cnt++;if(i==str1.length()-1){Flip(str1,i);if(i-1>=0)Flip(str1,i-1);	}else if(i==0){Flip(str1,0);Flip(str1,1);}else{Flip(str1,i);if(i-1>=0)Flip(str1,i-1);if(i-2>=0)Flip(str1,i-2);}}if(string(str1)==string(str2))break;} if(string(str1)!=string(str2))cout<<"impossible";else cout<<cnt;return 0;
}

2、拨钟问题

#define TABLE_LEN 5#include<stdio.h>const int table[10][TABLE_LEN]={{},{1,2,4,5},{1,2,3},{2,3,5,6},{1,4,7},{2,4,5,6,8},{3,6,9},{4,5,7,8},{7,8,9},{5,6,8,9}};int state[10];
int times[10],min=0x7FFFFFFF,ans_times[10];
bool isFirst=true;void deal(int k,int total)
{if (k==10){for (int i=1;i<=9;i++)if (state[i]&3)return;if (total<min){min=total;for (int i=1;i<=9;i++)ans_times[i]=times[i];}return;} for (times[k]=0;times[k]<4;times[k]++){for (int i=0;i<TABLE_LEN;i++)state[table[k][i]]+=times[k];deal(k+1,total+times[k]);for (int i=0;i<TABLE_LEN;i++)state[table[k][i]]-=times[k];}return;
}int main()
{for (int i=1;i<=9;i++)scanf("%d",&state[i]);deal(1,0);for (int i=1;i<=9;i++)for (int j=0;j<ans_times[i];j++){if (isFirst)isFirst=false;elseprintf(" ");printf("%d",i); }printf("\n");return 0; 
}

3、全排列

#include <iostream>
#include <string>
using namespace std;
void permute1(string prefix, string str)
{if(str.length() == 0) cout << prefix << endl;else	for(int i = 0; i < str.length(); i++)permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length()));	
}
int main()
{string str;cin>>str;permute1("",str);
}

4、2的幂次方表示

#include<stdio.h>
/*定义函数*/
void cimi(int n){int num=0;int i=0,j,k;int a[32];//数组定义为局部变量 while(n){//若n不是0 ,逐步将n简化,放到数组a中 j=n%2;//n余2运算 if(j==1)a[num++]=i;//存储第几次是1i++;n/=2;}for(i=num-1;i>=0;i--){//逆序遍历数组a if(a[i]==0)printf("2(0)");else if(a[i]==1)printf("2");else if(a[i]==2)printf("2(2)");else if(a[i]>2){printf("2(");cimi(a[i]);//递归调用 printf(")");}if(i!=0)printf("+");}
} 
int main(){int n;scanf("%d",&n);//输入ncimi(n);//调用函数 return 0;//结束程序 
}

5、Boolean Expressions

#include <iostream>
#include <cstdio>
using namespace std;char wholeExp[200];
bool exp();
bool factor();
bool item();
int ptr = 0;
bool exp() 
{bool result = item();while(wholeExp[ptr] == '|' ) {++ptr;result = result | item();}return result;
}
bool item() 
{bool result = factor();while(wholeExp[ptr] == '&') {++ptr;result = result & factor();}return result;
}
bool notExp()
{//wholeExp[ptr] == '!' when called;ptr++;bool result;switch(wholeExp[ptr]) {case 'F':++ptr;return true;break;case 'V':++ptr;return false;break;case '(':++ptr;result = exp();++ptr; //skip ')'return !result;break;case '!':result = notExp();return !result;break;}
}
bool factor() 
{bool result;switch( wholeExp[ptr]) {case 'F':++ptr;return false;break;case 'V':++ptr;return true;break;case '(':++ptr;result = exp();++ptr;return result;break;case '!':result = notExp();return result;break;}
}
int main()
{char c;int i = 0;int t = 1;int n = EOF + 1;while(n != EOF) {n = scanf("%c",&c);if( n == EOF || c == '\n') {wholeExp[i] = 0;if( i > 0) {ptr = 0;bool r = exp();if (r) {printf("Expression %d: V\n",t++);}elseprintf("Expression %d: F\n",t++);}i = 0;}else if( c != ' ')wholeExp[i++] = c;}return 0;
}

6、简单的整数划分问题

#include <iostream>
using namespace std;
int ways(int n,int i)
{if( n == 0)return 1;if( i == 0)return 0;if( i <= n)return ways(n-i,i) + ways(n,i-1); //用i和不用i的情况。i可以重复使用elsereturn ways(n,i-1);
}
int main()
{int n;while(cin >> n)cout << ways(n,n) << endl;return 0;
}

7、输出前k大的数

#include <iostream>
using namespace std;void swap(int & a,int & b) //交换变量a,b值
{int tmp = a;a = b;b = tmp;
}
void QuickSort(int a[],int s,int e)
{if( s >= e)return;int k = a[s];int i = s,j = e;while( i != j ) {while( j > i && a[j] >= k )--j;swap(a[i],a[j]);while( i < j && a[i] <= k )++i;	swap(a[i],a[j]);} //处理完后，a[i] = kQuickSort(a,s,i-1);QuickSort(a,i+1,e);
}int main()
{int n;cin>>n;int a[n];int size = sizeof(a)/sizeof(int);for(int i = 0;i < size; ++i) cin>>a[i];int k;cin>>k;QuickSort(a,0,size-1);for(int i = 0 ;i<k; ++i)  {	cout << a[--size] << endl;} return 0;
}

8、求排列的逆序数

#include <iostream> 
using namespace std; 
long long cnt=0;void Merge(int a[],int s,int m, int e,int tmp[])  
{int pb = 0;  //tmp指针 int p1 = s,p2 = m+1;//前半部、后半部指针 	//归并到 tmpwhile( p1 <= m && p2 <= e) {    if( a[p1] <= a[p2])  tmp[pb++] = a[p1++];   else  {tmp[pb++] = a[p2++];cnt+=m-p1+1;}  } //前半部剩余 while( p1 <= m)  tmp[pb++] = a[p1++]; //后半部剩余  while( p2 <= e)  tmp[pb++] = a[p2++];//拷贝回原数组a  for(int i = 0;i < e-s+1; ++i)   a[s+i] = tmp[i]; 
} void MergeSort(int a[],int s,int e,int  tmp[]) 
{  if( s < e) {   int m = s + (e-s)/2;   MergeSort(a,s,m,tmp);   MergeSort(a,m+1,e,tmp);   Merge(a,s,m,e,tmp);  } 
} int main() 
{  int n;cin>>n;int a[n]; int b[n];for(int i = 0;i < n; ++i) cin>>a[i];MergeSort(a,0,n-1,b); cout << cnt<<endl; return 0; 
} 

9、拦截导弹

#include <stdlib.h>  
#include <string.h>  
#include <stdio.h>  
#define N 26  int max(int a,int b)  
{  return a > b ? a:b;  
}  int main(int argc,char* argv[])  
{  
//freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);int iElemArr[N];//保存输入的元素  int iLenArr[N];//保存以第i号元素结尾的最长非递增子序列长度  int n,iCnt = 1;  int i,j;  while(EOF!=scanf("%d",&n))  {  //接受输入信息  int iTemp = n;  while(iTemp--)  {  scanf("%d",&iElemArr[iCnt++]);  }  //int iMax= 1;  //对每个元素进行遍历  for(i = 1 ; i <= n ; i++)  {  //易错，这里需要将初始值iMax放在每次i做变动之后  int iMax = 1;  //遍历当前元素之前的元素  for(j = 1; j < i ; j++)  {  //如果前面的元素>=后面的元素，就更新以第i个元素结尾的子序列的长度  if(iElemArr[j] >= iElemArr[i])  {  iMax = max(iMax,iLenArr[j] + 1);  }  }  iLenArr[i] = iMax;//更新以第i号元素结尾的子序列的长度  }  int iMMax = -123123123;  for(i = 1 ; i <= n ; i++)  {  if(iLenArr[i] > iMMax)  {  iMMax = iLenArr[i];  }  }  printf("%d\n",iMMax);  }  
//    system("pause");  
//    getchar();  return 0;  
}  

10、Zipper

#include<stdio.h>
#include<string.h>
char a[220],b[220],c[220*2];
bool flag;
int len1,len2,len3;
void dfs(int x,int y,int len)
{if(flag)return;if(len>=len3){flag=true;return;}if(a[x]==c[len]){dfs(x+1,y,len+1);}if(b[y]==c[len])dfs(x,y+1,len+1);
}
int main()
{//freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);int t,cot=0;scanf("%d",&t);while(t--){scanf("%s%s%s",a,b,c);len1=strlen(a);len2=strlen(b);len3=strlen(c);if(len1+len2!=len3){printf("Data set %d: no\n",++cot);continue;}flag=false;if(a[len1-1]==c[len3-1]||b[len2-1]==c[len3-1]){dfs(0,0,0);}if(flag)printf("Data set %d: yes\n",++cot);elseprintf("Data set %d: no\n",++cot);}
}

11、最佳加法表达式

#include<bits/stdc++.h>  
#include<cstring>  
#include<stdlib.h>  
using namespace std;  
const int MaxLen = 55;  
const string maxv = "999999999999999999999999999999999999999999999999999999999";  
string ret[MaxLen][MaxLen];  
string num[MaxLen][MaxLen];  
int cmp(string &num1,string &num2)  
{  int l1 = num1.length();  int l2 = num2.length();  if (l1 != l2)  {  return l1-l2;  }  else  {  for (int i=l1-1; i>=0; i--)  {  if (num1[i]!=num2[i])  {  return num1[i]-num2[i];  }  }  return 0;  }  
}  
void add (string &num1,string &num2,string &num3)  
{  //加法从低位到高位相加，那么需要将字符串倒过来  int l1 = num1.length();  int l2 = num2.length();  int maxl = MaxLen,c = 0;        //c是进位标志  for (int i=0; i<maxl; i++)  {  int t;  if (i < l1 && i < l2)  {  t = num1[i]+num2[i]-2*'0'+c;  }  else if (i < l1 && i >= l2)  {  t = num1[i] - '0' + c;  }  else if (i >= l1 && i < l2)  {  t = num2[i] - '0' + c;  }  else  {  break;  }  num3.append(1,t%10+'0');  c = t/10;  }  while (c)  {  num3.append(1,c%10+'0');  c /= 10;  }  
}  
int main()  
{  //freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);int m;                  //加号数目  string str;             //输入的字符串  while(cin >> m >> str)  {  //为了之后的加法计算先将这个字符串倒过来  reverse(str.begin(),str.end());  int n = str.length();  for (int i=0; i<n; i++)  {  num[i+1][i+1] = str.substr(i,1);  }  for (int i=1; i<=n; i++) //求解对应的num[i][j]  {  for (int j=i+1; j<=n; j++)  {  num[i][j] = str.substr(i-1,j-i+1);  }  }  //当加号数目为0  for (int i=1; i<=n; i++)  {  ret[0][i] = num[1][i];  }  for (int i=1; i<=m; i++) //对于加号数目的枚举  {  for (int j=1; j<=n; j++) //对于长度的枚举  {  string minv = maxv;  string tmp;  for (int k=i; k<=j-1; k++)  {  tmp.clear();  add(ret[i-1][k],num[k+1][j],tmp);  if (cmp(minv,tmp)>0)  {  minv = tmp;  }  }  ret[i][j] = minv;  }  }  //将原先颠倒的字符串倒回来  reverse(ret[m][n].begin(),ret[m][n].end());  cout << ret[m][n] << endl;  }  return 0;  
}  

12、复杂的整数划分问题

#include<cstdio>  
#include<iostream>  
#include<cstring>  
using namespace std;  
int main() {  int n,k;  while(~scanf("%d%d",&n,&k)) {  int dp[52][52]= {0};  //第一问  dp[0][0]=1;  for(int i=1; i<=n; ++i)  for(int j=1; j<=k; ++j) {  dp[j][i]=dp[j-1][i-1];  if(i-j>=j)  dp[j][i]+=dp[j][i-j];  }  cout<<dp[k][n]<<endl;  /*第二问 设dp[n][m]表示数n划分方案中，每个数不大于m 的划分数。 划分分两种情况： 划分中有1和没有1 动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m-1]。 */  memset(dp,0,sizeof(dp));  dp[0][0]=1;  for(int i=0; i<=n; ++i)  for(int j=1; j<=n; ++j)  if(i>=j) dp[i][j]=dp[i][j-1]+dp[i-j][j-1];  else dp[i][j]=dp[i][i];  cout<<dp[n][n]<<endl;  //第3问  int g[52][52]={0},f[52][52]={0};//偶数  g[0][0]=f[0][0]=1;  for(int i=1;i<51;++i)  for(int j=1;j<=i;++j)  {  g[i][j]=f[i-j][j];  f[i][j]=f[i-1][j-1]+g[i-j][j];    }  int ans=0;  for(int i=1;i<=n;++i)  ans+=f[n][i];  cout<<ans<<endl;  }  return 0;  
}  

13、Charm Bracelet

#include<iostream>
using namespace std;const int N = 3403;
const int M = 12881;int dp[M] = {0};int max(int x, int y)
{return x > y ? x : y;
}int main()
{int n, m;int w[N], d[M];cin >> n >> m;for (int i = 1; i <= n; i++){cin >> w[i] >> d[i];}for (int i = 1; i <= n; i++){for (int j = m; j >= w[i]; j--){dp[j] = max(dp[j-w[i]] + d[i], dp[j]);}}cout << dp[m] << endl;return 0;
}

14、分蛋糕

#include<cstdio>
#include<iostream>
using namespace std;
#define N 25
#define INF 5005
int f[N][N][N];int w,h,m;
int main(){w=h=m=20;for(int i=1;i<=w;i++){for(int j=1;j<=h;j++){f[i][j][1]=i*j;for(int k=2;k<=m;k++){f[i][j][k]=INF;for(int r=1;r<i;r++){f[i][j][k]=min(f[i][j][k],max(f[r][j][k-1],(i-r)*j));for(int p=1;p<k;p++)f[i][j][k]=min(f[i][j][k],max(f[r][j][p],f[i-r][j][k-p]));}for(int c=1;c<j;c++){f[i][j][k]=min(f[i][j][k],max(f[i][c][k-1],(j-c)*i));for(int p=1;p<k;p++)f[i][j][k]=min(f[i][j][k],max(f[i][c][p],f[i][j-c][k-p]));}}}}while(scanf("%d%d%d",&w,&h,&m)&&(w||h||m)){printf("%d\n",f[w][h][m]);}return 0;
}

15、红与黑

#include<bits/stdc++.h>
using namespace std;
int a[1000][1000];int s,n,m,i,j,x,y;char c;void find(int i,int j)
{if(!a[i][j]) return;a[i][j]=0;s++;find(i-1,j);find(i+1,j);find(i,j-1);find(i,j+1);
}
int main()
{  while(1){      cin>>m>>n;if(n==0&&m==0) break;memset(a,0,sizeof(a));s=0;for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>c;if(c=='@'||c=='.') a[i][j]=1;if(c=='@') x=i,y=j;}find(x,y);cout<<s<<endl;}
}

16、A Knight’s Journey

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<stdio.h>  
#include<math.h>  
#include<string>  
#include<stdio.h>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<deque>  
using namespace std;  
#define lson k*2  
#define rson k*2+1  
#define M (t[k].l+t[k].r)/2  
#define INF 1008611111  
#define ll long long  
#define eps 1e-15  
int p[30][30];//存是否走过  
int xx[30];//存路径的x坐标  
int yy[30];  
int dirx[8]={-1,1,-2,2,-2,2,-1,1};//方向比较重要  
int diry[8]={-2,-2,-1,-1,1,1,2,2};  
int n,m,tag;  
void dfs(int x,int y,int step)  
{  if(step>=m*n)//如果走满了  {  tag=1;  }  if(tag)  {  return;  }  int i,j,sx,sy;  for(i=0;i<8;i++)//八个方向dfs搜索回溯  {  sx=x+dirx[i];  sy=y+diry[i];  if(sx>=1&&sy>=1&&sx<=m&&sy<=n&&!p[sx][sy])  {  p[sx][sy]=1;  xx[step]=sx;  yy[step]=sy;//记录路径  dfs(sx,sy,step+1);  if(tag)  return;  p[sx][sy]=0;  }  }  
}  
int main()  
{  int i,j,test,q;  scanf("%d",&test);  for(q=1;q<=test;q++)  {  scanf("%d%d",&m,&n);  memset(p,0,sizeof(p));  tag=0;  xx[0]=1;  yy[0]=1;  p[1][1]=1;  dfs(1,1,1);//起点为1,1  printf("Scenario #%d:\n",q);  if(tag)  for(i=0;i<n*m;i++)  {  printf("%c%d",'A'+yy[i]-1,xx[i]);//输出是先y再x  }  else  printf("impossible");  printf("\n");  if(q!=test)//注意格式  printf("\n");  }  return 0;  
}  

17、棋盘问题

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;char str[10][10];
bool a[10];//a[i]表示第i列是否已经放过了棋子
int ans;
int n, m;
//cnt表示行数（从0开始），val表示放棋子的个数
void dfs(int cnt, int val)
{if(val == m)//当放了m个棋子后增加一种可能{ans++;return ;}if(cnt == n) return;//超过行数时直接返回int i;dfs(cnt+1, val);for(i = 0; i < n; i++){if(str[cnt][i] == '#' && !a[i]){a[i] = 1;//标记第i列已经放了棋子dfs(cnt+1, val+1);a[i] = 0;//还原}}
}int main(void)
{while(scanf("%d%d", &n, &m), n+m>0){int i;memset(a, 0, sizeof(a));for(i = 0; i < n; i++)scanf("%s", str[i]);ans = 0;dfs(0, 0);printf("%d\n", ans);}return 0;
}

18、鸣人和佐助

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[220][210],n,m,i,j,t;
int p[4000003],q[4000003],step[4000003],k[4000003],head,tail,mp[220][210];
int x1,x2,y1,y2;
int xx[10]={1,0,-1,0},yy[10]={0,1,0,-1};
int main()
{scanf("%d%d%d\n",&n,&m,&t);for (i=1;i<=n;i++){char c[210]; gets(c);for (j=1;j<=m;j++){if (c[j-1]=='#')  f[i][j]=1;if (c[j-1]=='*')  f[i][j]=0;if (c[j-1]=='@'){  f[i][j]=0;  x1=i; y1=j;  }if (c[j-1]=='+'){ f[i][j]=0; x2=i; y2=j;}}}head=0; tail=1; p[1]=x1; q[1]=y1; step[1]=0; k[1]=t;memset(mp,-1,sizeof(mp));mp[x1][y1]=t;int ans=100000000;while (head<tail){head++;for (i=0;i<4;i++){int xl=p[head]+xx[i],yl=q[head]+yy[i];if (xl>0&&xl<=n&&yl>0&&yl<=m&&(mp[xl][yl]==-1||mp[xl][yl]<=k[head]-1))if (f[xl][yl]==0){tail++; p[tail]=xl; q[tail]=yl; step[tail]=step[head]+1; k[tail]=k[head];mp[xl][yl]=k[head];}elseif (k[head]>0){tail++; p[tail]=xl; q[tail]=yl; step[tail]=step[head]+1; k[tail]=k[head]-1;mp[xl][yl]=k[head]-1;}if (mp[x2][y2]!=-1){printf("%d",step[tail]);return 0;}}}printf("-1");return 0;
} 

19、迷宫问题

#include<iostream> 
#include<cstring> 
using namespace std;  
int map[5][5];  
int vis[5][5];  
struct node{  int x;  int y;  int pre;  
}edge[100];  
int front=0,rear=1;//队头，队尾  
int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};  
void f(int i)//倒向追踪法  
{  if(edge[i].pre!=-1)  {  f(edge[i].pre);  cout<<"("<<edge[i].x<<", "<<edge[i].y<<")"<<endl;  }  
}  
void BFS(int x,int y)  
{  edge[front].x=x;  edge[front].y=y;  edge[front].pre=-1;  while(front<rear)//队列为空时终止  {  int u;  for(u=0;u<4;u++)  {  int x=edge[front].x+dir[u][0];  int y=edge[front].y+dir[u][1];  if(x<0||x>=5||y<0||y>=5||vis[x][y]==1||map[x][y]==1)  continue;  else  {  vis[x][y]=1;  map[x][y]=1;  edge[rear].x=x;//入队  edge[rear].y=y;  edge[rear].pre=front;  rear++;  }  if(x==4&&y==4)  f(front);  }  front++;//出队  }  
}  
int main()  
{  int i,j;  for(i=0;i<5;i++)  {  for(j=0;j<5;j++)  {  cin>>map[i][j];  }  }  memset(vis,0,sizeof(vis));  cout<<"("<<"0, 0)"<<endl;  BFS(0,0);  cout<<"(4, 4)"<<endl;  return 0;  
}  

20、Pots

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 105;
const double eps = 1e-7;
bool vis[maxn][maxn];
const int dir[4][2]= {1, 0, 0, 1, -1, 0, 0, -1};
char map[maxn][maxn];int a, b, k;
struct node
{int vola, volb, step;char str[maxn][maxn];
};bool bfs()
{memset(vis, false, sizeof(vis));queue<node> que;node p, q;p.vola = 0, p.volb = 0, p.step = 0;que.push(p);vis[0][0] = 1;///vis[p.vola][p.volb] = true;while(!que.empty()){p = que.front();que.pop();if(p.vola==k || p.volb == k){cout<<p.step<<endl;for(int i=1; i<=p.step; i++)///cout<<p.str[i]<<endl;printf("%s\n",p.str[i]);return true;}///倒满 aif(p.vola == 0){q = p;q.vola = a;q.step++;strcpy(q.str[q.step], "FILL(1)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}}///把 a 中的水倒出来else if(p.vola <= a){q = p;q.vola = 0;q.step++;strcpy(q.str[q.step], "DROP(1)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}///a -> bif(p.volb < b){q = p;if(q.volb + q.vola <= b){q.volb += q.vola;q.vola = 0;}else{q.vola = (q.vola+q.volb)-b;q.volb = b;}q.step++;strcpy(q.str[q.step], "POUR(1,2)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}}}///把 b 倒满if(p.volb == 0){q = p;q.volb = b;q.step++;strcpy(q.str[q.step], "FILL(2)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}}///把 b 中的水倒出来else if(p.volb <= b){q = p;q.volb = 0;q.step++;strcpy(q.str[q.step],"DROP(2)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}if(p.vola < a){q = p;if(q.vola + q.volb <= a){q.vola += q.volb;q.volb = 0;}else{q.volb = (q.vola+q.volb)-a;q.vola = a;}q.step++;strcpy(q.str[q.step], "POUR(2,1)");if(!vis[q.vola][q.volb]){vis[q.vola][q.volb] = true;que.push(q);}}}}return false;
}
int main()
{while(cin>>a>>b>>k){bool ok = bfs();if(!ok)puts("impossible");}return 0;
}

21、鸣人和佐助

#include <iostream>  
#include <queue>  
#include <algorithm>  
#include <cstring>  
using namespace std;  struct point  
{  int x, y, ckl, time;  point (int xx,int yy, int cc, int tt):x(xx), y(yy), ckl(cc), time(tt){};  
};  int r,c,t;  
int min_time = 1 << 30;  
int dx[4] = {0, 0, 1, -1};  
int dy[4] = {1, -1, 0, 0};  
char mp[210][210];  
bool visited[210][210][11];  int bfs(int x, int y, int ex, int ey, int t)  
{  queue<point> q;  q.push(point(x, y, t, 0));  while (!q.empty())  {  point temp = q.front();  q.pop();  for (int i = 0; i < 4; i++)  {  int sx = temp.x + dx[i];  int sy = temp.y + dy[i];  if (sx == ex && sy == ey)  {  min_time = temp.time + 1;  return true;  }  if (mp[sx][sy] == '*')  {  if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl])  {  visited[sx][sy][temp.ckl] = true;  q.push(point(sx, sy, temp.ckl, temp.time + 1));  }  }  if (mp[sx][sy] == '#')  {  if (sx >= 0 && sx < r && sy >= 0 && sy < c && !visited[sx][sy][temp.ckl - 1] && temp.ckl > 0)  {  visited[sx][sy][temp.ckl - 1] = true;  q.push(point(sx, sy, temp.ckl - 1, temp.time + 1));  }  }  }  }  return false;  
}  int main(){  cin >> r >> c >> t;  int x, y, ex, ey;  memset(visited, 0, sizeof(visited));  for (int i = 0; i < r; i++)  {  for (int j = 0; j < c; j++)  {  cin >> mp[i][j];  if(mp[i][j] == '@')  {  x = i;  y = j;  mp[i][j] = '*';  }  if(mp[i][j] == '+')  {  ex = i;  ey = j;  mp[i][j] = '*';  }  }  }  if (bfs(x, y, ex, ey, t))  cout << min_time << endl;  else  cout << "-1" <<endl;  
}  

22、大盗阿福

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 100005
int t,n,ans;int f[N],a[N];
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);memset(f,0,sizeof(f));ans=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){f[i]=a[i];f[i]=max(f[i-2]+a[i],f[i-3]+a[i]);ans=max(ans,f[i]);}printf("%d\n",ans);}return 0;
}

23、马走日

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[21][22],n,m,t;
int x[10]={-2,-2,-1,1,2,2,1,-1},y[10]={-1,1,2,2,1,-1,-2,-2};
int x1,y1,ans;
void dfs(int a,int b)
{bool p=true;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)if (f[i][j]==0){p=false;break;}if (p==false)break;}if (p==true){ans++;return ;}for (int i=0;i<=7;i++){int l=a+x[i];int k=b+y[i];if (f[l][k]==1)continue;if (l>0&&l<=n&&k>0&&k<=m){f[l][k]=1;dfs(l,k);f[l][k]=0;}}
}
int main()
{scanf("%d",&t);for (int i=1;i<=t;i++){scanf("%d%d",&n,&m);scanf("%d%d",&x1,&y1);x1++;y1++;memset(f,0,sizeof(f));f[x1][y1]=1;ans=0;dfs(x1,y1);cout<<ans<<endl;}
}

24、鸣人的影分身

#include<cstdio>
#include<iostream>
using namespace std;
#define N 12
int t,m,n;int f[N][N];             //f[i][j]表示把i分j个的方案数 
int main(){n=10,m=10;for(int i=0;i<=10;i++) f[0][i]=1;for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){if(i>=j) f[i][j]=f[i][j-1]+f[i-j][j];else f[i][j]=f[i][i];}}scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);printf("%d\n",f[m][n]);}return 0;
}

25、开餐馆

#include<iostream>  
#include<cstring>  
#include<cstdio>  
using namespace std;  
int T,n,k;  
int a[105],v[105],pre[105],f[105];  
int main(){  scanf("%d",&T);  for (int t=1;t<=T;++t){  scanf("%d%d",&n,&k);  memset(a,0,sizeof(a));  memset(f,0,sizeof(f));  memset(v,0,sizeof(v));  memset(pre,0,sizeof(pre));  for (int i=1;i<=n;++i)  scanf("%d",&a[i]);  for (int i=1;i<=n;++i)  scanf("%d",&v[i]);  for (int i=2;i<=n;++i)  for (int j=i-1;j>=1;--j)  if (a[i]-a[j]>k){  pre[i]=j; break;  }  f[1]=v[1];  for (int i=2;i<=n;++i)  f[i]=max(f[i-1],f[pre[i]]+v[i]);  printf("%d\n",f[n]);  }  
}  

26、宠物小精灵之收服

#include<cstdio>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
int l,m,n,minn;  
int A[105][2];  
int f[1005][505];  
int main()  
{  scanf("%d %d %d",&m,&l,&n);  for(int i=1;i<=n;i++)  {  scanf("%d %d",&A[i][0],&A[i][1]);  }  for(int i=1;i<=n;i++)  {  for(int j=m;j>=A[i][0];j--)  {  for(int k=l;k>=A[i][1];k--)  {  f[j][k]=max(f[j][k],f[j-A[i][0]][k-A[i][1]]+1);  }  }  }  printf("%d ",f[m][l]);  for(int i=0;i<=l;i++)  {  if(f[m][i]==f[m][l])  {  minn=i;  break;  }  }  printf("%d",l-minn);  
}  

27、单词序列

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>using namespace std;struct Note
{string sf;int nus;
} d[31];string ks,es;
queue<int> q;
bool b[31],vis;
int length;
int sum=0;int gs(string x,string y)
{int sum=0;for(int i=0;i<length;i++) if(x[i]!=y[i]) sum++;return sum;
}int main()
{cin>>ks>>es;length=ks.size();int i=1;char ch;d[i].sf=ks;i=2;while(cin>>d[i].sf) i++;d[i].sf=es;q.push(1);while(!q.empty()){int cur=q.front();q.pop();if(d[cur].sf==es) {printf("%d\n",d[cur].nus+1);vis=1;break;}for(int j=1;j<=i;j++){if(gs(d[cur].sf,d[j].sf)==1&&!b[j]){d[j].nus=d[cur].nus+1;q.push(j);b[j]=1;}}}if(!vis) printf("0\n");return 0;
}

28、Sudoku

#include <stdio.h>  
/* 构造完成标志 */  
int sign;   //0代表false,1代表true   
/* 创建数独矩阵 */  
int num[9][9];  
/* 函数声明 */  
void Input();  
void Output();  
int Check(int n, int key);//返回0代表false,1代表true   
int DFS(int n);  /* 主函数 */  
main()  
{     int test,i,j;  
//  freopen("in.txt","r",stdin);  scanf("%d",&test);  while(test--)  {  sign=0;//设初始值为0   Input();//输入   DFS(0);    Output();//输出         }  
}  /* 读入数独矩阵 */  
void Input()  
{  int i,j;  for (i = 0; i < 9; i++)  for (j = 0; j < 9; j++)  scanf("%1d",&num[i][j]);//一个数一个数的读   
}  /* 输出数独矩阵 */  
void Output()  
{  int i,j;  for (i = 0; i < 9; i++)  {  for (j = 0; j < 9; j++)  {  printf("%d",num[i][j]);  }  printf("\n");  }  
}  /* 判断key填入n时是否满足条件 */  
int Check(int n, int key)  
{  /* 判断n所在横列是否合法 */  int i,j;  int x,y;  for (j = 0; j < 9; j++)   {  /* i为n竖坐标 */  i = n / 9;  //如果有相同的数，返回0（不合法）   if (num[i][j] == key) return 0;  }  /* 判断n所在竖列是否合法 */  for (i = 0; i < 9; i++)  {  /* j为n横坐标 */  j = n % 9;  //如果有相同的数，返回0（不合法）   if (num[i][j] == key) return 0;  }  /* x为n所在的小九宫格左顶点竖坐标 */  x = n / 9 / 3 * 3;//如：38/9/3*3=3   /* y为n所在的小九宫格左顶点横坐标 */  y = n % 9 / 3 * 3;//如：38%9/3*3=6   /* 判断n所在的小九宫格是否合法 */  for (i = x; i < x + 3; i++)  {  for (j = y; j < y + 3; j++)  {  if (num[i][j] == key) return 0;  }  }  /* 全部合法，返回正确 */  return 1;  
}  /* 深搜构造数独 */  
int DFS(int n)  
{  /* 所有的都符合，退出递归 */  int i;  if (n > 80)  {  sign = 1;  return 0;  }  /* 当前位不为空时跳过 */  if (num[n/9][n%9] != 0)  {  DFS(n+1);  }  else  {  /* 否则对当前位进行枚举测试 */  for (i = 1; i <= 9; i++)  {  /* 满足条件时填入数字 */  if (Check(n, i) == 1)  {  num[n/9][n%9] = i;  /* 继续搜索 */  DFS(n+1);  /* 返回时如果构造成功，则直接退出 */  if (sign == 1) return 0;  /* 如果构造不成功，还原当前位 */  num[n/9][n%9] = 0;  }  }  }  
}  

29、画家问题

#include <iostream>
using namespace std;int wallC[16][17] = { 0 },paint[16][17] = { 0 };
//wallC 记录墙的颜色，y为黄色，w为白色，将其转为w 为１，y 为０；
//paint记录需要上色的位置，１表示需要上色，０表示不需要上色
int paintGuess(const int& wSize)
{for (int i = 1; i < wSize; i++)for (int j = 1; j <= wSize; j++){paint[i + 1][j] =(wallC[i][j] + paint[i][j] + paint[i - 1][j] + paint[i][j + 1] + paint[i][j -1]) % 2;}// 枚举第一行的不同状态组合，再以第一行不同状态组合来确定对应位置是否需要paint；//　因为相邻的两的位置的paint会相互抵消，所以需要以相邻位置的paint与当前颜色来判断// 是否需要按下for (int i = 1; i <= wSize; i++){int n = (paint[wSize][i] + paint[wSize - 1][i] + paint[wSize][i + 1] + paint[wSize][i - 1]) % 2;if (n != wallC[wSize][i]){return 1001;}//求paint的最小值，所以返回一个大数，然后比较更新得到最小值}//判断最后一行是否都已经变成黄色，如果不是则说明这不是解int times = 0;//统计解的paint的次数for (int i = 1; i <= wSize; i++)for (int j = 1; j <= wSize; j++){if (paint[i][j] == 1)times++;}return times;
}
int enumerate(const int& wSize)
{int times = 1001;int steps = 0, n = 1;while (paint[1][wSize + 1] < 1)         // 据二进制进位规则可知，如果wSize的后一位如果为１的话，则代表wSize位的所有组合都已经进行完成了{steps = paintGuess(wSize);if (steps < times) times =steps;   //求出最小值paint[1][1]++;n = 1;while (paint[1][n] > 1)             //模拟二进制进位{paint[1][n] = 0;n++;paint[1][n]++;}}return times;
}
int main(void)
{//freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);int cases, wSize, r, c;char color;for ( r = 0; r<16; r++)for (c = 0; c < 17; c++){wallC[r][c] = 0;paint[r][c] = 0;}                                  // 为良好习惯，清空上次数据cin >> wSize;for (r = 1; r <= wSize; r++)for (c = 1; c <= wSize; c++){cin >> color;wallC[r][c] = (color== 'y' ? 0 : 1);}int times = enumerate(wSize);if (times > 1000)cout << "inf" << endl;elsecout << times<< endl;return 0;
}

30、Calling Extraterrestrial Intelligence Again

#include<iostream>
#include<math.h>
using namespace std;int isprime(int n)
{int i;for(i=3;i<=sqrt(n*1.0);){if(n%i==0)return 0;i=i+2;}return 1;
}int main()
{//freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);double mat[10001];int i,j,k;int n,m;int flag,temp;int re,pr;int max;double a,b;int p,q;mat[0]=2;j=1;//最小的素数for(i=3;i<40000;){if(isprime(i))//先把素数结果提前求出来{mat[j]=i;j++;}i=i+2;//偶数直接排除} while(scanf("%d %lf %lf",&m,&a,&b)!=EOF)//使用scanf的速度比cin快很多{ max=0;if(!m&&!a&&!b)break;for(i=0;i<j;i++){for(k=0;k<j;k++){if((mat[i]/mat[k])<(a/b))break;//判断条件不符合,直接退出if(mat[k]*mat[i]>m)break;if(   (mat[i]/mat[k])<=1   &&  mat[k]*mat[i]>max ){max=mat[k]*mat[i];p=mat[k];q=mat[i];}}if(mat[i]*2>m)break;}cout<<q<<" "<<p<<endl;}return 0;
}

31、最大子矩阵

#include <stdio.h>  
#include <stdlib.h>  
#define MAX 110  int MaxSubMerticx(int *a,int N)  //一维最大序列和问题  
{  int max,dp[MAX],i;  max=a[0];  dp[0]=a[0];  for(i=1;i<N;i++)  {  dp[i]=(dp[i-1]+a[i])>a[i]?(dp[i-1]+a[i]):a[i];  //最长子序列  if(dp[i]>max)  max=dp[i];  }  return max;  
}  int main()  
{  //freopen("D:\\Users\\GZC\\Desktop\\test.txt","r",stdin);int N,metricx[MAX][MAX],dp[MAX],sum,max;  int i,j,k;  while(scanf("%d",&N)!=EOF)  {  for(i=0;i<N;i++)  for(j=0;j<N;j++)  scanf("%d",&metricx[i][j]);  max=metricx[0][0];  for(i=0;i<N;i++)       //从第i行开始向下，依次枚举所有可能的矩阵  {  for(j=0;j<N;j++)  //保存从第i行到第j行的列和，相当于纵向压缩，将矩阵列压缩为一个点，从而将最大子矩阵（二维，纵向+横向）转换为最大序列和（一维，纵向一定，横向最大），达到降维的目的  dp[j]=0;  for(j=i;j<N;j++)  {  for(k=0;k<N;k++)   //计算到达j行为止的每一列的和  dp[k]+=metricx[j][k];  sum=MaxSubMerticx(dp,N);   //求出在纵向为从i到j行，横向为0-N的最大横向方向子序列  if(sum>max)  max=sum;     //更新全局最优解  }  }  printf("%d\n",max);  }  return 0;  
}