信息学奥赛-入门级 题库
文化之旅
【问题描述】
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。
现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。
【输入】
输入文件 culture.in。
第一行为五个整数 N,K,M,S,T,每两个整数之间用一个空格隔开,依次代表国家个数(国家编号为 1 到 N),文化种数(文化编号为 1 到 K),道路的条数,以及起点和终点的编号(保证 S 不等于 T);
第二行为 N 个整数,每两个整数之间用一个空格隔开,其中第 i 个数 Ci,表示国家 i的文化为 Ci。
接下来的 K 行,每行 K 个整数,每两个整数之间用一个空格隔开,记第 i 行的第 j 个数为 aij,aij= 1 表示文化 i 排斥外来文化 j(i 等于 j 时表示排斥相同文化的外来人),aij= 0 表示不排斥(注意 i 排斥 j 并不保证 j 一定也排斥 i)。
接下来的 M 行,每行三个整数 u,v,d,每两个整数之间用一个空格隔开,表示国家 u与国家 v 有一条距离为 d 的可双向通行的道路(保证 u 不等于 v,两个国家之间可能有多条道路)。
【输出】
输出文件名为 culture.out。
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出-1)。
【输入输出样例 1】

【输入输出样例说明】
由于到国家 2 必须要经过国家 1,而国家 2 的文明却排斥国家 1 的文明,所以不可能到达国家 2。
【输入输出样例 2】

【输入输出样例说明】
路线为 1 -> 2。
【数据范围】
对于 20%的数据,有 2≤N≤8,K≤5;
对于 30%的数据,有 2≤N≤10,K≤5;
对于 50%的数据,有 2≤N≤20,K≤8;
对于 70%的数据,有 2≤N≤100,K≤10;
对于 100%的数据,有


#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t;
int c[101];
int a[101][101],road[101][101];
int main()
{
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
{
scanf("%d",&a[i][j]);
a[j][i]=a[i][j];
}
memset(road,0x3f3f3f3f,sizeof(road));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
road[u][v]=road[v][u]=w;
if(a[c[u]][c[v]]==1)
road[u][v]=road[v][u]=0x3f3f3f3f;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j&&i!=k&&j!=k)
{
if(a[i][j]!=1&&a[i][k]!=1&&a[j][k]!=1)
road[i][j]=min(road[i][j],road[i][k]+road[k][j]);
}
}
if(road[s][t]<1001)
cout<<road[s][t]<<endl;
else
cout<<-1<<endl;
}
数字统计
【问题描述】
请统计某个给定范围[L, R]的所有整数中,数字 2 出现的次数。
比如给定范围[2, 22],数字 2 在数2中出现了 1次,在数 12中出现 1 次,在数 20 中出现 1 次,在数 21 中出现 1 次,在数 22 中出现 2 次,所以数字 2 在该范围内一共出现了 6次。
【输入】
输入文件名为 two.in。
输入共 1 行,为两个正整数 L 和 R,之间用一个空格隔开。
【输出】
输出文件名为 two.out。
输出共 1 行,表示数字 2 出现的次数。
【输入输出样例1】

【输入输出样例2】

【数据范围】
1 ≤ L ≤R≤ 10000。
#include<cstdio>
int main()
{
int l,r,i,k,ans=0;
scanf("%d%d",&l,&r);
for(i=l;i<=r;i++)
for(k=i;k>0;k/=10)
if(k%10==2)ans++;
printf("%d\n",ans);
return 0;
}
接水问题
【问题描述】
学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为 1。
现在有 n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从 1到 n 编号,i号同学的接水量为 wi。接水开始时,1 到 m号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj 后,下一名排队等候接水的同学 k马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j 同学第x 秒结束时完成接水, 则 k 同学第 x+1 秒立刻开始接水。 若当前接水人数 n’不足 m,则只有 n’个龙头供水,其它 m−n’个龙头关闭。
现在给出 n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。
【输入】
输入文件名为 water.in。
第 1 行2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。
第 2 行 n 个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。
【输出】
输出文件名为 water.out。
输出只有一行,1 个整数,表示接水所需的总时间。
【输入输出样例1】

