首页 › 题库 › 信息学奥赛 › 信息学奥赛-入门级

信息学奥赛-入门级 题库

共 1088 道题 ,第 48 / 55 页 · 按题型筛选,点「查看答案」核对解析
941 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

道路游戏

【问题描述】

小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个机器人工厂和第 i+1 个机器人工厂(1≤ i≤ n-1),第 n 段马路连接第 n 个机器人工厂和第 1个机器人工厂。

游戏过程中,每个单位时间内,每段马路上都会出现一些金币,金币的数量会随着时间发生变化,即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买,机器人一旦被购买,便会沿着环形马路按顺时针方向一直行走,在每个单位时间内行走一次,即从当前所在的机器人工厂到达相邻的下一个机器人工厂,并将经过的马路上的所有金币收集给小新,例如,小新在 i(1≤ i≤ n)号机器人工厂购买了一个机器人,这个机器人会从 i 号机器人工厂开始,顺时针在马路上行走,第一次行走会经过 i 号马路,到达 i+1 号机器人工厂(如果 i=n,机器人会到达第 1 个机器人工厂),并将 i 号马路上的所有金币收集给小新。

游戏中,环形马路上不能同时存在 2 个或者 2 个以上的机器人,并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时,需要给这个机器人设定行走次数,行走次数可以为1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次数。

以下是游戏的一些补充说明:

1. 游戏从小新第一次购买机器人开始计时。

2. 购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。

3. 购买机器人和机器人行走是两个独立的过程,机器人行走时不能购买机器人,购买完机器人并且设定机器人行走次数之后机器人才能行走。

4. 在同一个机器人工厂购买机器人的花费是相同的,但是在不同机器人工厂购买机器人的花费不一定相同。

5. 购买机器人花费的金币,在游戏结束时再从小新收集的金币中扣除,所以在游戏过程中小新不用担心因金币不足,无法购买机器人而导致游戏无法进行。也因为如此,游戏结束后,收集的金币数量可能为负。

现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费,请你告诉小新,经过 m 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币。

【输入】

输入文件名为 game.in。

第一行 3 个正整数,n,m,p,意义如题目所述。

接下来的 n 行,每行有 m 个正整数,每两个整数之间用一个空格隔开,其中第 i 行描

述了 i 号马路上每个单位时间内出现的金币数量(1 ≤ 金币数量 ≤ 100),即第 i 行的第 j

