noip复赛总结归纳c文档格式.docx
- 文档编号:782342
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:45
- 大小:78.05KB
noip复赛总结归纳c文档格式.docx
《noip复赛总结归纳c文档格式.docx》由会员分享,可在线阅读,更多相关《noip复赛总结归纳c文档格式.docx(45页珍藏版)》请在冰点文库上搜索。
%d"
ans);
return0;
}
【年份】2010
二、【题目】2.接水问题
(water.pas/c/cpp)
学校里有一个水房,水房里一共装有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个整数,表示接水所需的总时间。
water.inwater.out
534
44121
【输入输出样例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号i同学接完水,5号同学接替4号同i学开始接水。
第4秒,3人接水。
第4秒结束时,1、2号同学每人的已接水量为4,5号同学的已接水量为1。
1、2、5号i同学接完水,即所有人完成接水。
总接水时间为4秒。
84
2371873270938076163
1≤n≤10000,1≤m≤100且m≤n;
1≤wi≤100。
【算法】把人数分为两部分,一人对一个水龙头,作为第一部分,剩下是第二部分的,每一次从第一部分找一个时间最少人,把第二部分的一个人加进去。
【代码】
#include<
stdio.h>
intw[10005];
inti,j,m,n;
scanf("
m,&
n);
for(i=1;
=m;
i++)//输入1到m的数据到w[i]
w[i]);
for(i=n+1;
i++)
intk=1;
//假设w[k]=w[1]是最小
for(j=2;
j<
=n;
j++)
if(w[k]>
w[j])
k=j;
w[k]+=w[i];
for(i=2;
if(w[k]<
w[i])
k=i;
printf("
w[k]);
return0;
【年份】2010
三、【题目】三国游戏
(sanguo.pas/c/cpp)
小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。
在游戏中,小涵和计算机各执一方,组建各自的军队进行对战。
游戏中共有N位武将(N为偶数且不小于4),任意两个武将之间有一个“默契值”,表示若此两位武将作为一对组合作战时,该组合的威力有多大。
游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了),换句话说,所谓的自由武将不属于任何一方。
游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:
小涵先从自由武将中选出一个加入自己的军队,然后计算机也从自由武将中选出一个加入计算机方的军队。
接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将,直到所有的武将被双方均分完。
然后,程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。
已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:
任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略,例如,游戏中一共有6个武将,他们相互之间的默契值如下表所示
双方选将过程如下所示:
小涵轮到计算机时可选的自由武将计算机计算机选将说明
第一轮5123464小涵手中5号武将与4号的默契值昀高,所以选择4号
第二轮5312641小涵手中的5号和3号武将与自由武将中配对可产生的昀大默契值为29,是由5号与1号配对产生的,因此计算机选择1号
第三轮5362412
小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必胜?
如果有,在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多少?
假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。
为了简化问题,保证对于不同的武将组合,其默契值均不相同。
输入文件名为sanguo.in,共N行。
第一行为一个偶数N,表示武将的个数。
第2行到第N行里,第(i+1)行有(N?
i)个非负整数,每两个数之间用一个空格隔开,表示i号武将和i+1,i+2,……,N号武将之间的默契值(0≤默契值≤1,000,000,000)。
输出文件sanguo.out共1或2行。
若对于给定的游戏输入,存在可以让小涵获胜的选将顺序,则输出1,并另起一行输出所有获胜的情况中,小涵最终选出的武将组合的最大默契值。
如果不存在可以让小涵获胜的选将顺序,则输出0。
sanguo.insanguo.out
6
528162927
233201
83226
3311
121
32
【输入输出样例说明】
首先小涵拿走5号武将;
计算机发现5号武将和剩下武将中的4号默契值最高,于是拿走4号;
小涵接着拿走3号;
计算机发现3、5号武将之一和剩下的武将配对的所有组合中,5号和1号默契值最高,于是拿走1号;
小涵接着拿走2号;
计算机最后拿走6号。
在小涵手里的2,3,5号武将中,3号和5号配合最好,默契值为32,而计算机能推出的最好组合为1号和6号,默契值为27。
结果为小涵胜,并且这个组合是小涵用尽所有方法能取到的最好组合。
8
42241029271258
3181626806
25336115
33201713
15779
450
191
77
对于40%的数据有N≤10。
对于70%的数据有N≤18。
对于100%的数据有N≤500。
【算法】每个武将先找第一大,删掉,再找第一大(就是找第二大),看看是否比现有答案大。
人是必胜的,直接输1和答案。
iostream>
cmath>
cstring>
algorithm>
intn,a[1000][1000],ans,maxx;
for(inti=1;
=n-1;
i++)//输入,a作为邻接矩阵
{
for(intj=i+1;
{
if(i==j)continue;
scanf("
a[i][j]);
a[j][i]=a[i][j];
}
for(intj=1;
if(a[i][j]>
a[i][maxx])maxx=j;
a[i][maxx]=0;
ans=max(ans,a[i][j]);
maxx=1;
1\n%d"
四、【题目】1.数字反转
(reverse.cpp/c/pas)
给定一个整数,请将该数各个位上数字反转得到一个新数。
新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。
【输入】输入文件名为reverse.in。
输入共1行,一个整数N。
【输出】输出文件名为reverse.out。
输出共1行,一个整数,表示反转后的新数。
【输入输出样例1】
123321
【输入输出样例2】
-380-83
【数据范围】
-1,000,000,000≤N≤1,000,000,000。
【算法】其实就是逆序输出一个字符串,但要判断正负,特判0,另外要删除前导0。
这题就是考字符串思想。
chara[20120];
gets(a);
intb,len=strlen(a);
if(a[0]=='
0'
){cout<
<
0;
-'
)cout<
'
;
boolf=0;
for(inti=len-1;
i>
=0;
i--)
if((f==1||a[i]!
='
)&
&
a[i]!
a[i],f=1;
【年份】2011
五、【题目】
2.统计单词数
(stat.cpp/c/pas)
一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。
现在,请你编程实现这一功能,具体要求是:
给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。
注意:
匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例1),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2)。
输入文件名为stat.in,2行。
第1行为一个字符串,其中只含字母,表示给定单词;
第2行为一个字符串,其中只可能包含字母和空格,表示给定的文章。
输出文件名为stat.out。
只有一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从0开始);
如果单词在文章中没有出现,则直接输出一个整数-1。
stat.instat.out
To
tobeornottobeisaquestion
20
【输入输出样例1说明】
输出结果表示给定的单词To在文章中出现两次,第一次出现的位置为0。
stat.instat.outto
DidtheOttomanEmpireloseitspoweratthattime
-1
【输入输出样例2说明】
表示给定的单词to在文章中没有出现,输出整数-1。
1≤单词长度≤10。
1≤文章长度≤1,000,000。
【算法】每遇到一个单词就和原来的进行比对,比对成功后再判断之后是否是空格。
cstdlib>
intmain(void)
chara[1010100],ch[1010];
gets(ch);
for(inti=0;
strlen(a);
i++)
if(a[i]>
a'
a[i]<
z'
)
a[i]=a[i]-'
+'
A'
strlen(ch);
if(ch[i]>
ch[i]<
ch[i]=ch[i]-'
intj=0,ans=0,pl=1111;
for(inti=0;
if(a[i]==ch[j])
j++;
elsej=0;
if(j==strlen(ch)&
a[i+1]=='
'
)
ans++;
if(pl==1111)pl=i-strlen(ch)+1;
if(ans!
=0)
cout<
ans<
"
"
pl;
elsecout<
-1"
六、【题目】1.质因数分解
(prime.cpp/c/pas)
已知正整数n是两个不同的质数的乘积,试求出较大的那个质数。
输入文件名为prime.in。
输入只有一行,包含一个正整数n。
输出文件名为prime.out。
输出只有一行,包含一个正整数p,即较大的那个质数。
【输入输出样例】
prime.inprime.out
217
对于60%的数据,6≤n≤1000。
对于100%的数据,6≤n≤2*109。
【算法】题目说这个数是两个质数的乘积,所以它只有两个因数,我们只要从·
1搜到sqrt(n),找出小的那个因数,再用原数除以它就可以了。
【代码】#include<
#include<
math.h>
intmain(){
intn;
&
for(inti=2;
=sqrt(n);
i++){
if(!
(n%i)){
n/=i;
if(n>
i){
%d\n"
n);
else{
i);
【年份】2012
七、【题目】
2.寻宝
(treasure.cpp/c/pas)
传说很遥远的藏宝楼顶层藏着诱人的宝藏。
小明历尽千辛万苦终于找到传说中的这个藏宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:
寻宝说明书。
说明书的内容如下:
藏宝楼共有N+1层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。
除了顶层外,藏宝楼另有N层,每层M个房间,这M个房间围成一圈并按逆时针方向依次编号为0,…,M-1。
其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。
每个房间里有一个指示牌,指示牌上有一个数字x,表示从这个房间开始按逆时针方向选择第x个有楼梯的房间(假定该房间的编号为k),从该房间上楼,上楼后到达上一层的k号房间。
比如当前房间的指示牌上写着2,则按逆时针方向开始尝试,找到第2个有楼梯的房间,从该房间上楼。
如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着:
“寻宝须知:
帮助你找到每层上楼房间的指示
牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。
请帮助小明算出这个打开宝箱的密钥。
输入文件为treasure.in。
+++++
第一行2个整数N和M,之间用一个空格隔开。
N表示除了顶层外藏宝楼共N层楼,
M表示除顶层外每层楼有M个房间。
接下来N*M行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况,
其中第(i-1)*M+j行表示第i层j-1号房间的情况(i=1,2,…,N;
j=1,2,…,M)。
第一个整数
表示该房间是否有楼梯通往上一层(0表示没有,1表示有),第二个整数表示指示牌上的数
字。
注意,从j号房间的楼梯爬到上一层到达的房间一定也是j号房间。
最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:
房间编号
从0开始)。
输出文件名为treasure.out。
输出只有一行,一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对20123
取模的结果即可。
treasure.in
23
12
03
14
01
15
1
第一层:
treasure.out
5
0号房间,有楼梯通往上层,指示牌上的数字是2;
1号房间,无楼梯通往上层,指示牌上的数字是3;
2号房间,有楼梯通往上层,指示牌上的数字是4;
第二层:
0号房间,无楼梯通往上层,指示牌上的数字是1;
1号房间,有楼梯通往上层,指示牌上的数字是5;
2号房间,有楼梯通往上层,指示牌上的数字是2;
小明首先进入第一层(底层)的1号房间,记下指示牌上的数字为3,然后从这个房间
开始,沿逆时针方向选择第3个有楼梯的房间2号房间进入,上楼后到达第二层的2号房间,
记下指示牌上的数字为2,由于当前房间本身有楼梯通向上层,该房间作为第一个有楼梯的
房间。
因此,此时沿逆时针方向选择第2个有楼梯的房间即为1号房间,进入后上楼梯到达
顶层。
这时把上述记下的指示牌上的数字加起来,即3+2=5,所以打开宝箱的密钥就是5。
对于50%数据,有0<
N≤1000,0<
x≤10000;
对于100%数据,有0<
N≤10000,0<
M≤100,0<
x≤1,000,000。
【算法】利用递推,模拟每一层的情况,我用结构体储存每一间的情况。
第二重循环中,k被多加了一次,应在外面去掉。
为了形成一个环,每走一步都要模一下房间数。
structnode
intnum;
intlt;
};
noderoom[1010][1010];
intn,m;
n,&
m);
for(intj=0;
m;
cin>
>
room[i][j].lt>
room[i][j].num;
intk,ans=0;
k;
ans+=room[i][k].num;
intx=0,y=room[i][k].num;
for(;
x!
=y;
++k)
k%=m;
if(room[i][k].lt==1)x++;
k--;
k%=m;
ans;
}【年份】2012
八、【题目】
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。
通过调
查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。
为了在门口展出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
输入文件flower.in,共2行。
第一行包含两个正整数n和m,中间用一个空格隔开。
第二行有n个整数,每两个整数之间用一个空格隔开,依次表示a1、a2、…an。
输出文件名为flower.out。
输出只有一行,一个整数,表示有多少种方案。
因为方案数可能很多,请输出
方案数对1000007取模的结果。
【输入输出样例1】
flower.in
24
32
【输入输出样例说明】
flower.out
2
有2种摆花的方案,分别是(1,1,1,2),(1,1,2,2)。
括号里的1和2表示两种花,
比如第一个方案是前三个位置摆第一种花,第四
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- noip 复赛 总结 归纳
![提示](https://static.bingdoc.com/images/bang_tan.gif)