【输入输出样例1解释】
第 1 秒,3 人接水。第 1秒结束时,1、2、3 号同学每人的已接水量为 1,3 号同学接完水,4 号同学接替 3 号同学开始接水。
第 2 秒,3 人接水。第 2 秒结束时,1、2 号同学每人的已接水量为 2,4 号同学的已接水量为 1。
第 3 秒,3 人接水。第 3 秒结束时,1、2 号同学每人的已接水量为 3,4 号同学的已接水量为 2。4号同学接完水,5 号同学接替 4 号同学开始接水。
第 4 秒,3 人接水。第 4 秒结束时,1、2 号同学每人的已接水量为 4,5 号同学的已接水量为 1。1、2、5 号同学接完水,即所有人完成接水。
总接水时间为 4 秒。
【输入输出样例2】

【数据范围】
1 ≤ n ≤ 10000,1 ≤m≤ 100 且 m≤ n;
1 ≤wi ≤ 100。
#include <bits/stdc++.h>
using namespace std;
int s[11000],ans;
int main(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> s[i];
}
int t = m + 1;
while(t <= n + m){
for(int i = 1;i <= m;i ++){
s[i]--;
if(s[i] == 0){
s[i] = s[t];
t ++;
}
}
ans ++;
}
cout << ans;
return 0;
}
导弹拦截
【问题描述】
经过 11 年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0 时,则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷:每套系统每天只能设定一次工作半径。而当天的使用代价,就是所有系统工作半径的平方和。
某天,雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段,所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹,请计算这一天的最小使用代价。
【输入】
输入文件名 missile.in。
第一行包含 4 个整数x1、y1、x2、y2,每两个整数之间用一个空格隔开,表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。
第二行包含 1 个整数 N,表示有 N颗导弹。接下来 N行,每行两个整数 x、y,中间用
一个空格隔开,表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。
【输出】
输出文件名 missile.out。
输出只有一行,包含一个整数,即当天的最小使用代价。
【提示】
两个点(x1, y1)、(x2, y2)之间距离的平方是
两套系统工作半径 r1、r2的平方和,是指 r1、r2 分别取平方后再求和,即 
【输入输出样例1】

【样例 1 说明】
样例1中要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为 18 和 0。
【输入输出样例2】

【样例 2 说明】
样例中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为 20 和 10。

【数据范围】
对于 10%的数据,N = 1
对于 20%的数据,1 ≤ N ≤ 2
对于 40%的数据,1 ≤ N ≤ 100
对于 70%的数据,1 ≤ N ≤ 1000
对于 100%的数据,1 ≤ N ≤ 100000,且所有坐标分量的绝对值都不超过 1000。
#include<bits/stdc++.h>
using namespace std;
const int N=100002;
struct fire
{
int x,y;
}a[N];
int f[N];
bool cmp(fire x,fire y)
{
return x.x<y.x;
}
int main()
{
int x1,y1,x2,y2,n,ans=1e9;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[i].x=(x1-x)*(x1-x)+(y1-y)*(y1-y);//不需要考虑坐标为负
a[i].y=(x2-x)*(x2-x)+(y2-y)*(y2-y);
}
sort(a+1,a+n+1,cmp);
for(int i=n;i>=1;i--)
f[i]=max(f[i+1],a[i].y);//其实顺推逆推无所谓
for(int i=1;i<=n;i++)
ans=min(f[i+1]+a[i].x,ans);
printf("%d",ans);
}
多项式输出
【问题描述】
一元 n 次多项式可用如下的表达式表示:

其中,
称为 i 次项,
称为 i 次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项式:
1. 多项式中自变量为 x,从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为 0 的项。
3. 如果多项式 n 次项系数为正,则多项式开头不出现“+”号,如果多项式 n 次项系数为负,则多项式以“-”号开头。
4. 对于不是最高次的项,以“+”号或者“-”号连接此项与前一项,分别表示此项系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于 0 次的项,其系数的绝对值为 1,则无需输出 1)。如果 x 的指数大于 1,则接下来紧跟的指数部分的形式为“x^b”,其中 b 为 x 的指数;如果 x 的指数为 1,则接下来紧跟的指数部分形式为“x”;如果 x 的指数为 0,则仅需输出系数即可。
5. 多项式中,多项式的开头、结尾不含多余的空格。
【输入】
输入文件名为 poly.in,共有 2 行
第一行 1 个整数,n,表示一元多项式的次数。
第二行有 n+1 个整数,其中第 i 个整数表示第 n-i+1 次项的系数,每两个整数之间用空格隔开。
【输出】
输出文件 poly.out 共 1 行,按题目所述格式输出多项式。
【输入输出样例 1】

