9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

noip复赛总结归纳(c++)



noip 复赛总结归纳(2010 至 2015 年 c++普及组复赛试题) 一、【题目】1.数字统计 (two.pas/c/cpp) 【问题描述】 请统计某个给定范围[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】 two.in two.out 2 22 6 【输入输出样例 2】 two.in two.out 2 100 20 【数据范围】 1 ≤ L ≤ R≤ 10000。 【算法】把每一位分出来,一一判断 【代码】#include<cstdio> using namespace std; int main() { int r,l,ans=0; scanf("%d%d",&r,&l); for(int i=r;i<=l;i++)//一一判断 { int num=i; while(num>0)//把每一位分离 { if(num%10==2) ans++; num/=10; }

} printf("%d",ans); return 0; } 【年份】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 个整数,表示接水所需的总时间。 【输入输出样例 1】 water.in water.out 5 3 4 4 4 1 2 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 号 i 同学接完水,5 号同学接替 4 号同 i 学开始接水。 第 4 秒,3 人接水。第 4 秒结束时,1、2 号同学每人的已接水量为 4,5 号同 学的已接水量为 1。1、2、5 号 i 同学接完水,即所有人完成接水。 总接水时间为 4 秒。

【输入输出样例 2】 water.in water.out 8 4 23 71 87 32 70 93 80 76 163 【数据范围】 1 ≤ n ≤ 10000,1 ≤m≤ 100 且 m≤ n; 1 ≤ wi ≤ 100。 【算法】把人数分为两部分,一人对一个水龙头,作为第一部分,剩下是第二部 分的,每一次从第一部分找一个时间最少人,把第二部分的一个人加进去。 【代码】 #include<stdio.h> int w[10005]; int main() { int i,j,m,n; scanf("%d%d",&m,&n); for (i=1;i<=m;i++)//输入 1 到 m 的数据到 w[i] scanf("%d",&w[i]); for (i=n+1;i<=m;i++) { int k=1;//假设 w[k]=w[1]是最小 for (j=2;j<=n;j++) if (w[k]>w[j]) k=j; w[k]+=w[i]; } int k=1; for (i=2;i<=n;i++) if (w[k]<w[i]) k=i; printf("%d",w[k]); return 0; } 【年份】2010 三、【题目】三国游戏 (sanguo.pas/c/cpp) 【问题描述】 小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。 在游戏中, 小涵和计算机各执一方, 组建各自的军队进行对战。 游戏中共有 N 位 武将(N 为偶数且不小于 4),任意两个武将之间有一个“默契值”,表示若此 两位武将作为一对组合作战时,该组合的威力有多大。游戏开始前,所有武将都

是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么 他就不再是自由武将了),换句话说,所谓的自由武将不属于任何一方。游戏开 始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵先 从自由武将中选出一个加入自己的军队, 然后计算机也从自由武将中选出一个加 入计算机方的军队。接下来一直按照“小涵→计算机→小涵→??”的顺序选择 武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对 默契值最高的武将组合代表自己的军队进行二对二比武, 拥有更高默契值的一对 武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。 已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合, 它采 取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每 个武将与当前每个自由武将进行一一配对, 找出所有配对中默契值最高的那对武 将组合,并将该组合中的自由武将选入自己的军队。 下面举例说明计算机的选将策略,例如,游戏中一共有 6 个武将,他们相互之 间的默契值如下表所示

双方选将过程如下所示: 小涵 轮到计算机时可选的自由武将 计算机 计算机选将说明 第一轮 5 1 2 3 4 6 4 小涵手中 5 号武将与 4 号的默契值昀高, 所以选 择 4号 第二轮 5 3 1 2 6 4 1 小涵手中的 5 号和 3 号武将与自由武将中配对可 产生的昀大默契值为 29,是由 5 号与 1 号配对产生的,因此计算机选择 1 号 第三轮 5 3 6 2 4 1 2 小涵想知道, 如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有 可能必胜?如果有, 在所有可能的胜利结局中,自己那对用于比武的武将组合的 默契值最大是多少? 假设整个游戏过程中, 对战双方任何时候均能看到自由武将队中的武将和对方军 队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。 【输入】 输入文件名为 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。

