第十四届蓝桥杯大赛青少组全国总决赛初级组\(C++\)题解
第一题
给定一个十进制正整数\(N（1≤N≤10^9）\)，请从小到大输出\(1\)~\(N\)之间（含\(1\)和\(N\)）所有满足以下要求的数：
-
这个数转换为八进制后是一个回文数；
-
这个数是一个平方数。
例如：\(N = 20\)，在\(1\)~\(20\)之间满足要求的数有\(1、4、9\)，因为有，
\(1\)转换为八进制为\(1\)，是一个回文数；且\(1 = 1^2\)，是一个平方数；
\(4\)转换为八进制为\(4\)，是一个回文数；且\(4 = 2^2\)，是一个平方数；
\(9\)转换为八进制为\(11\)，是一个回文数；且\(9 = 3^2\)，是一个平方数。
故输出1 4 9
输入描述
输入一个十进制正整数\(N（1≤N≤10^9）\)
输出描述
输出一行，包含若干个十进制正整数，表示满足题目要求的数。结果从小到大输出，两个正整数之间用一个空格隔开
样例输入
20
样例输出
1 4 9
题目解析
首先定义两个辅助函数：is_octal_palindrome用于检查一个数转换为八进制后是否为回文数，is_square用于检查一个数是否为平方数。在main函数中，我们遍历1到n之间的所有整数，检查它们是否满足题目要求，如果满足则输出
\(Code\)
#include <bits/stdc++.h>
using namespace std;
// 判断8进制回文
bool is_octal_palindrome(int n) {
string s1 = "";
while (n) {
s1 += to_string(n % 8);
n /= 8;
}
string s2 = s1;
reverse(s2.begin(), s2.end());
return s1 == s2;
}
// 判断完全平方数
bool is_square(int n) {
int s = (int)sqrt(n);
return s * s == n;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
if (is_octal_palindrome(i) && is_square(i))
cout << i << " ";
return 0;
}
由于\(n\)的数据范围太大，最多\(1e9\),所以，很明显\(O(N)\)的复杂度也会\(TLE\)掉一些测试样例，实测\(83\)分,需要进一步优化，你个蓝桥杯，还是初级组，还是第一题，上来就这么难是不是有点过了？？
为了优化代码，我们可以减少遍历的次数。因为我们要找的数是平方数，所以我们只需要遍历\(1\)到\(sqrt(n)\)之间的整数，然后检查它们的平方是否满足八进制回文数的条件。这样可以显著减少遍历次数。以下是优化后的代码：
\(Code\)
#include <bits/stdc++.h>
using namespace std;
bool is_octal_palindrome(int n) {
string s1 = "";
while (n) {
s1 += to_string(n % 8);
n /= 8;
}
string s2 = s1;
reverse(s2.begin(), s2.end());
return s1 == s2;
}
int main() {
int n;
cin >> n;
int s = (int)sqrt(n);
for (int i = 1; i <= s; i++) {
int s2 = i * i;
if (is_octal_palindrome(s2)) cout << s2 << " ";
}
return 0;
}
第二题
从金星探测器传回来一组测量数据，这是一个长度为\(N（1≤N≤1000000）\)的整数数列，数列中的每个整数代表某一种化学成分（相同的整数代表相同的化学成分）。
主要成分：指在包含的所有化学成分中比例超过一半（\(N÷2\)的结果向下取整）的成分。
现在要判断其是否有主要成分；如果有，其主要成分是哪一种？
例如：
当\(N=7\)，整数数列为1 2 3 2 2 1 2，其中成分\(2\)有\(4\)个，超过了\(7\)的一半（\(7\)的一半向下取整为\(3\)），所以主要成分是\(2\)。
当\(N=6\)，整数数列为1 102 31 31 1 102，其中的每一种成分都只有\(2\)个，未超过\(6\)的一半（\(6\)的一半为\(3\)），所以没有主要成分。
输入描述
第一行输入一个正整数\(N（1≤N≤1000000）\)，表示数列长度
第二行输入\(N\)个整数（\(1\)≤整数≤\(2×10^9\)），每个整数表示一种化学成分，两个整数之间用一个空格隔开
输出描述
输出一行，如果存在主要成分，则输出代表主要成分的整数，否则，输出No
**样例输入 **
7 1 2 3 2 2 1 2
样例输出
2
题目解析
好多孩子一看这题简单啊，就是一个桶嘛，所以很快就有了下面的代码：
\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int b[N]; // 开1e6不够，开2e9就会MLE，用桶是不行的
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++;
bool flag = false;
for (int i = 1; i <= n; i++)
if (b[a[i]] > n / 2) {
cout << a[i];
flag = true;
break;
}
if (!flag) cout << "No";
return 0;
}
但是，你看看数据范围啊，它的整数上限值是\(2\times 10^9\),如果按这个来设计桶的话，那肯定\(MLE\)啊! 需要\(Hash\)表处理，不能直接用桶来模拟：
\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
unordered_map<int, int> _map;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], _map[a[i]]++;
bool flag = false;
for (int i = 1; i <= n; i++)
if (_map[a[i]] > n / 2) {
cout << a[i];
flag = true;
break;
}
if (!flag) cout << "No";
return 0;
}
第三题
编程实现：简单算术题
题目描述：
给定一道 没有括号 的 四则混合运算算术题（可能包含多余的空格），请编程计算出结果。
运算规则如下：
既有乘、除法又有加、减法的，要先算乘除法，再算加减法
同级运算时，要从左往右按顺序计算
所有除法运算的结果都只保留整数部分（直接舍弃小数部分）
例如：当算术题为 \(2 + 3*4 - 10/6 + 1/24\)时，优先计算乘除法，有\(3*4=12，10/6=1，1/24=0\)；然后再计算加减法，\(2+3*4-10/6+1/24=2+12-1+0=13\)，故输出\(13\)。
输入描述
输入一个字符串，表示算术题，\(5\)≤字符串长度≤\(100000\)，字符串中只包含数字字符以及“+”、“-”、“*”、“/”运算符，不含括号，可能包含空格；
算式中的运算数范围：\(1\)≤运算数≤\(200\)。
输出描述
输出一个整数，表示算术题的计算结果。
题目数据保证算式的每一步运算的结果都在\(-2×10^9\)~\(2×10^9\)之间。
样例输入
2+3*4-10/6+1/24
样例输出
13
这就是一道用两个栈（运算符栈，数字栈）的表达式求值问题的裸题，如果讲过，孩子的电脑里有这道题，可以轻松\(AC\)，否则，就是\(0\)分。
\(Code\)
#include <bits/stdc++.h>
using namespace std;
stack<int> stk;
stack<char> op;
unordered_map<char, int> g{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
void eval() {
int a = stk.top();
stk.pop();
int b = stk.top();
stk.pop();
char p = op.top();
op.pop();
int r;
if (p == '+') r = b + a;
if (p == '-') r = b - a;
if (p == '*') r = b * a;
if (p == '/') r = b / a;
stk.push(r);
}
int main() {
string s;
getline(cin, s);
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') continue; // 过滤掉空格
if (isdigit(s[i])) {
int x = 0;
while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
x = x * 10 + s[i] - '0';
i++;
}
i--;
stk.push(x);
}
else if (s[i] == '(')
op.push(s[i]);
else if (s[i] == ')') {
while (op.top() != '(') eval();
op.pop();
} else {
while (op.size() && g[op.top()] >= g[s[i]]) eval();
op.push(s[i]);
}
}
while (op.size()) eval();
printf("%d\n", stk.top());
return 0;
}
第四题
编程实现：数独填数
数独是源自\(18\)世纪瑞士的一种数学游戏。玩家需要根据\(9×9\)网格上的已知数字，将剩余的所有空格填上数字，使得\(9×9\)网格上每一行、每一列及每一个\(3×3\)方块（粗线）内的数字均包含\(1\)~\(9\)，并且数字不重复。
这个数独可以使用如下\(9×9\)的字符方阵表示（空格用“.”表示）：
输入样例
17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
输出样例
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734
\(Code\)
回溯法，学过，电脑里有，就是轻松\(AC\)，否则，累死也白扯
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
int g[N][N];
int isValid(int r, int c, int x) {
// 同行，同列是不是存在同样的数字x
for (int i = 0; i < 9; i++)
if (g[r][i] == x || g[i][c] == x) return 0;
// 找出3X3的小方块开始行和开始列,也就是所在块左上角坐标
int row = r / 3 * 3;
int col = c / 3 * 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (g[row + i][col + j] == x)
return 0;
return 1;
}
int dfs() {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (g[r][c] == 0) {
for (int x = 1; x <= 9; x++) {
if (isValid(r, c, x)) {
g[r][c] = x;
if (dfs()) return true;
g[r][c] = 0;
}
}
return 0;
}
}
}
return 1;
}
int main() {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
char x;
cin >> x;
if (x != '.') g[i][j] = x - '0';
}
dfs();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) cout << g[i][j];
cout << endl;
}
return 0;
}
第五题
编程实现：数学实验
题目描述：
老师在黑板上写出了一个正整数数列，让所有同学都来做一个数学实验，要求如下：
这组数总共不超过\(500000\)个，每个数的大小范围在\(1\)~\(80\)之间；
要从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加\(1\)（例如：两个相邻的\(6\)，变成一个\(7\)）；
重复执行第\(2\)步；
当操作无法继续进行时，实验结束，此时，实验结果就是这组数里面最大的数。
注意：不同的实验方案得到的最大数不同。
现在给定了一个正整数数列，请你编写程序计算出能够得到的实验结果最大是多少。
例如：
当\(N=6\)，这个正整数数列是 \(1、2、2、2、3、4\)时，得到最大数的方法如下：
先将后面两个\(2\)变成一个\(3\)，然后\(3\)和\(3\)变成\(4\)，最后\(4\)和\(4\)变成\(5\)。可以证明，没有其它更好的方案，故输出\(5\)。
输入描述
第一行输入一个正整数\(N（1≤N≤500000）\)
第二行输入\(N\)个正整数（\(1\)≤正整数≤\(80\)），相邻两个数之间用一个空格隔开
输出描述
输出一个正整数，表示实验结束后能够得到的最大的实验结果
样例输入
6 1 2 2 2 3 4
样例输出
5
\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int a[N]; // 原数列
// DP数组
int f[N][82][2];
/*
考虑线性DP：
f[i][j][k]:
状态表示：所有 前i个数字，最后一个位置是数字j（可能是变更+1过，也可能是没有变更过）
k=0表示是未变更，k=1表示经过了相邻+相等+加1变更
属性：最大值
Q:为什么要开一个三维数组进行DP打表？为什么不是一维或是二维？
答：没有人闲着没事有一维够用开二维，有二维够用开三维，给自己找麻烦那是有病。
我们先假设开一维，代表的含义就是前i个数字最终符合条件可以获取到的最大值。来思考一下f[i]和f[i+1]之间的关系
此时，我们会发现，无法表示什么相邻，变更，不变更，状态不够清晰，需要把状态细化一下。
开个二维试试：f[i][j]
那就是表示前i个数字，最后一个数字是j,问题马上就来了：因为最后一位是j，可能是原来不是，是因为两个相邻一样的数字
拼出来的j,也可能是原始的j,这两个都是可能的，都应该保留下来，为后面的递推做地基，现在，我们把它们两个混淆了，就相
当于损毁了一个，导致后续的递推缺少了基础，明显也是不对的。
开个三维试试：f[i][j][k]
表示前i个数字，最后一个数字是j，这个j，如果k=0就代表原来就是j,如果k=1，就表示是因为相邻后相等+1等到的j。
这时，我们发现状态还是非常清晰的，任何一个状态的来龙去脉都可以不重不漏的描述清楚，没有丢失状态。
状态转移：
(1) 当我们位于第i个数字面前时，表示前i-1个已经处理完毕，对应的DP都已经填充利索了。
(2) 如果当前数字a[i]，与前一位的数字j不相等，那么很显然，不能形成与前一位数字相邻且相等，
f[i][a[i]][0]=max({f[i][a[i]][0],f[i-1][j][0],f[i-1][j][1]})
此处有的同学可能有疑问：前一位也不可能是所有的j∈(1,80)吧？是的，前一位的j只可能有2个数字，其它的肯定是0，这里我嫌麻烦，就直接枚举了81个数字
，因为没有填充的肯定是0，在求最大值的题目中，0是不会成为答案的，不会造成影响。
(3)如果当前数字a[i]，与前一位的数字j相等（这个j可能是变异过，也可能是原始的），那么与相位相邻可以产生+1的效果，有可能会使得最大值更新。
f[i][j + 1][1] = max({f[i][j + 1][1], f[i - 1][j][0], f[i - 1][j][1], f[i][j + 1][0], j + 1});
答案：
走完前n个数字，并且，枚举每一个可能结尾的数字j,变更或不变更的都可能是答案，需要一次枚举即可。
*/
/*
测试用例I
6
1 2 2 2 3 4
答案
5
测试用例II
6
1 2 2 1 3 4
答案
5
测试用例III
5
2 1 2 1 1
答案
3
测试用例IV
4
80 79 79 80
答案
81
测试用例V
6
2 3 4 4 4 5
答案
6
测试用例VI
6
2 3 4 6 5 5
答案
7
*/
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 初始化，前1个数字中，以a[1]结尾的状态，没有经历变更，最大值是a[1]
f[1][a[1]][0] = a[1];
// DP
// 以每个数字位置为阶段
for (int i = 2; i <= n; i++) {
int k = a[i];
for (int j = 1; j <= 81; j++) {
// 每一个前序可能状态，都可以通过加入a[i]时更新到新的状态
f[i][k][0] = max({f[i][k][0], f[i - 1][j][0], f[i - 1][j][1], k});
// 如果发现相邻且相等的情况,合并后+1
if (k == j)
f[i][j + 1][1] = max({f[i][j + 1][1], f[i - 1][j][0], f[i - 1][j][1], f[i][j + 1][0], j + 1});
}
}
// 结果
int res = 0;
for (int i = 1; i <= 81; i++)
res = max({res, f[n][i][0], f[n][i][1]});
cout << res << endl;
return 0;
}