(1≤ j≤ m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。

最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i 号机

器人工厂购买机器人需要花费的金币数量(1≤ 金币数量≤ 100)。

【输出】

输出文件 game.out 共一行,包含 1 个整数,表示在 m 个单位时间内,扣除购买机器人

花费的金币之后,小新最多能收集到多少金币。

【输入输出样例】

【数据范围】

对于 40%的数据,2≤ n≤ 40,1≤ m ≤ 40。

对于 90%的数据,2≤ n≤ 200,1≤ m ≤ 200。

对于 100%的数据,2≤ n≤ 1000,1≤ m≤ 1000,1≤p≤ m。

答案与解析
参考答案

#include <bits/stdc++.h> 

using namespace std;

int n,m,p,b[1001],a[1001][1001],f[1001];

int main(){

    scanf("%d%d%d",&n,&m,&p);//n表示工厂和马路的数量,m表示游戏时间,p表示机器人能穿过的工厂数量 

    memset(f,-1000000,sizeof(f)); 

    f[0]=0;

    for(int i=1; i<=n; i++)

        for(int j=1; j<=m; j++) 

            scanf("%d",&a[i][j]);//a[i,j]表示在第i段马路上 在第j秒时的金币数量 

    for(int i=1; i<=n; i++) 

      scanf("%d",&b[i]);//b[i]表示在第i个工厂购买机器人的价格 

    for(int i=1; i<=m; i++)

        for(int j=1; j<=n; j++){//j表示机器人的编号 

            int pre=j-1;// 机器人上一次在第pre个工厂 

            if(pre==0) pre=n;//如果t等于0(被1减了),那么就是从第n个过来的 

            int sum=a[pre][i];//sum表示在第pre段马路上第i秒时的金币数量 

            for(int k=1; k<=p; k++){//k表示在第i秒时第j个机器人走了k步 

                if(i-k<0) break;//时间不会是负的 

                f[i]=max(f[i],f[i-k]+sum-b[pre]);// f[i]表示第i秒时能获得的最大钱数 

                pre--;

                if(pre==0) pre=n;//跑道环形 

                sum+=a[pre][i-k];

            }

        }

    printf("%d",f[m]);

    return 0;

}

题目详情
942 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

ISBN号码

【问题描述】

每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码,例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言,例如0代表英语;第一个分隔符“-”之后的三位数字代表出版社,例如670代表维京出版社;第二个分隔之后的五位数字代表该书在出版社的编号;最后一位为识别码。

识别码的计算方法如下:

首位数字乘以1加上次位数字乘以2……以此类推,用所得的结果mod 11,所得的余数即为识别码,如果余数为10,则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的:对067082162这9个数字,从左至右,分别乘以1,2,…,9,再求和,即0×1+6×2+……+2×9=158,然后取158 mod 11的结果4作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确,如果正确,则仅输出“Right”;如果错误,则输出你认为是正确的ISBN号码。

【输入】

输入文件isbn.in只有一行,是一个字符序列,表示一本书的ISBN号码(保证输入符合ISBN号码的格式要求)。

【输出】

输出文件isbn.out共一行,假如输入的ISBN号码的识别码正确,那么输出“Right”,否则,按照规定的格式,输出正确的ISBN号码(包括分隔符“-”)。

【输入输出样例1】

【输入输出样例2】

答案与解析
参考答案

#include<stdio.h>

int main()

{

    char ch[100]={0};

    int sum,i;

    while(scanf("%s",ch)!=EOF)

    {

        i=0;

        sum=0;

        sum=sum+(ch[i]-'0');

        for(i=2;i<5;i++)

        {

            sum=sum+((ch[i]-'0')*i);

        }

        for(i=6;i<11;i++)

        {

            sum=sum+((ch[i]-'0')*(i-1));

        }

        sum=sum%11;

        if(sum==10)

        {

            if(ch[12]=='X')

                printf("Right\n");

            else{

                    ch[12]='X';

            printf("%s\n",ch) ;

             }

        }

       else if(sum==(ch[12]-'0'))

        printf("Right\n");

        else

        {

            ch[12]=(char)(sum+'0');

            printf("%s\n",ch);

 

        }

    }return 0;

}

题目详情
943 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

排座椅

【问题描述】

    上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生对数最少。

【输入】

输入文件seat.in的第一行,有5各用空格隔开的整数,分别是M,N,K,L,D(2<=N,M<=1000,0<=K<M,0<=L<N,D<=2000)。

接下来D行,每行有4个用空格隔开的整数,第i行的4个整数Xi,Yi,Pi,Qi,表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。

输入数据保证最优方案的唯一性。

【输出】

输出文件seat.out共两行。

第一行包含K个整数,a1a2……aK,表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道,其中ai< ai+1,每两个整数之间用空格隔开(行尾没有空格)。

第二行包含L个整数,b1b2……bk,表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道,其中bi< bi+1,每两个整数之间用空格隔开(行尾没有空格)。

【输入输出样例】

【输入输出样例解释】

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

struct node{

int x1,x2,y1,y2;

}a[2005];

bool cmp(int a,int b){

    return a>b;

}

int k1[1005],l1[1005],l2[1005],k2[1005],ansk[1000],ansl[1000];

int n,m,k,l,d,z=1,y=1;

int main(){

//freopen("seat.in","r",stdin);

//freopen("seat.out","w",stdout);

cin>>n>>m>>k>>l>>d;

for(int i=1;i<=d;i++){

cin>>a[i].x1>>a[i].x2>>a[i].y1>>a[i].y2;

if(a[i].x2==a[i].y2) k1[min(a[i].x1,a[i].y1)]++;//这块可以对照图理解一下 

else if(a[i].x1==a[i].y1) l1[min(a[i].x2,a[i].y2)]++;

} 

memcpy(k2,k1,sizeof(k1));

memcpy(l2,l1,sizeof(l1));

sort(k1+1,k1+n,cmp);//排序 

sort(l1+1,l1+m,cmp);

for(int i=1;i<=k;i++){//重新匹配 

for(int j=1;j<n;j++){

if(k2[j]==k1[i]){

k2[j]=0;//去重 

ansk[i]=j;

break;

} 

}

}

for(int i=1;i<=l;i++){//重新匹配 

for(int j=1;j<m;j++){

if(l2[j]==l1[i]){

l2[j]=0;//去重 

ansl[i]=j;

break;

} 

}

}

sort(ansk+1,ansk+k+1);//特别坑,输出要按顺序 

sort(ansl+1,ansl+l+1);

for(int i=1;i<=k;i++){

cout<<ansk[i]<<" ";

}

cout<<endl;

for(int i=1;i<=l;i++){

cout<<ansl[i]<<" ";

}

return 0;

}/*

4 5 1 2 3

4 2 4 3

2 3 3 3

2 5 2 4

*/

题目详情
944 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

传球游戏

【问题描述】

上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。

游戏规则是这样的:n个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号,并假设小蛮为1号,球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1,共2种。

【输入】

输入文件ball.in共一行,有两个用空格隔开的整数n,m(3<=n<=30,1<=m<=30)。

【输出】

输出文件ball.out共一行,有一个整数,表示符合题意的方法数。

【输入输出样例】

【限制】

40%的数据满足:3<=n<=30,1<=m<=20

100%的数据满足:3<=n<=30,1<=m<=30

答案与解析
参考答案

#include<stdio.h>

#include<iostream>

using namespace std;

int ans[31][31];

int main()

{

int n, m;

cin >> n >> m;

//ans[i][j]=ans[i-1][j-1]+ans[i+1][j-1]

ans[1][0] = 1;

for (int j = 1; j <= m;j++) //务必次数放在第一层循环

for (int i = 1; i <= n; i++)

{

int a = i - 1;//a为左边的同学

int b = i + 1;//b为右边的同学

if (a == 0)a = n;//如果超出限制就改变一下

if (b > n)b = 1;

ans[i][j] = ans[a][j - 1] + ans[b][j - 1];

}

cout << ans[1][m];

return 0;

}

题目详情
945 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

立体图

【问题描述】

小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。

小渊有一块面积为m*n的矩形区域,上面有m*n个边长为1的格子,每个格子上堆了一些同样大小的吉姆(积木的长宽高都是1),小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放:

每个顶点用1个加号’+’表示,长用3个”-“表示,宽用1个”/”表示,高用两个”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为43,45,47,124。字符’.’(ASCII码46)需要作为背景输出,即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则:

立体图中,定义位于第(m,1)的格子(即第m行第1列的格子)上面自底向上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。

【输入】

输入文件drawing.in第一行有用空格隔开的两个整数m和n,表示有m*n个格子(1<=m,n<=50)。

接下来的m行,是一个m*n的矩阵,每行有n个用空格隔开的整数,其中第i行第j列上的整数表示第i行第j列的格子上摞有多少个积木(1<=每个格子上的积木数<=100)。

【输出】

输出文件drawing.out中包含题目要求的立体图,是一个K行L列的字符矩阵,其中K和L表示最少需要K行L列才能按规定输出立体图。

【输入输出样例】

答案与解析
参考答案

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

int n,m,k,l;

int a[101][101];

char c[6][8]={

"  +---+",

" /   /|",

"+---+ |",

"|   | +",

"|   |/ ",

"+---+  "

},ans[1001][1001];

int start[6]={0,0,0,0,1,2},end[6]={5,6,7,7,7,7};//只能覆盖到这些区域,其他的不能覆盖

void add(int y,int x){

k=max(k,x+5);//如题

l=max(l,y+6);

for(int i=x;i<x+6;i++)

for(int j=y+start[i-x];j<y+end[i-x];j++)

ans[i][j]=c[x+5-i][j-y];//因为是倒着的要注意一下

}

int main(){

for(int i=0;i<999;i++)

for(int j=0;j<999;j++)

ans[i][j]='.';//初始值即为背景

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

scanf("%d",&a[i][j]);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

    for(int h=1;h<=a[i][j];h++)

        add(2*(n-i)+4*(j-1),2*(n-i)+3*(h-1));//公式

for(int i=k;i>=0;i--){//倒着输出

for(int j=0;j<=l;j++)

    printf("%c",ans[i][j]);

printf("\n");//换行

}

    return 0;

}

题目详情
946 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

奖学金

【问题描述】

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。

任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:

7 279

5 279

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279

7 279

则按输出错误处理,不能得分。

【输入】

输入文件scholar.in包含n+1行:

第1行为一个正整数n,表示该校参加评选的学生人数。

第2到n+1行,每行有3个用空格隔开的数字,每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输入数据的行号减1)。

 所给的数据都是正确的,不必检验。