【输入输出样例 2】

【数据范围】
1≤ n≤ 100,多项式各次项系数的绝对值均不超过 100。
#include<bits/stdc++.h>
using namespace std;
int a[101];
int main() {
int n;
cin>>n;
for(int i=1; i<=n+1; i++)
scanf("%d",&a[i]);
if(a[1]<0)
cout<<'-';
if(abs(a[1])>1)
cout<<abs(a[1]);
cout<<"x^"<<n;
int nn=n-1;
for(int i=2; i<=n+1; i++) {
if(a[i]==0) {
nn--;
continue;
}
if(a[i]>0)
cout<<'+';
else
cout<<'-';
if(abs(a[i])!=1||i==n+1)
cout<<abs(a[i]);
if(nn==1)
cout<<'x';
else if(nn==0)
continue;
else
cout<<"x^"<<nn;
nn--;
}
return 0;
}
分数线划定
【问题描述】
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A 市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第m*150%(向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。
【输入】
输入文件名为 score.in。
第一行,两个整数 n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n),中间用一个空格隔开,其中 n 表示报名参加笔试的选手总数,m 表示计划录取的志愿者人数。输入数据保证 m*150%向下取整后小于等于 n。第二行到第 n+1 行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号 k(1000 ≤ k ≤ 9999)和该选手的笔试成绩 s(1 ≤ s ≤ 100)。数据保证选手的报名号各不相同。
【输出】
输出文件 score.out。
第一行,有两个整数,用一个空格隔开,第一个整数表示面试分数线;第二个整数为进入面试的选手的实际人数。从第二行开始,每行包含两个整数,中间用一个空格隔开,分别表示进入面试的选手的报名号和笔试成绩,按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的顺序输出。
【输入输出样例】

【样例说明】
m*150% = 3*150% = 4.5,向下取整后为 4。保证 4 个人进入面试的分数线为 88,但因为 88
有重分,所以所有成绩大于等于 88 的选手都可以进入面试,故最终有 5 个人进入面试。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5000;
struct people{
int k; //报名号
int s; //笔试成绩
};
int cmp(const people &a, const people &b){
if(a.s != b.s)
return a.s > b.s;
else
return a.k < b.k;
}
int main()
{
int n, m, pass_number;
cin >> n >> m;
people p[n];
pass_number = m * 1.5;
for(int i=0; i<n; i++)
cin >> p[i].k >> p[i].s ;
sort(p, p+n, cmp); //按要求排序
for(int i=pass_number; i<n; i++){
if(p[i].s == p[pass_number-1].s)
pass_number ++;
else
break;
} //考虑分数在及格线的选手有多名的情况
cout << p[pass_number-1].s << " " << pass_number << endl;
for(int i=0; i<pass_number; i++){
cout << p[i].k << " " << p[i].s << endl;
}
return 0;
}
细胞分裂
【问题描述】
Hanks 博士是 BT (Bio-Tech,生物技术) 领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。
Hanks 博士手里现在有 N 种细胞,编号从 1~N,一个第 i 种细胞经过 1 秒钟可以分裂为Si 个同种细胞(Si 为正整数)。现在他需要选取某种细胞的一个放进培养皿,让其自由分裂,进行培养。一段时间以后,再把培养皿中的所有细胞平均分入 M 个试管,形成 M 份样本,用于实验。Hanks 博士的试管数 M 很大,普通的计算机的基本数据类型无法存储这样大的M 值,但万幸的是,M 总可以表示为 m1的 m2 次方,即 M =
,其中 m1,m2 均为基本数据类型可以存储的正整数。
注意,整个实验过程中不允许分割单个细胞,比如某个时刻若培养皿中有 4 个细胞,Hanks 博士可以把它们分入 2 个试管,每试管内 2 个,然后开始实验。但如果培养皿中有 5
个细胞,博士就无法将它们均分入 2 个试管。此时,博士就只能等待一段时间,让细胞们继续分裂,使得其个数可以均分,或是干脆改换另一种细胞培养。
为了能让实验尽早开始,Hanks 博士在选定一种细胞开始培养后,总是在得到的细胞“刚好可以平均分入 M 个试管”时停止细胞培养并开始实验。现在博士希望知道,选择哪种细胞培养,可以使得实验的开始时间最早。
【输入】
输入文件名为 cell.in,共有三行。
第一行有一个正整数 N,代表细胞种数。
第二行有两个正整数 m1,m2,以一个空格隔开, m1
m2 即表示试管的总数 M。
第三行有 N 个正整数,第 i 个数 Si 表示第 i 种细胞经过 1 秒钟可以分裂成同种细胞的个
数。
【输出】
输出文件 cell.out 共一行,为一个整数,表示从开始培养细胞到实验能够开始所经过的
最少时间(单位为秒)。
如果无论 Hanks 博士选择哪种细胞都不能满足要求,则输出整数-1。
【输入输出样例 1】

