信息与未来2017年真题解析

四季读书网 2026-04-20 13:12:11 1 0

信息与未来2017年真题解析

点评：考古年信息与未来真题，题目从整体难度来看要比最近两年的真题难度低一些，这一变化从侧面反映了信息学奥赛普及程度不断提高、命题思路逐步演进的过程。值得注意的一个技术细节是，部分题目的数据生成采用了线性同余生成器，这类构造方式在当前命题中已较少出现，具有一定“时代特征”。整体来看，这套题目虽然难度不高，但作为参赛者考前的练手与查缺补漏仍具价值。在知识覆盖面上，题目主要考查了数学、枚举、模拟、贪心、容器与算法应用，以及动态规划（）等核心内容。若以为参照，其难度大致分布在级至级之间，适合不同阶段的学生进行针对性训练。

站搜"苏A信奥张教练"有同步视频讲解。张老师作为专职信奥教练多年来指导几十位学生获信息与未来一等奖。年两位学生比赛成绩排名头部分别进入南京外国语信奥校队、金陵河西信奥班。若有辅导需要可联系本人VX:QinHuai-shaonian

[1] 龟兔赛跑

题目描述

兔子又来找乌龟赛跑啦！同样的错误兔子不会犯两次，所以兔子提出赛跑的时候，乌龟就觉得这场比赛很不公平。于是兔子进一步放宽了条件，表示他可以在比赛开始以后先睡分钟再开始追乌龟。

乌龟这下没办法确定比赛到底公平不公平了，所以请你来帮忙。假设乌龟每分钟可以跑米，兔子每分钟跑米。他希望你计算最大的整数赛跑距离 (米)，满足乌龟能在兔子先睡分钟的前提下，比兔子更早或同时到达终点。

输入格式

三个整数。

输出格式

一个整数，表示要求的最长赛跑距离。

输入输出样例 #1

输入 #1

11 21 7

输出 #1

说明/提示

。

本题原始满分为。

解题思路

考查数学问题。比赛开始后兔子先睡分钟，可以得知乌龟在这分钟里已经跑了米；乌龟每分钟可以跑米，兔子每分钟跑米，那么可得出两者的速度差为米/分，即每分钟兔子可以缩小与乌龟的距离为米；在乌龟跑了米时，兔子开始追赶乌龟，如果在终点处刚好追赶上乌龟，追赶的时间为分钟；在这分钟里，兔子跑的距离即为全程距离，为米，此数值即为赛跑距离。但考虑到C++中整数除法的整除可能导致中间计算结果不准确的问题，所以为，最后输出取整后的结果即可。

参考代码

#include <bits/stdc++.h>using namespace std;int main(){    int x, y, t;    cin >> x >> y >> t;    int s = 1.0*t*x/(y-x)*y;    cout << s;    return 0;}

[2] 密码锁

题目描述

乌龟给自己的贵重物品上了密码锁。密码锁上有个数字拨盘。每个数字拨盘每次向上拨使数字增加（向上拨得到），向下拨使数字减少（向下拨得到）。

拨盘上的数字组成一个位数。只要拨盘上的数字变为素数，密码锁就会被解开。素数 (又称质数) 是只能被和它自身整除的大于的自然数。因为乌龟动作实在太慢，他希望你帮他计算如何开锁，使得拨动的总次数最少。

输入格式

一个位数，表示拨盘的初始数字。

输出格式

一个位素数，表示开启密码锁使用的素数（拨动次数最少）。如有多组解，输出满足条件的最大数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

本题原始满分为。

解题思路

考查质数、数位分离和枚举。由于题目限定数字拨盘为位数，所以先把1~99999以内所有的质数都找出来并存进一个数组中。接下来从小到大遍历所有的质数，用初始数字的每一位和当前的质数的每一位进行判断，看初始数字这一位上的数字是向上拨还是向下拨次数会少一些，每次循环求各位拨动的次数和，取最小值即为答案；但最后输出前还要考虑到输出的结果一定是位数，例如得到的质数是这种形式，需要把前导也输出显示。

参考代码

#include <bits/stdc++.h>using namespace std;//判断x是否为质数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 isp[90000] = {0}, cnt = 0;    for(int i = 1; i <= 99999; i++){        if(isPrime(i)) isp[++cnt] = i;    }    int a = n % 10;    int b = n / 10 % 10;    int c = n / 100 % 10;    int d = n / 1000 % 10;    int e = n /10000;    int minx = 9999999, res = 0;    for(int i = 1; i <= cnt; i++){        int aa = isp[i] % 10;        int bb = isp[i] / 10 % 10;        int cc = isp[i] / 100 % 10;        int dd = isp[i] / 1000 % 10;        int ee = isp[i] /10000;        int t1 = min(abs(aa-a),10-abs(aa-a));        int t2 = min(abs(bb-b),10-abs(bb-b));        int t3 = min(abs(cc-c),10-abs(cc-c));        int t4 = min(abs(dd-d),10-abs(dd-d));        int t5 = min(abs(ee-e),10-abs(ee-e));        if(t1+t2+t3+t4+t5 <= minx){            minx = t1+t2+t3+t4+t5;            res = isp[i];        }    }    string s = to_string(res);    int len = 5 - s.size();    while(len--) cout << 0;    cout << res;    return 0;}