【输入输出样例 1】 sanguo.in sanguo.out 6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12 1 32 【输入输出样例说明】 首先小涵拿走 5 号武将; 计算机发现 5 号武将和剩下武将中的 4 号默契值最高, 于是拿走 4 号;小涵接着拿走 3 号;计算机发现 3、5 号武将之一和剩下的武 将配对的所有组合中,5 号和 1 号默契值最高,于是拿走 1 号;小涵接着拿走 2 号;计算机最后拿走 6 号。在小涵手里的 2,3,5 号武将中,3 号和 5 号配 合最好, 默契值为 32, 而计算机能推出的最好组合为 1 号和 6 号, 默契值为 27。 结果为小涵胜,并且这个组合是小涵用尽所有方法能取到的最好组合。 【输入输出样例 2】 sanguo.in sanguo.out 8 42 24 10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 1 77 【数据范围】 对于 40%的数据有 N ≤ 10。 对于 70%的数据有 N ≤ 18。 对于 100%的数据有 N ≤ 500。 【算法】每个武将先找第一大,删掉,再找第一大(就是找第二大),看看是否 比现有答案大。人是必胜的,直接输 1 和答案。 【代码】 #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,a[1000][1000],ans,maxx; int main()

{ scanf("%d",&n); for(int i=1;i<=n-1;i++)//输入,a 作为邻接矩阵 { for(int j=i+1;j<=n;j++) { if(i==j)continue; scanf("%d",&a[i][j]); a[j][i]=a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]>a[i][maxx])maxx=j; } a[i][maxx]=0; for(int j=1;j<=n;j++) ans=max(ans,a[i][j]); maxx=1; } printf("1\n%d",ans); return 0; } 【年份】2010 四、【题目】1.数字反转 (reverse.cpp/c/pas) 【问题描述】 给定一个整数, 请将该数各个位上数字反转得到一个新数。新数也应满足整数的 常见形式, 即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为 零(参见样例 2)。 【输入】输入文件名为 reverse.in。输入共 1 行,一个整数 N。 【输出】输出文件名为 reverse.out。输出共 1 行,一个整数,表示反转后的 新数。 【输入输出样例 1】 123 321 【输入输出样例 2】 -380 -83 【数据范围】 -1,000,000,000 ≤ N ≤ 1,000,000,000。

【算法】其实就是逆序输出一个字符串,但要判断正负,特判 0,另外要删除前 导 0。这题就是考字符串思想。 【代码】 #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { char a[20120]; gets(a); int b,len=strlen(a); if(a[0]=='0'){cout<<0;return 0;} if(a[0]=='-')cout<<'-'; bool f=0; for(int i=len-1;i>=0;i--) if((f==1||a[i]!='0')&&a[i]!='-')cout<<a[i],f=1; return 0; } 【年份】2011 五、【题目】 2.统计单词数 (stat.cpp/c/pas) 【问题描述】 一般的文本编辑器都有查找单词的功能, 该功能可以快速定位特定单词在文章中 的位置,有的还能统计出特定单词在文章中出现的次数。现在,请你编程实现这 一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和 第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给 定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同 (参见样 例 1) , 如果给定单词仅是文章中某一单词的一部分则不算匹配 (参见样例 2) 。 【输入】 输入文件名为 stat.in,2 行。第 1 行为一个字符串,其中只含字母,表示给定 单词;第 2 行为一个字符串,其中只可能包含字母和空格,表示给定的文章。 【输出】 输出文件名为 stat.out。只有一行,如果在文章中找到给定单词则输出两个整 数, 两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出 现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从 0 开始);如果单词在文章中没有出现,则直接输出一个整数 -1。 【输入输出样例 1】 stat.in stat.out To

to be or not to be is a question 2 0 【输入输出样例 1 说明】 输出结果表示给定的单词 To 在文章中出现两次,第一次出现的位置为 0。 【输入输出样例 2】 stat.in stat.out to Did the Ottoman Empire lose its power at that time -1 【输入输出样例 2 说明】 表示给定的单词 to 在文章中没有出现,输出整数 -1。 【数据范围】 1 ≤单词长度 ≤ 10。 1 ≤文章长度 ≤ 1,000,000。 【算法】 每遇到一个单词就和原来的进行比对,比对成功后再判断之后是否是空 格。 【代码】 #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> using namespace std; int main(void) { char a[1010100],ch[1010]; gets(ch); gets(a); for (int i=0;i<strlen(a);i++) if(a[i]>='a'&&a[i]<='z') a[i]=a[i]-'a'+'A'; for (int i=0;i<strlen(ch);i++) if(ch[i]>='a'&&ch[i]<='z') ch[i]=ch[i]-'a'+'A'; int j=0,ans=0,pl=1111; for(int i=0;i<strlen(a);i++) { if(a[i]==ch[j]) j++; else j=0; if(j==strlen(ch)&&a[i+1]==' ') { ans++; if(pl==1111)pl=i-strlen(ch)+1; } }

if(ans!=0) cout<<ans<<" "<<pl; else cout<<"-1"; return 0; } 【年份】2011 六、【题目】1.质因数分解 (prime.cpp/c/pas) 【问题描述】 已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。 【输入】 输入文件名为 prime.in。 输入只有一行,包含一个正整数 n。 【输出】 输出文件名为 prime.out。 输出只有一行,包含一个正整数 p,即较大的那个质数。 【输入输出样例】 prime.in prime.out 21 7 【数据范围】 对于 60%的数据,6 ≤ n ≤ 1000。 对于 100%的数据,6 ≤ n ≤ 2*109。 【算法】 题目说这个数是两个质数的乘积, 所以它只有两个因数, 我们只要从· 1 搜到 sqrt(n),找出小的那个因数,再用原数除以它就可以了。 【代码】#include <stdio.h> #include <math.h> int main(){ int n; scanf("%d", &n); for (int i=2;i<=sqrt(n);i++){ if (!(n%i)) { n /= i; if (n>i){ printf("%d\n",n); return 0; } else{ printf("%d\n",i); return 0; } } } } 【年份】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