【输入输出样例 1 说明】
经过 1 秒钟,细胞分裂成 3 个,经过 2 秒钟,细胞分裂成 9 个,……,可以看出无论怎么分
裂,细胞的个数都是奇数,因此永远不能分入 2 个试管。
【输入输出样例 2】

【输入输出样例 2 说明】
第 1 种细胞最早在 3 秒后才能均分入 24 个试管,而第 2 种最早在 2 秒后就可以均分(每
试管 144/(241
)=6 个)。故实验最早可以在 2 秒后开始。
【数据范围】
对于 50%的数据,有 m1
m2 ≤ 30000。
对于所有的数据,有 1≤ N ≤ 10000,1≤ m1 ≤ 30000,1≤ m2 ≤ 10000,1≤ Si≤ 2,000,000,000。
#include <bits/stdc++.h>
using namespace std;
int n,xb[10010],m1,m2,last=0;
int fj[30010]={0};
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
scanf("%d",&n);
scanf("%d%d",&m1,&m2);
while(m1)
{
int sqr = sqrt(m1);
bool bflag = 1;
for(int i=2;i<=sqr&&bflag;i++)
{
while(m1%i==0)
{
fj[i]+=m2;
bflag=0;
m1 /= i;
last=max(last,i);
}
}
if(bflag) {
if(m1) fj[m1]+=m2;
last = max(last,m1);
break;
}
}
int minn = 99999999;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
int maxx = 0;
for(int j = 2;j <= last;j++)
{
if(fj[j])
{
int p = 0;
while(x%j==0&&x){
p++;
x/=j;
}
if(!p) {
maxx = 99999999;
break;
}
maxx = max(maxx,ceil(1.0*fj[j]/p));
}
}
if(minn > maxx) minn = maxx;
}
if(minn==99999999)
printf("-1\n");
else printf("%d\n",minn);
return 0;
}
道路游戏
【问题描述】
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路,马路上有 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;
}
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;
}
排座椅
【问题描述】
上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的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
*/
传球游戏
【问题描述】
上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。
游戏规则是这样的: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;
}
纪念品分组
【题目描述】
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
【输入】
输入文件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;
}
守望者的逃离
【问题描述】
恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为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;
}
开心的金明
【问题描述】
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过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;
}
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;
}
陶陶摘苹果
【问题描述】
陶陶家的院子里有一棵苹果树,每到秋天树上就会结出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
不高兴的津津
【问题描述】
津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴,而且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周她会不会不高兴;如果会的话,哪天最不高兴。
【输入文件】
输入文件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
一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材,售价是30元;每张椅子要用16个单位的木材,售价是20元。使用已有的木材生产桌椅(不一定要用光木材)做多可以买_____元钱。
75名儿童去游乐场玩。他们可以骑旋转木马,坐滑行轨道,乘宇宙飞船。已知其中20人这三种东西都玩过,55人至少玩过其中两种。若每玩一样的费用为5元,游乐场总共收入700,可知有_____名儿童没有玩过其中任何一种。
program program1;
Var
a,b,c,d,e:integer;
begin
a:=79 ; b:=34; c:=57;d:=0 ; e:=-1;
if (a<c) or (b>c) then d:=d+e
else if (d+10<e) then d:=e+10
else d:=e-a;
writeln(d);
end.
输出:_____________________。