【输出】

输出文件scholar.out共有5行,每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。

【输入输出样例1】

【输入输出样例2】

【限制】

    50%的数据满足:各学生的总成绩各不相同

    100%的数据满足:6<=n<=300

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

long long a[100100];

struct student{

int a,b,c;//语文,数学,英语;

int id;

int sum; 

};

bool cmp(student da,student db){

if(da.sum!=db.sum){

return da.sum>db.sum;//总分比较。 

}else if(da.a!=db.a){

return da.a>db.a;//语文成绩比较。 

}

return da.id<db.id;//编号比较。 

}

int main() {

int n;

cin>>n;

student stu[n];

for(int i=0;i<n;i++){

cin>>stu[i].a>>stu[i].b>>stu[i].c;

stu[i].id=i+1;

stu[i].sum=stu[i].a+stu[i].b+stu[i].c;//总和。 

}

stable_sort(stu,stu+n,cmp);

for(int i=0;i<5;i++){

cout<<stu[i].id<<" "<<stu[i].sum<<endl;

}

return 0; 

}

题目详情
947 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

纪念品分组

【题目描述】

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。


【输入】

    输入文件group.in包含n+2行:

    第1行包括一个整数w,为每组纪念品价格之和的上限。

    第2行为一个整数n,表示购来的纪念品的总件数。

    第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。