2 1 0 1 0 1 1 1

3 2 3 4 1 5 2

【输入输出样例说明】 第一层: 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 被多加了一次,应在外面去掉。为了形成一个环,每走一步都要模一 下房间数。 【代码】#include<cstdio> #include<iostream> #include<cstdlib>

using namespace std; struct node { int num; int lt; }; node room[1010][1010]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=0;j<m;j++) cin>>room[i][j].lt>>room[i][j].num; int k,ans=0; cin>>k; for(int i=1;i<=n;i++) { ans+=room[i][k].num; int x=0,y=room[i][k].num; for(;x!=y;++k) { k%=m; if(room[i][k].lt==1)x++; } k--; k%=m; } cout<<ans; return 0; }【年份】2012 八、【题目】 小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。 通过调 查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从 1 到 n 标号。为了在门 口展出更多种花,规定第 i 种花不能超过 ai 盆,摆花时同一种花放在一起, 且不同种类的花需按标号的从小到大的顺序依次摆列。 试编程计算,一共有多少种不同的摆花方案。 【输入】 输入文件 flower.in,共 2 行。 第一行包含两个正整数 n 和 m,中间用一个空格隔开。 第二行有 n 个整数, 每两个整数之间用一个空格隔开, 依次表示 a1、 a2、 ?an。

