信息与未来2018年真题解析
点评：2018年题目难度适中，低于近两年。主要考点：循环、枚举、模拟、数学、高精度、BFS。前4题务必全对，第5题注意高精度乘法实现，第6题为BFS+枚举的最短路问题。建议进行限时模拟，尤其检验前4题在时间压力下的稳定性，为冲击难题打好基础。
B站搜"苏A信奥张教练"有同步视频讲解。张老师作为专职信奥教练多年来指导几十位学生获信息与未来一等奖。2025年两位学生比赛成绩排名头部分别进入南京外国语信奥校队、金陵河西信奥班。若有辅导需要或学习咨询可联系本人VX:QinHuai-shaonian
[1] 圣诞树
题目描述
圣诞树共有 层，从上向下数第 层有 个星星、第 层有 个星星、以此类推，排列成下图所示的形状。
星星和星星之间用绳子连接。第 层的每个星星都向下一层最近的两个星星连一段绳子，最后一层的相邻星星之间连一段绳子。
你能算出如果要布置一棵很大（ 层）的圣诞树，需要买多少段绳子吗？
输入格式
输入一行一个整数 ，圣诞树的层数。
输出格式
输出一行一个整数，代表圣诞树中绳子的段数。
输入输出样例 #1
输入 #1
2输出 #1
3输入输出样例 #2
输入 #2
4输出 #2
15说明/提示
样例解释
样例
层的圣诞树只需 段绳⼦。
样例
参考题图。
数据规模
所有数据满足 。
本题原始满分为 。
解题思路
考查循环和规律观察。通过题目所给示图可以发现：星星共有层，第层有颗星星，前层每颗星星会连接段绳子，那么第层就存在段绳子累加；最后一层为第层，有段绳子，最后再加上即可。
AC代码
#include <bits/stdc++.h>using namespace std;int main(){ int n, res = 0; cin >> n; for(int i = 1; i < n; i++){ res += 2*i; //第i层有i颗星星,2*i段绳 } res += n-1; //最后一层n颗星星,n-1段绳 cout << res; //输出绳子总数 return 0;}[2] 最大公约数
题目描述
输入三个正整数 ，求它们的最大公约数（Greatest Common Divisor）：最大的正整数 ，满足 都是 的倍数，即 。
输入格式
输入一行三个正整数 。
输出格式
输出一行一个整数 ，表示 的最大公约数。
输入输出样例 #1
输入 #1
12 34 56输出 #1
2输入输出样例 #2
输入 #2
28 70 28输出 #2
14说明/提示
样例解释
样例
。
样例
。
数据规模
所有数据满足 。
本题原始满分为 。
解题思路
考查数学和枚举。找三个整数的最小值作为最大公约数的可能上限。从该上限向下枚举，找到第一个能同时整除三个数的数，即为最大公约数并输出；当然也可以使用__函数更简。
AC代码
#include <bits/stdc++.h>using namespace std;int main(){ int x, y, z, res = 1; cin >> x >> y >> z; int b = min(x, min(y, z)); for(int i = b; i >= 1; i--){ if(x % i == 0 && y % i == 0 && z % i == 0){ res = i; break; } } cout << res; return 0;}[3] 双十一
题目描述
每年 月 日，各大网上商店都会有促销活动，因此大家都希望 月 日在周末，就可以更愉快地购物啦。请你写一个程序计算一段时间中， 月 日是周末（周六或周日）的数量。以下关于日期的定义和事实能帮到你：
• 年 月 日是星期一。 • 每年的 月有 天； 月有 天；闰年的 月有 天，非闰年的 月有 天。 • 闰年的计算方法：不能被 整除的年份称为普通年。普通年能被 整除的为闰年，因此 年是闰年， 年不是闰年；能被 整除的年份称为世纪年。世纪年能被 整除的是闰年，因此 年是闰年， 年不是闰年。
输入格式
输入一行两个整数 ，代表需要计算的起止年份。
输出格式
输出一个整数，第 年到第 年中 月 日是周末的年数（包括第 年和第 年）。
输入输出样例 #1
输入 #1
2018 2018输出 #1
1输入输出样例 #2
输入 #2
2018 2100输出 #2
23说明/提示
样例解释
样例
年 月 日是星期日。
样例
年到 年之间共有 个 月 日是周末。
数据规模
所有数据满足 。
本题原始满分为 。
解题思路
考查模拟、枚举。每周天，天一个循环，可以通过取余符号完成这种“循环”的效果。注意余数为代表星期日。先求出第年月日是星期几，然后从年到年进行枚举，算出每一年月日是星期几，判断并计数。注意对闰年的判定。
AC代码
#include <bits/stdc++.h>using namespace std;//判断某年是否为闰年bool isr(int y){ if((y % 400 == 0) || ( y % 4 == 0 && y % 100 != 0)) return true; else return false;}int a[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};int main(){ int x, y; cin >> x >> y; //计算x年的1月1日是星期几 int day = 0; //求1900年1月1日到x年1月1日有多少天 for(int i = 1900; i < x; i++){ day += 365; if(isr(i)) day++; //如果是闰年，额外加1天 } int start = (day+1)%7; //x年1月1日是星期start int cnt = 0, s = 0; for(int i = x; i <= y; i++){ for(int j = 1; j <= 10; j++){ //先求每年的前10个月的天数 s += a[j]; } if(isr(i)) s += 1; //单独判断闰年 s += 11; //再加11天 int b = (start + s - 1) % 7; //求的是11月第11天星期几，所以start+s后还要减1 if(b == 0||b == 6) cnt++; //如果这天是星期六或者星期日，计数加1 s += 50; //11月11日后到本年结束还有50天 } cout << cnt; return 0;}[4] 素数方阵
题目描述
把前 个素数从左上角开始按右、下、左、上、右、下、左、上……的顺序填入 的方阵就得到了蛇形素数方阵。以下是 和 的蛇形素数方阵：
给出 ，你的任务是求出 的蛇形素数方阵，并输出其中某个方格中的数值。
素数，又称质数，是指除 和其自身之外，没有其他约数的大于 的正整数。
输入格式
输入一行三个正整数 。
输出格式
输出一行一个整数，表示 蛇形素数方阵第 行第 列中的数字。
输入输出样例 #1
输入 #1
5 1 4输出 #1
7输入输出样例 #2
输入 #2
5 4 3输出 #2
79说明/提示
样例解释
参考上图 。
数据规模
所有数据满足 。
本题原始满分为 。
解题思路
考查模拟、二维数组和质数判定。由于题中的范围是，也就是说最多会向地图中填充个质数，所以我们先把从小到大排行前的质数筛出来放进一个数组中，然后一个个地把质数填入地图。在填质数的过程中要注意两个问题：①整体方向按照“右下左上”的顺序 ②换方向有两种情况，一是出界、二是未出界但下个位置已经存在质数了。 模拟将地图填充完毕后输出二维数组中的第行第列的数。
AC代码
#include <bits/stdc++.h>using namespace std;int isp[520], cnt = 0; //存质数的数组int mp[23][23]; //模拟地图int main(){ int n, x, y; cin >> n >> x >> y; //3000内大约有400+个质数 for(int i = 2; i <= 3000; i++){ bool f = false; for(int j = 2; j * j <= i; j++){ if(i % j == 0){ f = true; break; } } if(!f) isp[++cnt] = i; //如果i是质数，就把i添加到isp数组中 } int i = 1, j = 1, t = 1; //模拟填数，也可以用方向数组更简洁 while(t <= n*n){ while(j<=n && mp[i][j]==0){ //向右 mp[i][j] = isp[t]; t++; j++; //方向向右时列+1 } j--; //越界后记得“拉”回来，列减1 i++; while(i<=n && mp[i][j]==0){ //向下 mp[i][j] = isp[t]; t++; i++; //方向向下时行+1 } i--; //越界后记得“拉”回来，行减1 j--; while(j>=1 && mp[i][j]==0){ //向左 mp[i][j] = isp[t]; t++; j--; } j++; i--; while(i>=1 && mp[i][j]==0){ //向上 mp[i][j] = isp[t]; t++; i--; } i++; j++; } cout << mp[x][y]; return 0;}[5] 整数乘方
题目描述
定义 的 次幂 （共 个 相乘）。记 的十进制表示转换为字符串后奇数字符（阿拉伯数字 ）的个数为 ，偶数字符（阿拉伯数字 ）的个数为 ，求 的数值。
例如，。
奇数数位用方框标出：，故 ；
偶数数位用方框标出：, 故 。
输入格式
输入一行两个整数 。
输出格式
输出一行一个整数，代表 的值。
输入输出样例 #1
输入 #1
3 12输出 #1
2输入输出样例 #2
输入 #2
5 18输出 #2
-1说明/提示
样例 解释
。
数据规模
的数据满足 ；
所有数据满足 。
本题原始满分为 。
解题思路
考查高精度。得到乘方结果后，逐位遍历结果字符串中每个数字是奇数还是偶数，分别用对应变量计数后作差即可。
AC代码
#include <bits/stdc++.h>using namespace std;string gj_c(string s1, string s2){ //高精度乘法 string s = ""; int a[250] = {0}, b[250] = {0}, c[520] = {0}; int lens1 = s1.size(); int lens2 = s2.size(); for(int i = 0; i < lens1; i++) a[lens1-i] = s1[i] - '0'; //倒序存储 for(int i = 0; i < lens2; i++) b[lens2-i] = s2[i] - '0'; //倒序存储 int lenc = lens1 + lens2; for(int i = 1; i <= lens2; i++){ for(int j = 1; j <= lens1; j++){ c[i+j-1] += a[j] * b[i]; c[i+j] += c[i+j-1] / 10; c[i+j-1] %= 10; } } while(c[lenc] == 0 && lenc > 1) lenc--; //删除前导0 for(int i = lenc; i >= 1; i--){ s += char(c[i] + '0'); } return s; //以字符串形式返回计算结果}int main(){ int a, n; cin >> a >> n; string res = "1"; for(int i = 1; i <= n; i++){ res = gj_c(res, to_string(a)); //累乘 } //cout << res; 测试结果 int A = 0, B = 0; for(int i = 0; i < res.size(); i++){ //遍历结果字符串 int t = res[i]-'0'; if(t%2 == 0) B++; else A++; } cout << A-B; return 0;}[6] 棋盘游戏
题目描述
给定一个十进制数 ，将它转换为二进制字符串并在高位填 以补足 位，就得到了一个长度为 的 字符串，我们用这个字符串表示 的棋盘，按从左到右、从上到下的顺序将 （白子）、（黑子）放入棋盘。
例如，，按顺序填入棋盘（ 白子、 黑子），得到如下棋盘（左边棋盘）：
我们现在可以交换棋盘中相邻（共享一条边的两个格子相邻，因此一个格子至多有 个相邻的格子）的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下（右边棋盘所示）的棋盘，至少需要 步。
对于给定的棋盘（保证棋盘中恰好有 个白子和 个黑子），求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。
输入格式
输入一行一个整数 ，为十进制表示下的棋盘。
输出格式
输出一行一个整数，最少需要交换的步数。
输入输出样例 #1
输入 #1
447输出 #1
3输入输出样例 #2
输入 #2
42405输出 #2
8说明/提示
样例解释
样例
参考上图，将 处的⿊⼦移动到 需要 步。
样例
如下图所示，。
数据规模
的测试数据满足棋盘可以在 次交换内变为白子在上、黑子在下。
所有数据保证 ，且 转换为二进制后恰好有 个 。
本题原始满分为 。
解题思路
考查枚举、、进制。将棋盘状态抽象为位二进制字符串作为节点，从初始状态出发，每次交换相邻的不同数字生成新状态。通过队列层序遍历，首次到达目标状态“前个后个”时的步数即为最少移动次数。
AC代码
#include <bits/stdc++.h>using namespace std;struct Node{ string s; //某阶段的棋盘状态 int step; //到达此状态需要移动的次数};queue<Node> q;int n, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};map<string, bool> vis; //标记某棋盘状态是否出现过string res = "";int a[5][5]; //模拟棋盘void trans(int x){ while(x){ res = to_string(x % 2) + res; x /= 2; } int len = res.size(); int t = 16 - len; while(t--) res = "0" + res; //不够16位就补成16位 //cout << res; 测试}int main(){ cin >> n; trans(n); vis[res] = true; q.push({res, 0}); while(!q.empty()){ string cur = q.front().s; int cnt = q.front().step; q.pop(); if(cur == "0000000011111111"){ //当前队首的棋盘状态是目标,输出步数结束循环 cout << cnt << endl; break; } for(int i = 1; i <= 4; i++){ for(int j = 1; j <= 4; j++){ a[i][j] = cur[4*(i-1)+j-1];//把字符串分布在棋盘,方便判断相邻格子 } } //枚举当前棋盘的每个位置的棋子,能交换就交换,同时记录棋盘状态和步数并入队 for(int i = 1; i <= 4; i++){ for(int j = 1; j <= 4; j++){ for(int k = 0; k < 4; k++){ int nx = i + dx[k], ny = j + dy[k]; if(nx >= 1&&nx <= 4&&ny >= 1&&ny <= 4&&a[i][j] != a[nx][ny]){ swap(cur[4*(i-1)+j-1], cur[4*(nx-1)+ny-1]); //交换对应字符 if(!vis[cur]){ //如果之前标记过就不需要相同状态再入队 vis[cur] = true; q.push({cur, cnt+1}); } swap(cur[4*(i-1)+j-1], cur[4*(nx-1)+ny-1]); //记得恢复回原态 } } } } } return 0;} 
