江苏省2024年"信息与未来"中小学生编程思维展示活动 题解
1. 幸运数字
1.1 题面描述
如果一个正整数的二进制表示中，每个比特的左边或右边都至少有一个相同的比特，Dr. X 就认为它是一个"幸运数字"。
例如：
：有落单的 1，不是幸运数字 ：有落单的 0，不是幸运数字 ：是幸运数字 ：是幸运数字
给定两个整数 和 ，求出 范围内有多少个幸运数字。
输入格式：输入空格分隔的整数 和 。
输出格式：输出一行一个整数，代表 和 之间（）幸运数字的数量。
样例：
输入：
1 100
输出：
14
输入：
4096 65535
输出：
1364
数据范围：
1.2 思路
二进制表示中，所有连续相同字符的段长度都 就是幸运数字。
不大，直接枚举即可。把数转成二进制字符串，逐位检查：
首字符只检查右侧 尾字符只检查左侧 中间字符左右至少有一个相同
注意：除2取余得到的是逆序二进制，要反转后再判断。
1.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
boolisLucky(int x){
if (x == 0) returnfalse;
string s;
int tmp = x;
while (tmp > 0) {
s += (tmp % 2) + '0';
tmp /= 2;
}
reverse(s.begin(), s.end());
int n = s.size();
for (int i = 0; i < n; i++) {
if (i == 0) {
if (s[i] != s[i + 1]) returnfalse;
} elseif (i == n - 1) {
if (s[i] != s[i - 1]) returnfalse;
} else {
if (s[i] != s[i - 1] && s[i] != s[i + 1]) returnfalse;
}
}
returntrue;
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> a >> b;
int ans = 0;
for (int i = a; i <= b; i++)
if (isLucky(i)) ans++;
cout << ans << endl;
return0;
}
2. 红绿灯
2.1 题面描述
七段数码管每个数字对应固定的点亮段（A~G）。Dr. X 发现数码管可能发生故障：
常亮：某段始终点亮 不亮：某段始终不亮
根据日志记录（观察到的数字和亮着的段），推断每段的故障状态。
输入格式：第一行 表示日志数量，接下来 行每行形如 kABC...， 是观察到的数字，后面的字母表示亮着的段。
输出格式：输出7个字符代表A~G段状态：
常亮输出 X不亮输出 x无法确定输出 -
样例：
输入：
3
1BCD
7BCD
7DCB
输出：
x--X---
数据范围：
2.2 思路
预存每个数字正常应该亮的段。对比观察到的亮段：
实际亮了但正常不该亮 → 常亮 X实际没亮但正常该亮 → 不亮 x
2.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
char ans[10];
// 0~9每个数字的A~G点亮状态，1亮0灭
int book[10][7] = {
{1, 1, 1, 1, 1, 1, 0}, // 0
{0, 1, 1, 0, 0, 0, 0}, // 1
{1, 1, 0, 1, 1, 0, 1}, // 2
{1, 1, 1, 1, 0, 0, 1}, // 3
{0, 1, 1, 0, 0, 1, 1}, // 4
{1, 0, 1, 1, 0, 1, 1}, // 5
{1, 0, 1, 1, 1, 1, 1}, // 6
{1, 1, 1, 0, 0, 0, 0}, // 7
{1, 1, 1, 1, 1, 1, 1}, // 8
{1, 1, 1, 1, 0, 1, 1} // 9
};
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < 7; i++) ans[i] = '-';
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int x = s[0] - '0';
int a[10] = {0};
for (int j = 1; j < s.size(); j++)
a[s[j] - 'A'] = 1;
for (int j = 0; j < 7; j++) {
if (a[j] == 1 && book[x][j] == 0) ans[j] = 'X';
if (a[j] == 0 && book[x][j] == 1) ans[j] = 'x';
}
}
for (int i = 0; i < 7; i++) cout << ans[i];
cout << endl;
return0;
}
3. 间谍卫星
3.1 题面描述
的01网格中，有一个边与坐标轴平行的实心正方形：
边界全是 '1'内部和其余位置都是 '0'
输出每个正方形的边长。
输入格式：第一行 表示测试数据组数，接下来每组128行128列网格。
输出格式：每行输出对应网格中正方形的边长。
数据范围：网格固定 ，满分15分。
3.2 思路
正方形边界全为 '1'，所以 '1' 的总数就是周长。
周长 ，所以边长 总数 。
3.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n;
for (int k = 0; k < n; k++) {
int cnt = 0;
for (int i = 0; i < 128; i++) {
cin >> s;
for (int j = 0; j < 128; j++)
if (s[j] == '1') cnt++;
}
cout << cnt / 4 << endl;
}
return0;
}
4. 图灵完备
4.1 题面描述
仅用 ()+[]! 六个字符写一段JavaScript代码，执行结果恰好是给定非负整数 。
输入格式：一个非负整数
输出格式：一段JS代码，输出字符数不超过5000
样例：
输入：
0
输出：
+[]
数据范围：，满分15分。
4.2 思路
根据题目我们可以推测出几个基本原理
+[]在JS中等于0+!![]等于1[表达式]会把表达式结果转成字符串
如果使用 个 相加的话，最终输出会超出限制。我们不直接累加，而是将 转为字符串逐位处理。把 拆成数字每一位，每位用若干个 +!![] 拼出数字，然后以字符的形式全部拼接，最后外层加 +() 转数字。
4.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
string x;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> x;
cout << "(+[";
for (int i = 0; i < x.size(); i++) {
cout << "[";
int num = x[i] - '0';
if (num != 0) {
for (int j = 0; j < num; j++)
cout << "+!![]";
} else {
cout << "+[]";
}
cout << "]";
if (i < x.size() - 1) cout << "+";
}
cout << "])";
return0;
}
5. 数据排序
5.1 题面描述
处理简化的CSV文件，按指定列排序。排序规则用 列名+ 表示升序，列名- 表示降序。
CSV格式：
第一行是标题（全是字符串列） 单元格由半角逗号分隔 数值列全是数字，字符串列至少包含一个字母
关键：稳定排序，即所有排序关键字都相等的行保持原顺序。
输入格式：
第一行 表示行数（含标题） 接下来 行CSV数据 接下来一行 表示排序关键字数 接下来 行每行一个排序规则
输出格式：排序后的完整CSV（含标题行）
样例：
输入：
4
Name,p1,p2,p3,Score
ZhangSan,40,30,28,98
LiSi,40,28,30,98
WangWu,40,25,20,85
3
Score-
Name+
p3-
输出：
Name,p1,p2,p3,Score
LiSi,40,28,30,98
ZhangSan,40,30,28,98
WangWu,40,25,20,85
数据范围：，表格不超过26列，数值0~1000。
5.2 思路
这道题的思路并不复杂，主要是模拟与多关键字稳定排序，代码细节较多。用结构体存每一行，同时记录原始行号 xb。比较时按优先级逐层检查关键字：
数值列转成整数比较 字符串列按字典序比较 所有关键字都相等时比较初始顺序 xb
sort 本身是不稳定排序，但通过 xb 兜底可以实现稳定排序的效果。
5.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
structnode {
int xb; // 原始行号，用于兜底
string sz[15]; // 每列内容
} CSV[105];
int n, x, m;
string sz2[15];
// 查找列名对应的列号
intfindCol(string s){
for (int j = 1; j <= x; j++)
if (CSV[1].sz[j] == s) return j;
return-1;
}
// 字符串转整数
inttoInt(string s){
int sum = 0;
for (char c : s)
sum = sum * 10 + (c - '0');
return sum;
}
// 判断是否全为数字
boolisNum(string s){
for (char c : s)
if (c < '0' || c > '9') returnfalse;
returntrue;
}
// 比较函数
boolcmp(node a, node b){
for (int i = 1; i <= m; i++) {
string colName = sz2[i].substr(0, sz2[i].size() - 1);
int col = findCol(colName);
bool asc = sz2[i].back() == '+';
if (a.sz[col] != b.sz[col]) {
if (isNum(a.sz[col])) {
int ai = toInt(a.sz[col]), bi = toInt(b.sz[col]);
return asc ? ai < bi : ai > bi;
} else {
return asc ? a.sz[col] < b.sz[col] : a.sz[col] > b.sz[col];
}
}
}
return a.xb < b.xb;
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, z;
cin >> n;
for (int i = 1; i <= n; i++) {
CSV[i].xb = i;
cin >> s;
s += ',';
z = "";
x = 0;
for (char c : s) {
if (c == ',') {
x++;
CSV[i].sz[x] = z;
z = "";
} else {
z += c;
}
}
}
cin >> m;
for (int i = 1; i <= m; i++)
cin >> sz2[i];
sort(CSV + 2, CSV + n + 1, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= x; j++) {
cout << CSV[i].sz[j];
if (j != x) cout << ",";
}
cout << "\n";
}
return0;
}
6. AI机器人
6.1 题面描述
网格（），机器人从 出发执行程序。程序包含：
U/D/L/R：向对应方向移动一格，越界或遇到障碍物#则不动(S)n：把子程序 重复 次（ 为1~9）(S)*：AI循环，执行次数由机器人自主决定
求：哪些平地格子无论怎么选 * 循环次数都无法到达。
输入格式：，接下来 行网格，最后一行程序（长度 ）
输出格式： 行输出：
#：障碍物+：可达的平地.：不可达的平地
样例：
输入：
3 7
...#...
...#...
.......
LLLRRRRRRRRDDDDRRRRRRRRR
输出：
+++#...
..+#...
..+++++
数据范围：满分20分。
6.2 思路
本题是省选级别的难题，用 bitset<128> 表示可达位置集合，每个bit对应一个格子。1 表示可能到达，0 表示不可能，同时用一个全局 vis 记录执行过程中所有曾经到达过的位置。
处理 (S)* 时，把每次循环可能停留的位置叠加，直到不再变化。
障碍物用另一个矩阵表示， 1 表示空格，0 表示障碍物。为处理方便在每行最后增加一列障碍物，然后每次移动之后的位置有两个来源：
原位置移位之后与空格的交集 原位置与障碍物反向移位后的交集（即被障碍物挡住停留在原地的情况）
用位运算来处理很方便，将两种情况合并就是移动后的结果了。
直接提交会超时，要加上记忆化搜索，只需要记录关键指令位 ( 的结果。直接记忆化只能过部分数据，因为整个矩阵的状态数是 级别，显然过大。再观察发现其中每个点可以独立计算互不干扰，因此可以将矩阵拆成点之后再对每个点分别记忆化，最后将所有点的结果合并就是完整的结果了，这样每一步最多只需要保存 个结果。
6.3 AC代码
#include<bits/stdc++.h>
usingnamespacestd;
typedefbitset<128> GRID;
int n, m, to[1000];
string path;
GRID blank, vis(1), flag(1);
unordered_map<int, GRID> mp[1000];
GRID move(GRID &g, char ch){
GRID res;
if (ch == 'U')
res = (g >> (m+1) & blank) | (g & ~(blank << (m+1)));
elseif (ch == 'D')
res = (g << (m+1) & blank) | (g & ~(blank >> (m+1)));
elseif (ch == 'L')
res = (g >> 1 & blank) | (g & ~(blank << 1));
elseif (ch == 'R')
res = (g << 1 & blank) | (g & ~(blank >> 1));
vis |= res;
return res;
}
GRID solve(int &ind, int p);
GRID solve2(int &ind, GRID g){
GRID res;
int start = ind;
for (int i = 0; i < n * (m+1); i++)
if (g[i]) {
ind = start;
res |= solve(ind, i);
}
return res;
}
GRID solve(int &ind, int p){
int t = ind;
if (mp[t].find(p) != mp[t].end()) {
ind = to[t];
return mp[t][p];
}
GRID res = flag << p;
while (ind < path.size()) {
char ch = path[ind++];
if (ch == '(') {
int start = ind;
GRID last = res;
res = solve2(ind, last);
if (path[ind] == '*') {
res |= last;
GRID diff = res ^ last;
while (diff.any()) {
last = res;
ind = start;
res = solve2(ind, diff) | last;
diff = res ^ last;
}
} else {
for (int i = 0; i < path[ind] - '1'; i++) {
last = res;
ind = start;
res = solve2(ind, last);
}
}
ind++;
} elseif (ch == ')') {
break;
} else {
res = move(res, ch);
}
}
to[t] = ind;
return mp[t][p] = res;
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
string s;
for (int i = 0, p = 0; i < n; i++, p++) {
cin >> s;
for (int j = 0; j < m; j++, p++)
if (s[j] == '.') blank[p] = 1;
}
cin >> path;
int t = 0;
solve2(t, vis);
for (int i = 0, p = 0; i < n; i++, p++) {
for (int j = 0; j < m; j++, p++) {
if (!blank[p]) cout << '#';
elseif (vis[p]) cout << '+';
elsecout << '.';
}
cout << "\n";
}
return0;
}
文章来源：
四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