【输出】 输出文件名为 flower.out。 输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请 输出 方案数对 1000007 取模的结果。 【输入输出样例 1】 flower.in 2 4 3 2 【输入输出样例说明】 flower.out 2 有 2 种摆花的方案,分别是(1,1,1,2), (1,1,2,2)。括号里的 1 和 2 表示两种花, 比如第一个方案是前三个位置摆第一种花,第四个位置摆第二种花。 【数据范围】 对于 20%数据,有 0<n≤8,0<m≤8,0≤ai≤8; 对于 50%数据,有 0<n≤20,0<m≤20,0≤ai≤20; 对于 100%数据,有 0<n≤100,0<m≤100,0≤ ai≤100。 【算法】用 dp 解决。有一个规律:当种数固定时,摆 m 盆花的方案数是从 1 盆 到 n-1 盆的方案数总和,种数为 n 时,按照上一个步骤从一盆做到 m 盆,用得到 的新数据加到旧数据上,但一定要从上往下做,否则旧数据会被改变。第一个循 环控制种数, 第二个从上往下控制盆数,第三个循环为了是为了加上它之前的所 有数据。最后记得要把初始值 dp[0]设为 1,否则没有数据出得来。 【代码】#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> using namespace std; int a[1050],dp[1050],n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=min(a[i],j);k++) dp[j]=(dp[j]+dp[j-k])%1000007; printf("%d",dp[m]%1000007);

} 【年份】2012 九、【题目】 记数问题(NOIP 普及组 2013 第一题) (count.cpp/c/pas) 描述 试计算在区间 1 到 n 的所有整数中,数字 x(0 ≤ x ≤ 9)共出现了多少次?例 如,在 1 到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,数字 1 出现 了 4 次。 【输入】 输入文件名为 count.in。 输入共 1 行,包含 2 个整数 n、x,之间用一个空格隔开 【输出】 输出文件名为 count.out。 输出共 1 行,包含一个整数,表示 x 出现的次数。 【输入输出样例】 count.in count.out 11 1 4 限制 每个测试点 1s。 【数据说明】 对于 100%的数据,1≤ n ≤ 1,000,000,0 ≤ x ≤ 9。 【算法】这一题数据不大,一个一个找就可以了。关键之处就是用 sprintf 转化 成字符数组一一判断。 【代码】 #include <stdio.h> int main(){ int n,num,i,j,ans = 0; scanf("%d %d",&n,&num); char s[1000010]; for(i = 1;i<=n;i++){ sprintf(s+1, "%d",i); for(j = 1;s[j];j++) if(s[j] == num+48) ans++; } printf("%d\n",ans); return 0; } 【年份】2013 十、【题目】 小朋友的数字 有 n 个小朋友排成一列。 每个小朋友手上都有一个数字,这个数字可正可负。规 定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最 少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一 个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中 (不包括他本人),小朋友分数加上其特征值的最大值。 请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取 模后输出。 格式 【输入】 输入文件为 number.in。 第一行包含两个正整数 n、p,之间用一个空格隔开。第二行包含 n 个数, 每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。 【输出】 输出文件名为 number.out。 输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。 【输入输出样例 1】 number.in number.out 5 997 21 1 2 3 4 5 【输入输出样例说明】 小朋友的特征值分别为 1、3、6、10、15,分数分别为 1、2、5、11、21, 最大值 21,对 997 的模是 21。 【输入输出样例 2】 number.in number.out 5 7 -1 -1 -1 -1 -1 -1 【输入输出样例说明】 小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、 -2,最大值 -1 对 7 的模为-1,输出-1。 【数据范围】 对于 50%的数据,1 ≤ n ≤ 1,000,1 ≤ p ≤ 1,000 所有数字的绝对值 不超过 1000; 对于 100%的数据,1 ≤ n ≤ 1,000,000, 1≤ p ≤ 109, 其他数字的 绝对值均不超过 109。 【算法】求特征值就是最大字段和,先预处理一下,复杂度更低。剩下就直接循 环求出答案。 【代码】#include <bits/stdc++.h> #define f(a) for(int i=1;i<=a;i++) using namespace std; int main() { long long n,p,score[10101],a[10101],b[10101]={0},c[10101];//c 是特 征值 for(int i=1;i<=10100;i++) score[i]=c[i]=-101010;

cin>>n>>p; f(n) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) b[i]+=a[j]; for(int i=1;i<=n;i++) for(int l=1;l<=i;l++) for(int r=l;r<=i;r++) c[i]=max(c[i],b[r]-b[l-1]); score[1]=c[1]; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) score[i]=max(score[i],score[j]+c[j]); sort(score+1,score+n+1); int ans=score[n]; if(ans<0) ans=((ans*-1)%p)*-1; cout<<ans; return 0; }【年份】2013 十一、【题目】 表达式求值(noip2013 普及组第二题) (expr.cpp/c/pas) 描述 给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。 【输入】 输入文件为 expr.in。 输入仅有一行,为需要你计算的表达式,表达式中只包含数字、加法运算符 “+”和乘 ,且没有括号,所有参与运算的数字均为 0 到 231-1 之间的整 数。输入数据保 法运算符“*” 证这一行只有 0~ 9、+、*这 12 种字符。 【输出】 输出文件名为 expr.out。 输出只有一行,包含一个整数,表示这个表达式的值。注意:当答案长度多 于 4 位时, 请只输出最后 4 位,前导 0 不输出。 【输入输出样例 1】 expr.in expr.out 1+1*3+4 8 【输入输出样例 2】 expr.in expr.out

