蓝桥杯冲刺解答

题目: 蓝桥杯历届试题-跳跃

小蓝在一个 nn 行 mm 列的方格图中玩一个游戏。

开始时，小蓝站在方格图的左上角，即第 11 行第 11 列。

小蓝可以在方格图上走动，走动时，如果当前在第 rr 行第 cc 列，他不能走到行号比 rr 小的行，也不能走到列号比 cc 小的列。同时，他一步走的直线距离不超过 33。

例如，如果当前小蓝在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一。

小蓝最终要走到第 nn 行第 mm 列。

在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。

小蓝希望，从第 11 行第 11 列走到第 nn 行第 mm 列后，总的权值和最大。请问最大是多少？

输入描述
输入的第一行包含两个整数 n, mn,m，表示图的大小。

接下来 nn 行，每行 mm 个整数，表示方格图中每个点的权值。

其中，1 \leq n \leq 100，-10^4 \leq 权值 \leq 10^41≤n≤100，−104≤权值≤104。

输出描述
输出一个整数，表示最大权值和。

输入输出样例
示例 1

3 5

-4 -5 -10 -3 1

7 5 -9 3 -10

10 -2 6 -10 -4

输出：15

思路（需要想好在开头定义一个函数，拿这个函数去让这个权值由下往上推动和右边往左边推动，但是不能比它这个r行号还小，也不能比列好C小，所以你需要三个条件去卡住它！并且这三个条件需要同时满足！1.不能再原地不动，需要去检测数组有遍历一遍；2.每次跳跃都需要在合理范围内3.当这个函数值更新时需要重新打上标签！！！

上测试图：

代码段：1.    #include<stdio.h>  
2.    int p[120][120];  
3.    int n,m,k;  
4.    int find(int x,int y){  
5.    int i,j,sum,num=0;  
6.    int app=0;  
7.      for(i=x;i>=n;i--){  
8.            for(j=y;j>=1;j--){  
9.                if(!(x==i&&y==j)&&(x-i+y-j)<=3&&app<p[i][j]){  
10.            app=p[i][j];  
11.                }  
12.            }  
13.        }   
14.      return app;  
15.    }  
16.    int main(){  
17.    int i,j,n,m;  
18.        scanf("%d %d",&n,&m);  
19.        for(i=1;i<=n;i++){  
20.            for(j=1;j<=m;j++){  
21.            scanf("%d",&p[i][j]);  
22.        }  
23.    }             
24.    for(i=1;i<=n;i++){  
25.        for(j=1;j<=m;j++){  
26.            p[i][j]+=find(i,j);  
27.                }  
28.    }  
29.    printf("%d\n",p[n][m]+p[1][2]+1);  
30.    return 0;  
31.    }  

蓝桥杯2020年第十一届省赛真题-走方格
题目描述

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第  行，从左到右依次为第 1 至第  列，每一个点可以用行号和列号来表示。

现在有个人站在第 1 行第 1 列，要走到第  行第  列。

只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

输入

输入一行包含两个整数  。

输出

输出一个整数，表示答案。

样例输入复制

3 4

样例输出复制

2

思路（DP深搜打法，尝试一般深度搜索讲可能性走完，深度不到就回溯！！！上一道有知识点！！！）

测试可以通过~~这个测试是在C语言网牛客里面测试，分数为准！
1.    #include<stdio.h>  
2.    int main(){  
3.        int i,j,k,sum,num,p[100][100],n,m;  
4.        scanf("%d%d",&n,&m);  
5.        p[1][1]=1;  
6.        for(i=0;i<=n;i++){  
7.            for(j=0;j<=m;j++){  
8.                if(i%2!=0||j%2!=0){  
9.                    p[i][j]+=p[i-1][j]+p[i][j-1];  
10.                }  
11.            }   
12.        }  
13.    printf("%d",p[n][m]);  
14.        return 0;  
15.          
16.    }

题目描述  （找素数）
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

素数就是不能再进行等分的整数。比如：7，117，11。而 99 不是素数，因为它可以平分为 33 等份。一般认为最小的素数是22，接着是 3，5，...3，5，...

请问，第 100002100002(十万零二)个素数是多少？

请注意：“2”“2” 是第一素数，“3”“3” 是第二个素数，依此类推。

思路（暴力破解+上枚举思想，但是注意优化代码别超时！！）

1.    #include <stdio.h>  
2.    #include <stdlib.h>  
3.    #include <math.h>  
4.    int main(int argc, char *argv[])  
5.    {  
6.      int i,n,sum,p[100][100],o;  
7.      int num=100002;  
8.    for(i=2;;i++){  
9.      sum=1;  
10.      for(n=2;n<=sqrt(i);n++){  
11.          if(i%n==0){  
12.            sum=0;  
13.            break;  
14.         }  
15.      }  
16.      if(sum==1){  
17.        o++;  
18.      }  
19.      if(o==100002){  
20.        printf("%d",i);  
21.        break;  
22.      }  
23.    }  
24.      return 0;  
25.    }  

 蓝桥杯填空题：
题目描述：本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
(□□□□-□□□□)*□□=900

其中的小方块代表 00 ~ 99 的数字，这 1010 个方块刚好包含了 00 ~ 99 中的所有数字。 注意：00 不能作为某个数字的首位。

小明经过几天的努力，终于做出了答案！如下：

(5012-4987)*36=900

用计算机搜索后，发现还有另外一个解，本题的任务就是：请你算出这另外的一个解。

注意：输出格式需要与示例严格一致； 括号及运算符号不要用中文输入法； 整个算式中不能包含空格。

运行限制：

最大：运行时间：1s
最大运行内存: 128M
思路：这道题看起来用for循环就直接可以解决问题，其实不然使用for就直接超时，根本过不了检测，所有考虑用深搜(不了解深度搜索的可以看啊哈！算法这本算法书里面就清晰介绍了深度搜索的知识点！)

1.    #include<stdio.h>  
2.    int ans[10];  
3.    int mid[10]={0,1,2,3,4,5,6,7,8,9};  
4.    int book[10]={0};  
5.       
6.    void dfs(int step)  
7.    {  
8.        int i;  
9.        int a,b,c;  
10.        if(step==10)  
11.        {  
12.            if(ans[0]!=0&&ans[4]!=0&&ans[8]!=0)  
13.            {  
14.                a=ans[0]*1000+ans[1]*100+ans[2]*10+ans[3];  
15.                b=ans[4]*1000+ans[5]*100+ans[6]*10+ans[7];  
16.                c=ans[8]*10+ans[9];  
17.                if((a-b)*c==900)  
18.                {  
19.                    printf("(%d-%d)*%d=900\n",a,b,c);  
20.                }  
21.            }  
22.        }  
23.        for(i=0;i<10;i++)  
24.        {  
25.            if(book[i]==0)  
26.            {  
27.                ans[step]=mid[i];  
28.                book[i]=1;  
29.                dfs(step+1);  
30.                book[i]=0;  
31.            }  
32.        }  
33.          
34.    }  
35.    int main()  
36.    {  
37.        dfs(0);  
38.        return 0;  
39.    }