【输出】

    输出文件group.out仅一行,包含一个整数,即最少的分组数目。


【输入输出样例】

【限制】

    50%的数据满足:1 <= n <= 15

    100%的数据满足:1 <= n <= 30000, 80 <= w <= 200

答案与解析
参考答案

#include <stdio.h>

#include <stdlib.h>

#define MAXN 30010

int save[MAXN];

int n,l,r,ans,max;

int cmp(const void *a,const void *b)

{

   return  *(int *)a- *(int *)b;

   

}

int main()

{

    scanf("%d%d",&max,&n);

    for (int i = 0; i < n; ++i)

        scanf("%d",&save[i]);

    qsort(save,n,sizeof(int),cmp);    //排序

    r = n - 1;

    l=0;

    while (l <= r)

    {

        if (save[l] + save[r] <= max)     //大加小,与规定价格比较

        {

            ++l;

            --r;

            ++ans;

        }

        else

        {

            --r;

            ++ans;

        }

    }

    printf("%d\n",ans);

    return 0;

}

题目详情
948 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

守望者的逃离

【问题描述】

   恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。距离的单位为米(m)。

【输入】

    输入文件escape.in仅一行,包括空格隔开的三个非负整数M, S, T。

【输出】

    输出文件escape.out包含两行:

    第1行为字符串“Yes”或“No”(区分大小写),即守望者是否能逃离荒岛。

    第2行包含一个整数。第一行为“Yes”(区分大小写)时表示守望者逃离荒岛的最短时间;第一行为“No”(区分大小写)时表示守望者能走的最远距离。