1+1234567890*1 7891 【输入输出样例 3】 expr.in expr.out 1+1000000003*1 4 【输入输出样例说明】 样例 1 计算的结果为 8,直接输出 8。 样例 2 计算的结果为 1234567891,输出后 4 位,即 7891。 样例 3 计算的结果为 1000000004,输出后 4 位,即 4。 【数据范围】 对于 30%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100; 对于 80%的数据,0≤表达式中加法运算符和乘法运算符的总数≤1000; 对于 100%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100000。 【算法】关键在于输入,hzwer 教的这种输入可以把数字和运算符分开。然后先 找乘,再找加。 【代码】 #include<cstdio> #include<iostream> using namespace std; long long a[1000001]; char c[1000001]; int main() { int i=2; cin>>a[1]; int ans=0; while(scanf("%c",&c[i++])!=EOF) scanf("%d",&a[i++]); i-=2; for(int j=i;j>0;j--) if(c[j]=='*'){a[j-1]*=a[j+1];a[j-1]%=10000;} for(int j=1;j<=i;j++) if(c[j]=='+'){ans+=a[j+1];ans%=10000;} cout<<(ans+a[1])%10000; return 0; } 【年份】2013 十二、【题目】 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。 珠心算 训练, 既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得 到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。 他随机生成 一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数, 恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。 格式 输入格式 输入共两行,第一行包含一个整数 n,表示测试题中给出的正整数个数。 第二行有 n 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出 的正整数。 输出格式 输出共一行,包含一个整数,表示测验题答案。 样例 1 样例输入 1 4 1 2 3 4 样例输出 1 2 对于 100%的数据,3 ≤ n ≤ 100,测验题给出的正整数大小不超过 10,000。 【算法】枚举所有加法后得数,稍微更改桶排序,在排序同时去掉多余的数。 然后和原数比对。因为得数排过序,所以当得数大于原数时就不用判断了。 正常情况用栈做。 【代码】#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> using namespace std; int main() { int n,num[1010]; cin>>n; for(int i=1;i<=n;i++) cin>>num[i]; int pl[10101],x=0; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) pl[++x]=num[i]+num[j]; int ans[10101],y=0; bool tong[10101]; memset(tong,0,sizeof(tong)); for(int i=1;i<=x;i++) tong[pl[i]]=1;

for(int i=1;i<=10001;i++) if(tong[i]==1) ans[++y]=i; int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=y;j++) { if(num[i]==ans[j]) { sum++; break; } if(num[i]<ans[j]) break; } cout<<sum; return 0; } 【年份】2014 十三、【题目】 在社交媒体上, 经常会看到针对某一个观点同意与否的民意调查以及结果。 例如, 对某 一观点表示支持的有 1498 人,反对的有 902 人,那么赞同与反对的比例 可以简单的记为 1498:902。 不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。因为这 个比例的数值太大,难以一眼看出它们的关系。对于上面这个例子,如果把比例 记为 5:3,虽然与 真实结果有一定的误差,但依然能够较为准确地反映调查结 果,同时也显得比较直观。 现给出支持人数 A,反对人数 B,以及一个上限 L,请你将 A 比 B 化简为 A’ 比 B’,要求在 A’和 B’均不大于 L 且 A’和 B’互质(两个整数的最大公 约数是 1)的前提下,A’/B’ ≥ A/B 且 A’/B’ - A/B 的值尽可能小。 格式 输入格式 输入共一行,包含三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表 示支持人数、反对人数以及上限。 输出格式 输出共一行,包含两个整数 A’,B’,中间用一个空格隔开,表示化简后的比 例。 样例输入 1 1498 902 10 样例输出 1

