第四届蓝桥杯大赛个人赛省赛（软件类）A组真题
A. 高斯日记 大数学家高斯有个好习惯：无论如何都要记日记。
他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210
后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？
高斯出生于：1777年4月30日。
在高斯发现的一个重要定理的日记上标注着：5343，因此可算出那天是：1791年12月15日。
高斯获得博士学位的那天日记上标着：8113 请你算出高斯获得博士学位的年月日。提交答案的格式例如：1980-03-21
请严格按照格式，通过浏览器提交答案。
注意：只提交这个日期，不要写其它附加内容，比如：说明性的文字。
分析：日期判断。excel大法也行，这里就上代码了
#include<iostream> #include<string> using namespace std; int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool check(int date)//合法日期判断 { int y = date / 10000; int m = date % 10000 / 100; int d = date % 100; if(!m || !d || m > 12) return false; if(m != 2 && d > month[m]) return false; if(m == 2) { int leap = y % 4 == 0 && y % 100 || y % 400 == 0;//闰年平年判断 if(d > 28 + leap) return false; } return true; } int main() { int res = 0; for(int i = 17770430;i < 20000000;i++)//枚举数字 { if(check(i)) res++; if(res == 8113) { cout << i; break; } } return 0; }答案 : 1799-07-16
B. 排它平方数 小明正看着 203879 这个数字发呆。 原来，203879 * 203879 = 41566646641这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。具有这样特点的6位数还有一个，请你找出它！
再归纳一下筛选要求：
6位正整数每个数位上的数字不同其平方数的每个数位不含原数字的任何组成数位 答案是一个6位的正整数。请通过浏览器提交答案。
注意：只提交另一6位数，题中已经给出的这个不要提交。
注意：不要书写其它的内容（比如：说明性的文字）。
#include<iostream> #include<cmath> #include<cstring> using namespace std; bool check(int t) { int v[10] = {0};//访问数组记录出现的数字 long long k =(long long) pow(t,2); while(t)//记录本身出现过的数字 { v[t % 10] = 1; t /= 10; } while(k)//平方后 { if(v[k % 10]) return false; k /= 10; } return true; } int main() { for(int i = 100000;i <= 999999;i++)//枚举 { if(check(i)) { cout << i; break; } } return 0; }答案：141494
C. 振兴中华 小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：
比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 要求跳过的路线刚好构成“从我做起振兴中华”这句话。请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
分析：暴力搜索，记忆化dp
做法一：dfs
#include <iostream> #include <cstdio> using namespace std; int a[4][5]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}}; //把字映射到数字上 int res; void dfs(int i,int j) { if(i == 3 && j == 4)//终点 { res++; return; } //根据句子顺序，向下和向右搜索 if(a[i][j + 1] == a[i][j] + 1)//向右 且比之前的数大一，也就是按顺序的下一个字 dfs(i,j + 1); if(a[i + 1][j] == a[i][j] + 1)//向下 dfs(i + 1,j); } int main() { dfs(0,0); cout << res; return 0; }做法二：dp
#include <iostream> #include <cstdio> using namespace std; int f[10][10]; int main() { f[1][1] = 1; for (int i = 1; i <= 4; i++) for (int j = 1; j <= 5; j++) f[i][j] += f[i - 1][j] + f[i][j - 1];//当前位置都是由上边和左边路径值的和 cout << f[4][5] << endl; return 0; }答案：35
D. 颠倒的价牌 小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。
其标价都是4位数字（即千元不等）。
小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了。
这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，比如：1958 倒着挂就是：8561，差了几千元啊!!
当然，多数情况不能倒读，比如，1110 就不能倒过来，因为0不能作为开始数字。
有一天，悲剧终于发生了。某个店员不小心把店里的某两个价格牌给挂倒了。并且这两个价格牌的电视机都卖出去了!
庆幸的是价格出入不大，其中一个价牌赔了2百多，另一个价牌却赚了8百多，综合起来，反而多赚了558元。
请根据这些信息计算：赔钱的那个价牌正确的价格应该是多少？ 答案是一个4位的整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
#include<iostream> #include<string> using namespace std; //对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以 int a[10] = {0,1,2,-1,-1,5,9,-1,8,6}; int getNum(int k) { if(k % 10 == 0) return -1;//末尾为0的情况 int res = 0;//挂倒后的数 while(k) { if(a[k % 10] == -1) return -1;//不能挂到的数，如出现3，挂到后不是正确的数，是卖不出的 res = res * 10 + a[k % 10]; k /= 10; } return res; } int main() { for(int i = 1000;i <= 9999;i++) { for(int j = 1000;j <= 9999;j++) { int a = getNum(i); int b = getNum(j); if(a == -1 || b == -1)//不能挂到 continue; if((a + b - i - j == 558) && (i - a) > 200 && (i - a) < 300 && (b - j) > 800 && (b - j) < 900 )//符合盈利558，一个获利200多，一个赔了三百多 { cout << i << " " << j << " " << a << " " << b << endl; } } } return 0; }答案：9088
E 前缀判断 题目标题：前缀判断
如下的代码判断 needle_start指向的串是否为haystack_start指向的串的前缀，如不是，则返回NULL。
比如：“abcd1234” 就包含了 “abc” 为前缀
char* prefix(char* haystack_start, char* needle_start) { char* haystack = haystack_start; char* needle = needle_start; while(*haystack && *needle){ if(_______________) return NULL; //填空位置 } if(*needle) return NULL; return haystack_start; }请分析代码逻辑，并推测划线处的代码，通过网页提交。 注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
分析
这个题目的意思也就是，从两个串的开始进行对应位置的匹配，直到有一个串已经检查完则循环结束，期间若出现对应位置的字符不匹配则说明字符串不匹配提前结束循环返回。
答案：*haystack++) != *(needle++)
F. 逆波兰表达式 正常的表达式称为中缀表达式，运算符在中间，主要是给人阅读的，机器求解并不方便。
例如：3 + 5 * (2 + 6) - 1
而且，常常需要用括号来改变运算次序。
相反，如果使用逆波兰表达式（前缀表达式）表示，上面的算式则表示为：
3 * 5 + 2 6 1不再需要括号，机器可以用递归的方法很方便地求解。
为了简便，我们假设：
只有 + - * 三种运算符 每个运算数都是一个小于10的非负整数 下面的程序对一个逆波兰表示串进行求值。
其返回值为一个结构：其中第一元素表示求值结果，第二个元素表示它已解析的字符数。
struct EV { int result; //计算结果 int n; //消耗掉的字符数 }; struct EV evaluate(char* x) { struct EV ev = {0,0}; struct EV v1; struct EV v2; if(*x==0) return ev; if(x[0]>='0' && x[0]<='9'){ ev.result = x[0]-'0'; ev.n = 1; return ev; } v1 = evaluate(x+1); v2 = _____________________________; //填空位置 if(x[0]=='+') ev.result = v1.result + v2.result; if(x[0]=='*') ev.result = v1.result * v2.result; if(x[0]=='-') ev.result = v1.result - v2.result; ev.n = 1+v1.n+v2.n; return ev; }请分析代码逻辑，并推测划线处的代码，通过网页提交。
注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
分析 我们先模拟程序运行，观察v1得到的v1.result为3，那么很显然后面的代码就是要计算3+5*(2 + 6)，即v2.result的结果应该是5*(2 + 6)的结果，那么根据递归求解子问题的方法，那么答案就显而易见了。
答案：evaluate(x+v1.n+1)
G. 错误票据 某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）
每个整数代表一个ID号。
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID
例如：
用户输入：
2 5 6 8 11 9 10 12 9 则程序输出：
7 9
代码：
#include<bits/stdc++.h> using namespace std; int N; int m,n; unordered_map<int,int> um; int main() { cin >> N; int minn = 0,maxn = 0; while(N) { int a; while(cin >> a) { minn = min(minn,a); maxn = max(maxn,a); um[a]++; } N--; } int t,k; for(int i = minn;i <= maxn;i++) { if(!um.count(i)) t = i; if(um[i] == 2) k = i; } cout << t << " " << k; return 0; }H. 买不到的数目 小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
要求输出：
一个正整数，表示最大不能买到的糖数
例如：
用户输入：
4 7 程序应该输出：
17 再例如：
用户输入：
3 5 程序应该输出：
7
代码：
#include <iostream> using namespace std; int gcd(int a, int b){ return !b ? a : gcd(b, a % b); } int lcm(int a, int b){ return (a/gcd(a,b) * b); } int main() { int a, b; cin >> a >> b; cout << (lcm(a, b) - (a + b)) << endl; return 0; }也附上dfs超时代码吧
#include <iostream> using namespace std; //给定一个m，是否能用p和q凑出来 bool dfs(int m,int p,int q) { if(m == 0) return true; if(m >= p && dfs(m - p,p,q)) return true; if(m >= q && dfs(m - q,p,q)) return true; return false; } int main() { int p,q; cin >> p >> q; int res = 0; for(int i = 1; i <= 1000;i ++) { if(!dfs(i,p,q)) res = i; } cout << res << endl; return 0; }I. 剪格子 如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0
程序输入输出格式要求：
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000
程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。
例如：
用户输入：
3 3 10 1 52 20 30 1 1 2 3 则程序输出： 3
再例如： 用户输入：
4 3 1 1 1 1 1 30 80 2 1 1 1 100 则程序输出：
10
代码：
#include <iostream> #include <cstdio> using namespace std; const int N = 10010; int m, n, sum, ans = 0x3f3f3f3f; int a[N][N]; int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0}; bool vis[N][N]; void dfs(int x, int y, int s, int cnt) { cout << s << endl; if (s > sum / 2) return; if (s == sum / 2) { if (cnt < ans) ans = cnt; return; } for (int i = 0; i < 4; i ++) { int tx = x + dx[i], ty = y + dy[i]; if (tx < 1 || tx > n || ty < 1 || ty > m || vis[tx][ty]) continue; vis[tx][ty] = true; dfs(tx, ty, s + a[tx][ty], cnt + 1); vis[tx][ty] = false; } } int main() { cin >> m >> n; for (int i = 1;i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j], sum += a[i][j]; if (sum % 2) { cout << 0 << endl; return 0; } dfs(1, 1, a[1][1], 1); cout << ans << endl; return 0; }J. 大臣的旅费 很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式：
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出格式:
输出一个整数，表示大臣J最多花费的路费是多少。
样例输入:
5 1 2 2 1 3 1 2 4 5 2 5 4 样例输出:
135
分析： Y总的视频讲解: https://www.acwing.com/video/710/
秦淮岸大佬的讲义:https://www.acwing.com/blog/content/319/
代码：
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n; struct edg{ int id,w; }; vector<edg> v[N]; int dict[N]; void dfs(int u,int father,int distance) { dict[u] = distance; for(auto node : v[u]) { if(node.id != father) dfs(node.id,u,distance + node.w); } } int main() { cin >> n; for(int i = 0;i < n - 1;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); v[a].push_back({b,c}); v[b].push_back({a,c}); } dfs(1,-1,0); int u = 1; for(int i = 1;i <= n;i++) if(dict[i] > dict[u]) u = i; dfs(u,-1,0); for(int i = 1;i <= n;i++) if(dict[i] > dict[u]) u = i; int s = dict[u]; printf("%lld",s * 10 + s * (s + 1ll) / 2); }