[3] 房屋积水

题目描述

乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形状给了你，希望你帮他计算暴雨后屋顶的积水总量。

乌龟的屋顶由顺次排在同一水平线上的个宽度为、高度为整数 (分别给出) 的瓦片组成。例如给定，瓦片的高度分别为，屋顶可以画在下图所示的网格中，灰色格子为瓦片。

暴雨过后，如果一个方格向左右两侧延伸都能到达瓦片占据的方格，它就会积水。所以图中波浪线格子在暴雨后会积水，屋顶的积水方格总数为。

试题中使用的生成数列定义如下：整数在输入中给出。

对于。

输入格式

两个整数，表示屋顶的宽度和生成数列的首项。从左向右数第个瓦片的高度。

输出格式

一个整数，表示暴雨后屋顶积水方格的总数。

输入输出样例 #1

输入 #1

10 1

输出 #1

说明/提示

。

本题原始满分为。

解题思路

考查模拟算法。首先根据题意，使用题目中对的生成方式，生成下图为输入输出样例的图示，其中黄色代表瓦片，红色代表积水。不难看出每组瓦片处如果积水，需要满足当前瓦片的左边、右边都要有比它高的瓦片(注意：比积水处瓦片高的可以不是相邻的)。比当前瓦片高的所有左右瓦片高度中分别找到最大的，然后两者取后，再减去当前瓦片的高度就是积水的数量；例如，编号为瓦片处积水为多少？可以看到编号处瓦片高度为，先遍历编号的左边找比大的所有瓦片中的最大值为，再遍历编号的右边找比大的所有瓦片中的最大值为，那么编号为7最多可以积水为。以此类推，遍历除两端的所有的瓦片，累加后输出即为答案。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;  //给long long类型起别名为llint main(){    int n, r1;    cin >> n >> r1;    ll a[110] = {0, r1%10}, r[110] = {0,r1};    for(int i = 2; i <= n; i++){        r[i] = (r[i-1]*6807+2831)%201701;        a[i] = r[i]%10;    }    int res = 0;    for(int i = 2; i < n; i++){        int max1 = 0, max2 = 0;        for(int p = 1; p < i; p++){            if(a[p] >= a[i] && a[p] >= max1) max1 = a[p];        }        for(int q = i+1; q <= n; q++){            if(a[q] >= a[i] && a[q] >= max2) max2 = a[q];        }        int temp = min(max1, max2);        if(temp == 0) continue;        res += temp - a[i];    }    cout << res;    return 0;}

[4] 任务调度

题目描述

乌龟因为动作太慢，有个任务已经超过截止日期了。乌龟处理第个任务需要单位时间。从时刻开始，乌龟可以选择某项任务，完成它，然后再开始另一项任务，如此往复直到所有任务都被完成。

由于已经超过截止日期，乌龟会为此受到一定的惩罚，惩罚值等于所有任务完成时刻之和。例如，有 2 个任务分别需要和单位时间完成。如果先完成任务 1，惩罚值为；如果先完成任务 2，惩罚值为。

乌龟希望你求出惩罚值最小的完成任务的顺序。

试题中使用的生成数列定义如下：整数在输入中给出。

对于。

输入格式

两个整数，表示任务的数量和生成数列的首项。处理任务的时间。

输出格式

一个整数，表示完成所有任务的最小惩罚值。

输入输出样例 #1

输入 #1

10 2

输出 #1

说明/提示

对于的数据，。

本题原始满分为。

解题思路

考查贪心算法。首先根据题意，使用题目中对的生成方式，生成根据题意，惩罚值等于所有任务完成时刻之和。例如，有个任务分别需要和单位时间完成。如果先完成任务，惩罚值为；如果先完成任务 2，惩罚值为。这提示我们，若有多个任务需要完成，将任务按处理时间从小到大排序完成，可能是最优的方案。假设已经从小到大排序，考虑每个任务的完成时间：

第一个任务：

第二个任务：

第三个任务：

以此类推...

将、、求和后，得到总时刻之和

可以发现，下标越小的a的前方的系数越大，所以的方式可以使总和最小！

的情况下，总和中，可以发现规律为出现次

注：具体证明过程需要利用排序不等式（对于两组实数，顺序乘积和最大，逆序乘积和最小，乱序乘积和介于两者之间）感兴趣的同学可自行查阅，此处不做赘述。

参考代码

#include <bits/stdc++.h>using namespace std;int main(){    int n, r1;    cin >> n >> r1;    int a[1001] = {0, r1%100+1}, r[1001] = {0, r1};    for(int i = 2; i <= n; i++){        r[i] = (r[i-1]*6807+2831)%201701;        a[i] = (r[i]%100)+1;    }    sort(a+1,a+1+n);  //从小到大排序    int res = 0;    for(int i = 1; i <= n; i++){        res += a[i]*(n-i+1);    }    cout << res;    return 0;}

[5] 基因组分析

题目描述