5 3 对于 100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤ L。 【算法】在 1~L 的范围内找出和原比例精度差距最小的一组数字。 【代码】 #include<iostream> using namespace std; double a,b,aa,bb,l; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main() { cin>>a>>b>>l; double ans=a/b; double ans2=0.0000; double ans3=1000000.00; for(double i=1.0;i<=l;i++) { for(double j=1.0;j<=l;j++) { ans2=(double)i/j; double ans4=ans2-ans; if(ans4>=0&&gcd((int)i,(int)j)==1&&ans4<=ans3) {ans3=ans4;aa=i;bb=j;} } } cout<<aa<<" "<<bb<<endl; return 0; } 【年份】2014 十四、【题目】 一个 n 行 n 列的螺旋矩阵可由如下方法生成: 从矩阵的左上角(第 1 行第 1 列)出发,初始时向右移动;如果前方是未曾经 过的格子, 则继续前进,否则右转;重复上述操作直至经过矩阵中所有格子。 根据经过顺序,在格子中 依次填入 1, 2, 3, ... , n2,便构成了一个螺旋矩 阵。 下图是一个 n = 4 时的螺旋矩阵。 1121110 213169 314158 4567 现给出矩阵大小 n 以及 i 和 j,请你求出该矩阵中第 i 行第 j 列的数是多 少。 格式

输入格式 输入共一行,包含三个整数 n,i,j,每两个整数之间用一个空格隔开,分别表 示矩阵大小、待求的数所在的行号和列号。 输出格式 输出共一行,包含一个整数,表示相应矩阵中第 i 行第 j 列的数。 样例 1 样例输入 1 4 2 3 样例输出 1 14 对于 50%的数据,1 ≤ n ≤ 100; 对于 100%的数据,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n。 【算法】外壳上的数分布是有规律的,可以由左上角的数推出所有的数。在外壳 上找不到就把外壳剥掉,在新的矩阵的外壳找,但注意更新左上角的数,可以用 递归做。 【代码】 #include<iostream> #include<cstdio> using namespace std; int num(int beg,int n,int i,int j) { if(i==1)return beg+j-1; if(j==n)return beg+n+i-2; if(i==n)return beg+n+n-2+n-j; if(j==1)return beg+n+n+n-3+n-i; return num(beg+4*(n-1),n-2,i-1,j-1); } int main() { int n,i,j; cin>>n>>i>>j; cout<<num(1,n,i,j)<<endl; return 0; } 【年份】2014 十五、【题目】

扫雷游戏 (mine.cpp/c/pas) 【Online judge】
【问题描述】

扫雷游戏是一款十分经典的单机小游戏。在 n 行 m 列的雷区中有一些格子 含有地雷(称之为地雷格) ,其他格子不含地雷(称之为非地雷格) 。玩家翻开一 个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。 现在给出 n 行 m 列的雷区中的地雷分布,要求计算出每个非地雷格周围的 地雷格数。 注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下 八个方向上与之直接相邻的格子。 【输入格式】 输入文件名为 mine.in。 输入文件第一行是用一个空格隔开的两个整数 n 和 m, 分别表示雷区的行数 和列数。 接下来 n 行,每行 m 个字符,描述了雷区中的地雷分布情况。字符’*’表 示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分 隔符。 【输出格式】 输出文件名为 mine.out。 输出文件包含 n 行,每行 m 个字符,描述整个雷区。用’*’表示地雷格, 用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。 【输入输出样例 1】 mine.in mine.out 3 3 *10 *?? 221 ??? 1*1 ?*? 见选手目录下的 mine/mine1.in 和 mine/mine1.ans。 【输入输出样例 2】 mine.in mine.out 2 3 2*1 ?*? *21 *?? 见选手目录下的 mine/mine2.in 和 mine/mine2.ans。 【输入输出样例 3】 见选手目录下的 mine/mine3.in 和 mine/mine3.ans。 【数据说明】 对于 100%的数据,1≤n≤100,1≤m≤100。 【算法】 只要搜索一遍就可以了。 复杂度只有 O (8nm) 。 注意数组要开至少 103*103 我前面开 102 结果 RE 了?? 【代码】 #include<cstdio>

