【解析】第十二届蓝桥杯青少组4月C++省赛真题解析及参考答案
点击领取>>>信息学奥赛 NOI、NOIP、各区CSP-J/S初赛复赛试题&蓝桥杯、信息杯、智慧杯编程试卷& 海淀区科普节、程序设计大赛
上周六，第十二届蓝桥杯青少组4月C++省赛结束，不知道同学们考得如何？为了让大家提前了解自己此次考试的发挥如何，老师们特意为大家带来了真题解析及参考答案，每一题都是新鲜出炉，快来看看你考得怎么样吧！
#include #include using namespace std;
int main(){ string s; cin >> s; for (int i = s.size()-1; i >= 0; i--) { cout << s[i]; } cout << endl; return 0;}2.剪绳子(40分)
#include using namespace std;
int main(){ int n; cin >> n; int ans = 1; for (int i = 1; i <= n; i++) { ans *= 2; } ans += 1; cout << ans << endl; return 0;}3.合数求和(50分)
#include using namespace std;
bool isPrime(int x){ if (x < 2) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true;}
int main(){ int n; cin >> n; int sum = 0; for (int i = 4; i <= n; i++) { if (!isPrime(i)) { sum += i; } } cout << sum << endl; return 0;}#include #include using namespace std;
int dp[35][550];
int main(){ int n, m; cin >> n >> m; int sum = 0; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= (i+1)*i/2; j++) { dp[i][j] = dp[i-1][j+i] + dp[i-1][abs(j-i)]; } } if (m == 0) cout << dp[n][m] / 2 << endl; else cout << dp[n][m] << endl; return 0;}【解析】
本题属于计数型动态规划问题，我们可以定义出状态dp[i][j]表示1~i的数字拆分成两个子数组求和的差的绝对值为j的方案数。
方程为 dp[i][j] = dp[i-1][j+i] + dp[i-1][abs(j-i)]
答案需要特判m == 0时的情况，例如n=3, m=0时，只有一组A1={1, 2}, A2={3}，但使用dp会将正反计算两次，因此需要对结果除以2；
其他情况下，不会出现正反计算两次的情况，因此直接输出即可。
5.最大价值(总分80分)
#include #include using namespace std;
int w[55], v[55];int dp[55][605];
int main(){ int t, m; cin >> t >> m; for (int i = 1; i <= m; i++) { cin >> w[i] >> v[i]; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= t; j++) { if (j >= w[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); else dp[i][j] = dp[i-1][j]; } } cout << dp[m][t] << endl; return 0;}【解析】
本题为01背包问题，属于模板题。
6.黑精灵与白精灵(总分100分)
按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。
路线：从黑精灵初始位置（1，1）到正下方方格（2，1）走1步，正下方方格（2，1）到其下方穿越们（3，1）“D”走1步，然后穿越到另一扇穿越门（2，3）向正下方（3，3）走1步，最后到大白精灵家（3，4）需要走1步，故最短路线需要4步。
【输入描述】
第一行输入两个以一个空格隔开的正整数N（2
接下来第二行输入两个以一个空格隔开的正整数：N1（N1<=N），M1（M1<=M），代表第一个穿越门位于第N1行第M1列；
接下来第三行输入两个以一个空格隔开的正整数：N2（N2<=N），M2（M2<=M），代表第二个穿越门位于第N2行第M2列；
注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2；两个穿越门位置也不能位于左上角（1，1）和右下角（M，N）；第一个穿越门位置要在第二个穿越门前边或者上边。
【输出描述】
输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。
【输入样例】
3 4
2 3
3 1
【输出样例】
4
#include #include using namespace std;
int main(){ int n, m; cin >> n >> m; int n1, m1, n2, m2; cin >> n1 >> m1 >> n2 >> m2; int ans1 = (n1 + m1 - 2) + (n - n2 + m - m2); int ans2 = (n2 + m2 - 2) + (n - n1 + m - m1); cout << min(ans1, ans2) << endl; return 0;}【解析】
本题题目描述较长，但读懂题目以后我们只需要计算曼哈顿距离即可。走穿越门一定不会比不走穿越门更坏，因此分别计算先走穿越门1和先走穿越门2的两种路线的步数，输出较小值即可。
微信公众号搜索： 北京小学学习资料 家长升学指南 关注公众号，获取最新资讯！
扫码添加“家长论坛”微信好友（微信号 16619908263）
获取信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节真题
咨询信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节政策请拨打电话 16619908263 （同微信号）
没有找到相关结果
0 个回复