乌龟得到了他的基因组，一个只包含四种字母的字符串。乌龟想起科学家说，基因组中很多片段都多次重复出现，而且这种重复是很有意义的，于是他想计算一下自己基因组里片段的重复情况。

给定一个基因组，其中一个长度为的子串称为一个“-片段”。乌龟希望你计算出基因组中不同的 -片段数量。例如，基因组的 -片段有，其中不同的片段数量有个。

试题中使用的生成数列定义如下：整数在输入中给出。

对于。

输入格式

整数，表示基因组的长度、片段的长度和数列生成的首项。基因组第个字符在的值为时分别为。

输出格式

一个整数，表示不同的 -片段的数量。

输入输出样例 #1

输入 #1

20 2 37

输出 #1

说明/提示

的数据满足；

的数据满足。

本题原始满分为。

解题思路

考查字符串和。首先根据题意，使用题目中对的生成方式，生成。接着根据的值为时分别为，生成得到基因组字符串；下一步是提取所有长度为 k 的字符串，这里可以使用 substr 函数，使用方式是，指的是从下标开始截取长度为的字符串，放入字符串变量中。由于题目中说到要统计有多少个不同的字符串，可以使用容器；会自动去重，每次插入一个子串，它只保留唯一值。因此我们只要把截取的子串放入中，最后输出集合大小即可。

参考代码

#include <bits/stdc++.h>using namespace std;int main(){    int n, k, r1;    cin >> n >> k >> r1;    int r[100001] = {0, r1};    for(int i = 2; i <= n; i++){        r[i] = (r[i-1]*6807+2831)%201701;    }    string s = "";    for(int i = 1; i <= n; i++){        if(r[i]%4 == 0) s += "A";        else if(r[i]%4 == 1) s += "T";        else if(r[i]%4 == 2) s += "C";        else if(r[i]%4 == 3) s += "G";    }    set<string> st;    for(int i = 0; i <= s.size()-k; i++){        string t = s.substr(i, k);        st.insert(t);    }    cout << st.size();    return 0;}

[6] 加强版密码锁

题目描述

乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由个拨盘组成，每个拨盘初始时有一个到之间的整数。向上拨使数字变为，向下拨使数字变为。因为密码锁年久失修，拨盘拨动的次数越多越费力。如果一个拨盘被拨动次，需要花费单位时间。密码锁只有在所有的拨盘上的数字形成一个从左到右严格递增的数列时才会解开。乌龟再次请你帮忙，求解解开密码锁的最少时间。

试题中使用的生成数列定义如下：整数在输入中给出。

对于。

输入格式

两个整数，表示拨盘的数量和数列生成的首项。从左向右数第个拨盘的初始数字为。

输出格式

一个整数，表示解开密码锁的最少时间。

输入输出样例 #1

输入 #1

10 4

输出 #1

说明/提示

的数据满足，所有数据满足。

本题原始满分为。

解题思路

考查二维动态规划，本题难度大概在七级。首先根据题意，使用题中对的生成方式，生成。共有个拨盘，而每个拨盘可以向上转动、也可以向下转动，两个方向转动取最小值。而后逐个处理个拨盘的转动时间，但要注意根据题意相邻的后面的数字要比前面的数字大（严格递增）。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;int dp[110][100]; // dp[i][j]含义：把第i位数字(拨盘)修改为j时的最少消耗时间//计算拨盘从x转换为y时最小消耗的时间int cost(int x, int y){    int c1 = abs(x-y)*abs(x-y);    int c2;    if(x < y) c2 = (x+99-y+1)*(x+99-y+1);    else c2 = (99-x+y+1)*(99-x+y+1);    //cout << c1 << endl << c2 << endl; 测试    return min(c1, c2);}int main(){    int n, r1;    cin >> n >> r1;    int a[101] = {0, r1%100}, r[1001] = {0, r1};    //按照题意生成r数组的值和a数组的值    for(int i = 2; i <= n; i++){        r[i] = (r[i-1]*6807+2831)%201701;        a[i] = r[i]%100;    }    //int x = cost(2,98); 测试    memset(dp, 0x3f, sizeof(dp)); //由于后面要取最小时间，初始dp数组所有值都为最大值    //处理第一个拨盘由a[1]拨动到j时的各自的消耗时间dp[1][j]    for(int j = 0; j <= 99; j++){        dp[1][j] = cost(a[1], j);    }    //从第2个拨盘开始dp,遍历第i个拨盘由a[i]拨动到j时的最小消耗时间    for(int i = 2; i <= n; i++){        for(int j = 0; j <= 99; j++){            for(int k = j+1; k <= 99; k++){ //保证从左到右严格升序，所以k从j+1开始取                dp[i][k] = min(dp[i][k], dp[i-1][j]+cost(a[i], k));//找dp[i][k]的最小值            }        }    }    int minx = INT_MAX;    for(int j = 0; j <= 99; j++){        minx = min(minx, dp[n][j]); //求前n个拨盘都处理完的最小消耗时间    }    cout << minx << endl;    return 0;}

本文地址： https://sjds.net/645330.html

文章来源：四季读书网