#include<iostream> #include<cstring> using namespace std; int u[9]={-10,0,1,0,-1,1,1,-1,-1},w[9]={-10,1,0,-1,0,1,-1,1,-1}; int main(void) { int a,b; cin>>a>>b; char maps[105][105]; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) cin>>maps[i][j]; int map[105][105]; memset(map,0,sizeof(map)); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) if(maps[i][j]=='*')map[i][j]=-1; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) if(map[i][j]!=-1) for(int k=1;k<=8;k++) { if(map[i+u[k]][j+w[k]]==-1) map[i][j]++; } for(int i=1;i<=a;i++) { for(int j=1;j<=b;j++) { if(map[i][j]!=-1)cout<<map[i][j]; else cout<<"*"; } cout<<endl; } return 0; }【年份】2015 十六、【题目】 经过 11 年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离 不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0 时,则能够拦 截与它位置恰好相同的导弹。 但该导弹拦截系统也存在这样的缺陷:每套系统每 天只能设定一次工作半径。 而当天的使用代价, 就是所有系统工作半径的平方和。 某天,雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段,所以只有两套 系统投入工作。 如果现在的要求是拦截所有的导弹,请计算这一天的最小使用代 价。

格式 输入格式 第一行包含 4 个整数 x1、y1、x2、y2,每两个整数之间用一个空格隔开,表示 这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。 第二行包含 1 个整数 N(1 ≤ N ≤ 100000)。表示有 N 颗导弹。 接下来 N 行,每行两个整数 x、y,中间用一个空格隔开,表示一颗导弹的坐标 (x, y)。不同导弹的坐标可能相同。 所有坐标分量的绝对值都不超过 1000。 输出格式 只有一行,包含一个整数,即当天的最小使用代价。 样例 1 样例输入 1 0 0 10 0 2 -3 3 10 0 样例输出 1 18 样例 2 样例输入 2 0 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 1 样例输出 2 30 限制 每个测试点 1s。 提示 两个点(x1, y1)、(x2, y2)之间距离的平方是(x1? x2)2+(y1?y2)2。 两套系统工作半径 r1、r2 的平方和,是指 r1、r2 分别取平方后再求和,即 r12 +r22 。 样例 1 说明: 样例 1 中要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径 的平方分 别为 18 和 0。 样例 2 说明: 样例中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹,在满足

最小使用代价的前提下,两套系统工作半径的平方分别为 20 和 10。

【算法】这是一道贪心。把所有导弹和第一套的距离从大到小排序,然后平均分 配一些第二套,使两套系统的工作半径尽量接近。因为后面要求平方和,前面就 不要开平方了。 【代码】 #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int x1,x2,y1,y2,n,rb=0; int ans=1<<20; struct data { int x,y,s1,s2; }a[100005]; bool cmp(data a,data b){return a.s1<b.s1;} int main() { cin>>x1>>y1>>x2>>y2>>n; for(int i=1;i<=n;i++) { cin>>a[i].x>>a[i].y; a[i].s1=(a[i].x-x1)*(a[i].x-x1)+(a[i].y-y1)*(a[i].y-y1); a[i].s2=(a[i].x-x2)*(a[i].x-x2)+(a[i].y-y2)*(a[i].y-y2); } sort(a+1,a+n+1,cmp); for(int i=n;i;i--) {