【输入输出样例1】

【输入输出样例2】

【限制】 

    30%的数据满足:1 <= T <= 10, 1 <= S <= 100

    50%的数据满足:1 <= T <= 1000, 1 <= S <= 10000

    100%的数据满足:1 <= T <= 300000, 0 <= M <= 1000, 1 <= S <= 108.

答案与解析
参考答案

#include <algorithm>

  #include <iostream>

  

  using namespace std;

  

  int m,s,t;

  int now_s,now_time;

  int nows,tim;

  

 int main()

 {

     cin>>m>>s>>t;

     while(now_time<t&&s>now_s)

     {

         now_s+=17;

         if(m>=10) m-=10,nows+=60;

         else m+=4;

         now_s=max(now_s,nows);

         now_time++;

     }

     if(now_s<s||now_time>t) cout<<"No"<<endl<<now_s;

     else cout<<"Yes"<<endl<<now_time;

     return 0;

 }

题目详情
949 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 9.1 线性动态规划

Hanoi双塔问题

【问题描述】

给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘;

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序;

任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。

【输入】

输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。

【输出】

输出文件hanoi.out仅一行,包含一个正整数, 为完成上述任务所需的最少移动次数An。


【输入输出样例1】

【输入输出样例2】

【限制】

    对于50%的数据,1<=n<=25

    对于100%的数据,1<=n<=200

 

【提示】

    设法建立An与An-1的递推关系式。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

 

int a[1000],len_a;

int main()

{

    int n,len;

    freopen("hanoi.in","r",stdin);

    freopen("hanoi.out","w",stdout);

cin>>n;

    a[1]=2; //第一个2次 

    len_a=1; //数字长度为1 

    for(int i=1;i<=n;i++) // 做n次*2的高精乘法 

    {

        

        for(int j=len_a;j>=1;j--) // 从高位做起 

        {

            a[j]=a[j]*2; //乘2 

            if(a[j]>=10)  //进位 

            {

                a[j+1]++;

                a[j]-=10;

            }

        }

        while(a[len_a+1]>0) len_a++; //进最高位 

    }

    a[1]=a[1]-2;  // 不能忘记-2 

    for(int i=len_a;i>=1;i--) //输出 

        cout<<a[i];

    fclose(stdin);

    fclose(stdout);

    return 0;

}

题目详情
950 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

明明的随机数

【问题描述】

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入文件】

输入文件random.in 有2行,第1行为1个正整数,表示所生成的随机数的个数:

N

第2行有N个用空格隔开的正整数,为所产生的随机数。

【输出文件】

输出文件random.out 也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

【输入样例】

  10

  20 40 32 67 40 20 89 300 400 15

【输出样例】

  8

  15 20 32 40 67 89 300 400

答案与解析
参考答案

#include<stdio.h>

  int main(){

      int N,a[1001]={0},t,i;

      int count=0; 

     scanf("%d",&N);

      for(i=0;i<N;i++){

         scanf("%d",&t);

          if(a[t]==0){

              a[t]=t;

             count++;

        }

     }

     printf("%d\n",count);

     for(i=0;i<1001;i++){

         if(a[i]!=0)

             printf("%d ",a[i]);

     }

     return 0;

 }

题目详情
951 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

开心的金明

【问题描述】

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)

请你帮助金明设计一个满足要求的购物单。

【输入文件】

输入文件happy.in 的第1行,为两个正整数,用一个空格隔开:

N m

(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)

从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数

v p

(其中v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5))

【输出文件】

输出文件happy.out只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。

【输入样例】

1000 5

800 2

400 5

300 5

400 3

200 2

【输出样例】

3900

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int n,m;

int v[26],p[26];

int f[30001];

int main(){

scanf("%d%d",&m,&n);

for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&p[i]),p[i]*=v[i];

