1、水下探测器
水下探测器可以潜入湖中在任意水深进行科学探索。
湖水的最大深度为 h 米,即它在湖底时到水面的距离，0<=h<=100；
探测器最初的水下深度为 s 米，0<=s<=100；
当探测器不在水面（当前深度大于 0）时，每个 u 指令可使它上浮 1 米，而当探测器在水面时，u 指令是无效的；
当探测器不在湖底（当前深度小于 h）时，每个 d 指令可使它下沉 1 米，而当探测器在湖底时，d 指令是无效的；
在执行到无效指令时，探测器不做任何操作而继续执行下一指令。
编程实现：
根据给定的 h、s 和一个指令序列（由字符 u、d 组成的字符串，长度不超过 100），求出执行完整的指令序列后，探测器的水下深度。
输入：
第一行：h 和 s，以空格分开。0<=s<=h<=100
第二行：长度不超过 100 的指令字符串，串中仅包含字母 u 或 d
输出：
代表探测器在执行指令后的水下深度的数字。
样例输入：
9 1
uduudd
样例输出：
2
样例数据分析:
考察知识:
基础语法,字符串,循环,条件判断
参考代码:
1. #include <stdio.h> 2. #include <iostream> 3. using namespace std; 4. int main(int argc, char *argv[]) 5. { 6. int h,s; 7. scanf("%d %d",&h,&s); 8. char n[101]; 9. scanf("%c",n); 10. int l=strlen(n); 11. for(int i=0;i<l;i++){ 12. if(n[i]=='u') 13. if(s>0)s--; 14. else if(n[i]=='d') 15. if(s<h)s++; 16. } 17. printf("%d",s); 18. return 0; 19. }
2、猫吃鱼
明明家从 1 号站点出发，开车去旅游，一共要经过 n 个站点，依次为 2、3……n。
由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐（包括 1 号站点）。
除了 1 号站点只能吃 1 号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。
但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。
为使问题简化，我们约定：
（1）车从某站开出时油箱中都是此站点刚加的汽油。
（2）车载冰箱能容纳一路上需要的所有鱼。
即：每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。
编程实现：
为了降低小猫吃鱼的总代价，明明预先上网查到了这 n 个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗？
输入：
第一行：站点数 n，1<n<100。
接下来的 n 行：每行两个以空格分隔的正整数，表示：这一站买一条鱼的费用，以及从这一站把每条
鱼保存到下一站的费用，两个费用均为小于 10000 的正整数。
输出：
最小总费用，是一个正整数。
样例输入：
5
6 3
7 1
3 2
8 3
9 5
样例输出：
29
参考代码:
1. #include <iostream> 2. #include <stdio.h> 3. using namespace std; 4. int m[100][3]; 5. int main(int argc, char *argv[]) 6. { 7. int n; 8. scanf("%d",&n); 9. for(int i=1;i<=n;i++) 10. scanf("%d %d",&m[i][1],&m[i][2]); 11. int sum=0,min=99999; 12. for(int i=1;i<=n;i++){ 13. if(min>m[i][1]) min=m[i][1]; 14. sum+=min; 15. min+=m[i][2]; 16. } 17. printf("%d\n",sum); 18. return 0; 19. }
3、评选最佳品牌
n 个评委投票，在 m 个商品中评选一个最佳品牌。
评选采用多轮淘汰制，即：每轮投票，淘汰掉得票最少的候选品牌（得票并列最少的品牌一起淘汰）。
如此一轮轮淘汰下去，如果最后只剩下一个品牌当选，即告评选成功。
但如果在某轮投票中，当时未被淘汰的所有候选品牌（大于等于两个品牌）都并列得票最少，即告评选失败。
如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。
在评选流程中，每个评委的态度都可用一个序列来表示；例如当 m=5 时，某评委的评选态度序列为：3、
5、1、2、4，则表示该评委：优先投 3 号，当 3 号被淘汰时投 5 号，当 3 和 5 都被淘汰时投 1，当 3、5、1 都被淘汰时投 2，仅剩 4 号时才投 4 号品牌的票。
选票的序列中可以表示弃权，用 0 来表示，例如当 m=5 时，某评委的评选态度序列为：3、5、0，则表示该评委：优先投 3 号，当 3 号被淘汰时投 5 号，其它情况下不投任何品牌的票。
编程实现：
请你编一个程序，模拟各轮投票的过程，得到评选结果。
输入：
第一行：m(0<m<10,表示参加评选的品牌数)和 N(1<n<1000,表示参加投票的评委数)，之间以空格分隔接下来的 n 行：每行都是长度不超 m 的数字字符串，每个字符串表示一个评委的评选态度。
输出：
评选结果。
样例 1 输入：
3 4
123
213
132
10
样例 1 输出：
1
样例 2 输入：
3 4
321
213
231
312
样例 2 输出：
-2
样例数据分析:
考察知识:
字符串,桶排序,模拟算法
参考代码:
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. #include<fstream> 5. using namespace std; 6. const int M=15,N=1010; 7. int g[N][M];//存储评委投票态度 8. int piao[M];//得票桶 9. int st[M];//品牌标识桶 10. bool success=true; 11. int last_piaoshu; 12. int last_pinpai; 13. int n,m;//n个评委 m个品牌 14. void pingxuan() 15. { 16. while(1){ 17. memset(piao,0,sizeof(piao)); 18. for(int i=1;i<=n;i++) 19. for(int j=1;j<M;j++){ 20. int k=g[i][j]; 21. if(k==0) break;//弃权票 22. if(st[k])continue;//品牌已淘汰 23. piao[k]++;//投票入桶 24. break;//投票完成换下个评委 25. } 26. //寻找最大票数和最小票数 27. int min=1001,max=-1001; 28. for(int i=1;i<M;i++){ 29. if(piao[i]<min && !st[i])min=piao[i]; 30. if(piao[i]>max && !st[i])max=piao[i]; 31. } 32. if(max>min){//淘汰掉最小得票的品牌 33. for(int i=1;i<M;i++) 34. if(piao[i]==min && st[i]==false)st[i]=true;//标志淘汰 35. continue;//进入下一轮评选 36. } 37. else{ 38. int sum=0; 39. for(int i=1;i<M;i++)//搜索有几个最小票数的品牌 40. if(piao[i]==min)sum++,last_pinpai=i; 41. if(sum==1)return;//只剩一个品牌，结束循环 42. else{//剩余多个品牌，评选失败 43. last_piaoshu=min;//保留最后一轮的得票 44. success=false;//标识失败 45. return ;//评选结束 退出循环 46. } 47. } 48. } 49. } 50. int main() 51. { 52. //freopen("king.in","r",stdin); 53. cin>>m>>n; 54. for(int i=1;i<=n;i++){ 55. string str; 56. cin>>str; 57. for(int j=0;j<str.size();j++) 58. g[i][j+1]=str[j]-'0'; 59. } 60. pingxuan(); 61. if(success) cout<<last_pinpai<<endl; 62. else cout<<"-"<<last_piaoshu<<endl; 63. return 0; 64. }
4、最大购物优惠
小惠听说超市正在打折促销，要制订一个得到最大优惠的购物计划。
小惠的体力可以提起 w 单位重量的东西，还有一个能装 V 个单位体积的购物袋，并详细了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内，尽可能多地得到购物优惠。
超市规定这些打折商品每种只能购买一件。
编程实现：
请你编写程序，制定一个购买商品的计划，求出小惠能得到的最大优惠金额和实际应购买的各商品序号。
输入：
第一行：依次为 w、v 和 n(n 为商品种类数)，所有数值均为不超过 100 的正整数
接下来的 n 行：每行有三个整数，依次为某种商品的重量、体积和让利金额，数值间以空格分开，所有数值均为不超过 100 的正整数
输出：
第一行：小惠能够得到的最大让利金额
第二行：依次为从小到大排列的商品序号，序号从 1 开始，序号间用空格分开。若第二行输出的序列不唯一，则输出其最小字典序。
样例输入：
10 9 4
8 3 6
5 4 5
3 7 7
4 5 4
样例输出：
9
2 4
样例数据分析:
考察知识:
动态规划,二维费用的背包问题,在01背包问题的基础上增加一个费用维度
状态转移方程:
yh[i][j][k]=max(yh[i-1][j][k],yh[i-1][j-w[i]][k-v[i]]+n[i])
经典01背包问题解(https://blog.csdn.net/qq_38410730/article/details/81667885)
总体思路：
1.先从后往前推，得到最大让利金额，并形成具体方案（仿照最短路问题，从后往前）
2.再从前往后推，得到具体方案的字典序
参考代码:
1. #include<iostream> 2. #include<algorithm> 3. #include<fstream> 4. using namespace std; 5. const int N=110; 6. int w[N],v[N],p[N]; 7. int f[N][N][N]; 8. int main() 9. { 10. //freopen("shopping.in","r",stdin); 11. int W,V,n; 12. cin>>W>>V>>n; 13. for(int i=1;i<=n;i++) cin>>w[i]>>v[i]>>p[i]; 14. //求最短路，从后往前推 15. for(int i=n;i>=1;i--){ 16. for(int j=0;j<=W;j++) 17. for(int k=0;k<=V;k++){ 18. f[i][j][k]=f[i+1][j][k]; 19. if(j>=w[i] && k>=v[i]) 20. f[i][j][k]=max(f[i][j][k],f[i+1][j-w[i]][k-v[i]]+p[i]); 21. } 22. } 23. cout<<f[1][W][V]<<endl; 24. //字典序向后推 25. int j=W,k=V; 26. for(int i=1;i<=n;i++) 27. if(j>=w[i] && k>=v[i] && f[i][j][k]==f[i+1][j-w[i]][k-v[i]]+p[i]){ 28. cout<<i<<' '; 29. j-=w[i],k-=v[i]; 30. } 31. puts(""); 32. return 0; 33. }
5、迷宫
把一个 n 行 m 列的字符阵列看做一个迷宫，迷宫仅包含 L、Q、B、S 中的大写字母（蓝桥杯赛的汉语拼音首字母）。
初始时，你可以从任意一个“L”字母开始，移向相邻的“Q”字母，然后从此“Q”字母出发，移向相邻的“B”字母，然后从此“B”字母出发，移向相邻的“S”字母……。这样，你就算是走过了一个“LQBS”字符序列。
接下来，仍然可以从此“S”字母出发，移向相邻的“L”字母……，重复上述的动作，你就可以不断地走过“LQBS”序列。
请注意，所谓相邻仅包含上、下、左、右 4 个方向，且只能从 L->Q，从 Q->B，从 B->S，从 S->L。
可以想像，由于选择的出发点不同，我们有可能在迷宫中走过无数次的“LQBS”，或者是有限次的“LQBS”，
或者一次也走不了。
编程实现：
请你编写程序，求出在给定的迷宫中，我们最多可以走过多少次“LQBS”?
输入：
第一行：正整数 n,m，表示迷宫的规模为 n 行 m 列，0<m<100，0<n<100
接下来的 n 行：每行 m 个符合题意的字母，字母间无空格。
输出：
一个整数。即：如果在迷宫中可以无限次的走过“LQBS”，输出-1，否则，输出可以走过“LQBS”的最多次数。
样例 1 输入：
1 2
LQ
样例 1 输出：
0
样例 2 输入：
3 3
LSB
QBQ
BSL
样例 2 输出：
-1
样例 3 输入：
4 4
BLQB
BBQS
SBQL
QQQQ
样例 3 输出：
2
样例数据分析:
考察知识:
搜索与回朔
由于笔者的学员暂时未学到搜索与回朔算法,所以采用循环遍历类似穷举算法进行题解
参考代码:
1. #include<iostream> 2. #include<algorithm> 3. #include<fstream> 4. using namespace std; 5. const int N=110; 6. char g[N][N]; 7. int f[N][N]; 8. int n,m; 9. bool wuxian; 10. int mstep,step=1; 11. int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 12. void dfs(int x,int y){ 13. for(int i=0;i<4;i++){ 14. int xx=x+dx[i],yy=y+dy[i]; 15. if(xx<0||xx>n-1||yy<0||yy>m-1)continue;//越界跳过 16. if((g[x][y]=='L' && g[xx][yy]=='Q')||(g[x][y]=='Q' && g[xx][yy]=='B')|| 17. (g[x][y]=='B' && g[xx][yy]=='S')||(g[x][y]=='S' && g[xx][yy]=='L')){ 18. if(f[xx][yy]){ 19. wuxian=true; 20. return ; 21. } 22. f[xx][yy]=1; 23. step++; 24. mstep=max(mstep,step); 25. dfs(xx,yy); 26. f[xx][yy]=0; 27. step--; 28. } 29. } 30. return ; 31. } 32. int main() 33. { 34. //freopen("LQBS3.in","r",stdin); 35. cin>>n>>m; 36. for(int i=0;i<n;i++) cin>>g[i]; 37. for(int i=0;i<n;i++){ 38. for(int j=0;j<m;j++){ 39. if(g[i][j]=='L'){ 40. memset(f,0,sizeof(f)); 41. dfs(i,j); 42. } 43. if(wuxian){ 44. cout<<-1<<endl; 45. return 0; 46. } 47. } 48. } 49. cout<<mstep/4<<endl; 50. 51. return 0; 52. }