rb=max(a[i+1].s2,rb); ans=min(ans,a[i].s1+rb); } printf("%d",ans); return 0; } 【年份】2010 十七、【题目】 有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习 任何一种文化超过一次, 即如果他学习了某种文化,则他就不能到达其他有这种 文化的国家。 不同的国家可能有相同的文化。不同文化的国家对其他文化的看法 不同,有些文化会排斥外来文化,即如果他学习了某种文化,则他不能到达排斥 这种文化的其他国家。 现给定各个国家间的地理关系,各个国家的文化,每种 文化对其他文化的看法, 以及这位使者游历的起点和终点(在起点和终点也会学 习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。 格式 输入格式 第一行为五个整数 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,两个国家之间可能 有多条道路。 输出格式 输出只有一行, 一个整数, 表示使者从起点国家到达终点国家最少需要走的距离 数,如果无解则输出-1。 样例 1 样例输入 1 2 2 1 1 2 1 2 0 1 1 0 1 2 10 样例输出 1

-1 样例 2 样例输入 2 2 2 1 1 2 1 2 0 1 0 0 1 2 10 样例输出 2 10 【算法】就用了 floyed 最短路算法,如果一个国家排斥另一个国家,就把道路 设为不可通行。(表示数据太弱??O(n^3)也不会炸??) 【代码】 #include<bits/stdc++.h> using namespace std; const int INF=999999; int n,k,m,s,t,dist[101][101],c[101],a[101][101]; int main() { scanf("%d%d%d%d%d",&n,&k,&m,&s,&t); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) dist[i][j]=INF; 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]); for (int i=1;i<=m;i++) { int a1,b1,c1; scanf("%d%d%d",&a1,&b1,&c1); dist[a1][b1]=dist[b1][a1]=min(dist[a1][b1],c1); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[c[i]][c[j]]) dist[i][j]=INF; for(int k=1;k<=n;k++) //floyd for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

if(dist[s][t]==INF) printf("%d",-1); else printf("%d",dist[t][s]); } 【年份】2014 十八、【题目】 【算法】用什么算法思想解决,数据存储结构 【代码】(加上注释) 【年份】 十九、【题目】 【算法】用什么算法思想解决,数据存储结构 【代码】(加上注释) 【年份】 二十、【题目】 【算法】用什么算法思想解决,数据存储结构 【代码】(加上注释) 【年份】 二十一、【题目】 【算法】用什么算法思想解决,数据存储结构 【代码】(加上注释) 【年份】



更多相关文章:
noip复赛总结归纳(c++)
noip 复赛总结归纳(2010 至 2015 年 c++普及组复赛试题) 一、【题目】1.数字统计 (two.pas/c/cpp) 【问题描述】 请统计某个给定范围[L, R]的所有整数中,...
NOIP复习资料(C++版)
NOIP复习资料(C++版)_学科竞赛_高中教育_教育专区。noip 前言NOIP 复习资料(C++...这是复赛复习资料——需要有人能用心总结整理初赛的知识,就像这份资料一样。...
NOIP算法整理
即便我本人对 C++也是赞赏有 加,不过 PASCAL 作为...NOIP 算法总结 22 山东省广饶一中 杨庆礼 Einstein...NOIP2015复赛提高组成绩... 暂无评价 22页 1下载券...
noip复习资料(提高组c++版)
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8...这是复赛复习资料——需要有人能用心总结整理初赛的知识,就像这份资料一样。...
历年noip普及组(c++)完善程序题总结归纳
历年noip普及组(c++)完善程序题总结归纳_其它课程_初中教育_教育专区。完善程序题总结归纳 By:七(6) yx 一、 【题目】 (哥德巴赫猜想)哥德巴赫猜想是指,任一...
NOIP算法分类总结(C语言)
NOIP算法分类总结(C语言)_工学_高等教育_教育专区。...{ lc++; Record[lc]=i; P/=i; If(p==1){...NOIP实用算法 33页 免费 NOIP复赛冲刺资料集锦10 45...
NOIP复习资料
我觉得应该把常用的代码总结一下,所 以就在网络...输出字符串 str:cout<<str; 4 NOIP 复习资料(C++...NOIP 初赛相当于其他科目的省级联赛,NOIP 复赛相当于...
noip复习提纲
NOIP 初赛复习提纲综述:初赛考的知识点就是计算机...组复赛题 A2、提高组初赛题 B1 和提高组 复赛题 ...(PASCAL/C/C++)- 2003 1.初等算法(计数、统计、...
2008noip普及组复赛--排座位--代码C++
2008noip普及组复赛--排座位--代码C++_计算机软件及应用_IT/计算机_专业资料。竞赛题解 2.排座椅 排座椅(seat.pas/c/cpp) ) 【问题描述】 上课的时候总有...
NOIP2012山东赛区复赛通知(新)
NOIP2012山东赛区复赛通知(新)_制度/规范_工作范文_...(比赛结束后颁 奖总结大会颁奖) ,其中提高组和普及...C++:devcpp-4.9.9.2(C 盘装有 G++4.4.5 C++...
更多相关标签:
noip2016提高组复赛    noip2016普及组复赛    noip2015提高组复赛    2016noip复赛成绩查询    noip2016复赛成绩    noip2016复赛    noip2015普及组复赛    noip2016复赛名单    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图