for(int i=1;i<=n;i++)

for(int j=m;j>=v[i];j--)

f[j]=max(f[j],f[j-v[i]]+p[i]);

printf("%d",f[m]);

return 0;

}

题目详情
952 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

Jam的计数法

【问题描述】

Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数,而是使用小写英文字母计数,他觉得这样做,会使世界更加丰富多彩。在他的计数法中,每个数字的位数都是相同的(使用相同个数的字母),英文字母按原先的顺序,排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中,每个字母互不相同,而且从左到右是严格递增的。每次,Jam还指定使用字母的范围,例如,从2到10,表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5,那么,紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。(如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”,则U<V< span>,且不存在Jam数字P,使U<P<V< span>)。你的任务是:对于从文件读入的一个Jam数字,按顺序输出紧接在后面的5个Jam数字,如果后面没有那么多Jam数字,那么有几个就输出几个。

【输入文件】

输入文件counting.in 有2行,第1行为3个正整数,用一个空格隔开:

s t w

(其中s为所使用的最小的字母的序号,t为所使用的最大的字母的序号。w为数字的位数,这3个数满足:1≤s<T< span>≤26, 2≤w≤t-s ) 

第2行为具有w个小写字母的字符串,为一个符合要求的Jam数字。

所给的数据都是正确的,不必验证。

【输出文件】

输出文件counting.out 最多为5行,为紧接在输入的Jam数字后面的5个Jam数字,如果后面没有那么多Jam数字,那么有几个就输出几个。每行只输出一个Jam数字,是由w个小写字母组成的字符串,不要有多余的空格。

【输入样例】

  2 10 5

  bdfij

【输出样例】

bdghi

bdghj

bdgij

bdhij

befgh

答案与解析
参考答案

#include<cstdio>

 

int main()

{

int s,t,w,num[26];

scanf("%d %d %d\n",&s,&t,&w);

for(int i=0;i<w;i++){

num[i]=getchar();

num[i]=num[i]-'a'+1;

}

for(int k=0;k<5;k++)

for(int i=w-1;i>=0;i--){

if(num[i]+1<=t-(w-1-i)){

num[i]+=1;

for(int j=i+1;j<w;j++)num[j]=num[i]+j-i;

for(int i=0;i<w;i++)printf("%c",num[i]+'a'-1);

printf("\n");

break;

}

}

 

return 0;

}

题目详情
953 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 1.2 进制与编码

数列

【问题描述】

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:

1,3,4,9,10,12,13,…

(该序列实际上就是:30,31,30+31,32,30+32,31+32,30+31+32,…)

请你求出这个序列的第N项的值(用10进制数表示)。

例如,对于k=3,N=100,正确答案应该是981。

【输入文件】

输入文件sequence.in 只有1行,为2个正整数,用一个空格隔开:

k N

(k、N的含义与上述的问题描述一致,且3≤k≤15,10≤N≤1000)。

【输出文件】

输出文件sequence.out 为计算结果,是一个正整数(在所有的测试数据中,结果均不超过2.1*109)。(整数前不要有空格和其他符号)。

【输入样例】

  3 100

【输出样例】

981

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
954 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

陶陶摘苹果

【问题描述】

陶陶家的院子里有一棵苹果树,每到秋天树上就会结出10个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。

现在已知10个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。

【输入文件】

输入文件apple.in包括两行数据。第一行包含10个100到200之间(包括100和200)的整数(以厘米为单位)分别表示10个苹果到地面的高度,两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间(包含100和120)的整数(以厘米为单位),表示陶陶把手伸直的时候能够达到的最大高度。

【输出文件】

输出文件apple.out包括一行,这一行只包含一个整数,表示陶陶能够摘到的苹果的数目。

【样例输入】

100 200 150 140 129 134 167 198 200 111

110

【样例输出】

5

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
955 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

校门外的树

【问题描述】

某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。

【输入文件】

输入文件tree.in的第一行有两个整数:L(1 <= L <= 10000)和 M(1 <= M <= 100),L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。

【输出文件】

输出文件tree.out包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。

【样例输入】

500 3

150 300

100 200

470 471

【样例输出】

298

【数据规模】

对于20%的数据,区域之间没有重合的部分;

对于其它的数据,区域之间有重合的情况。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
956 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

采药

【问题描述】

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。” 

如果你是辰辰,你能完成这个任务吗?

【输入文件】

输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

【输出文件】

输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

【样例输入】

70 3

71 100

69 1

1 2

【样例输出】

3

【数据规模】

对于30%的数据,M <= 10;

对于全部的数据,M <= 100。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
957 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

循环

【问题描述】

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。

众所周知,2的正整数次幂最后一位数总是不断的在重复2,4,8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:

这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数n的正整数次幂来说,它的后k位是否会发生循环?如果循环的话,循环长度是多少呢?

注意:

1.  如果n的某个正整数次幂的位数不足k,那么不足的高位看做是0。

2.  如果循环长度是L,那么说明对于任意的正整数a,n的a次幂和a + L次幂的最后k位都相同。

【输入文件】

输入文件circle.in只有一行,包含两个整数n(1 <= n < 10100)和k(1 <= k <= 100),n和k之间用一个空格隔开,表示要求n的正整数次幂的最后k位的循环长度。

【输出文件】

输出文件circle.out包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。

【样例输入】

32 2

【样例输出】

4

【数据规模】

对于30%的数据,k <= 4;

对于全部的数据,k <= 100。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
958 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

不高兴的津津

【问题描述】

津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴,而且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周她会不会不高兴;如果会的话,哪天最不高兴。

【输入文件】

输入文件unhappy.in包括七行数据,分别表示周一到周日的日程安排。每行包括两个小于10的非负整数,用空格隔开,分别表示津津在学校上课的时间和妈妈安排她上课的时间。

【输出文件】

输出文件unhappy.out包括一行,这一行只包含一个数字。如果不会不高兴则输出0,如果会则输出最不高兴的是周几(用1, 2, 3, 4, 5, 6, 7分别表示周一,周二,周三,周四,周五,周六,周日)。如果有两天或两天以上不高兴的程度相当,则输出时间最靠前的一天。

【样例输入】

5 3

6 2

7 2

5 3

5 4

0 4

0 6

【样例输出】

3

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
959 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

花生采摘

【问题描述】

鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!——熊字”。

鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图1)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”

我们假定多多在每个单位时间内,可以做下列四件事情中的一件:

1)      从路边跳到最靠近路边(即第一行)的某棵花生植株;

2)      从一棵植株跳到前后左右与之相邻的另一棵植株;

3)      采摘一棵植株下的花生;

4)      从最靠近路边(即第一行)的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分别为13, 7, 15, 9。沿着图示的路线,多多在21个单位时间内,最多可以采到37个花生。

【输入文件】

输入文件peanuts.in的第一行包括三个整数,M, N和K,用空格隔开;表示花生田的大小为M * N(1 <= M, N <= 20),多多采花生的限定时间为K(0 <= K <= 1000)个单位时间。接下来的M行,每行包括N个非负整数,也用空格隔开;第i + 1行的第j个整数Pij(0 <= Pij <= 500)表示花生田里植株(i, j)下花生的数目,0表示该植株下没有花生。

【输出文件】

输出文件peanuts.out包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以采到花生的个数。

【样例输入1】

6 7 21

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

【样例输出1】

37

【样例输入2】

6 7 20

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

【样例输出2】

28

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
960 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

FBI树

【问题描述】

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1) T的根结点为R,其类型与串S的类型相同;

2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。

【输入文件】

输入文件fbi.in的第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2N的“01”串。

【输出文件】

输出文件fbi.out包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。

【样例输入】

3

10001011

【样例输出】

IBFBBBFIBFIIIFF

【数据规模】

对于40%的数据,N <= 2;

对于全部的数据,N <= 10。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情