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

此文档收集于网络，仅供学习与交流，如有侵权请联系网站删除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。【算法】把每一位分出来，一一判断【代码】#includeusing namespace std;int main() int r,l,ans=0; scanf(%d%d,&r,&l);for(int i=r;i0)/把每一位分离 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 423 71 87 32 70 93 80 76 163 【数据范围】1 n 10000，1 m 100 且m n；1 wi 100。【算法】把人数分为两部分，一人对一个水龙头，作为第一部分，剩下是第二部分的，每一次从第一部分找一个时间最少人，把第二部分的一个人加进去。【代码】#includeint w10005;int main()int i,j,m,n;scanf(%d%d,&m,&n);for (i=1;i=m;i+)/输入1到m的数据到wiscanf(%d,&wi);for (i=n+1;i=m;i+)int k=1;/假设wk=w1是最小for (j=2;jwj)k=j;wk+=wi;int k=1;for (i=2;i=n;i+)if (wkwi)k=i;printf(%d,wk);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 65 28 16 29 2723 3 20 18 32 2633 1112 132 【输入输出样例说明】首先小涵拿走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 842 24 10 29 27 12 5831 8 16 26 80 625 3 36 11 533 20 17 1315 77 94 5019 177 【数据范围】对于 40%的数据有 N 10。对于 70%的数据有 N 18。对于 100%的数据有 N 500。【算法】每个武将先找第一大，删掉，再找第一大（就是找第二大），看看是否比现有答案大。人是必胜的，直接输1和答案。【代码】#include#include#include#include#includeusing namespace std;int n,a10001000,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,&aij);aji=aij;for(int i=1;i=n;i+)for(int j=1;jaimaxx)maxx=j;aimaxx=0;for(int j=1;j=n;j+)ans=max(ans,aij);maxx=1;printf(1n%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#include#include#include#includeusing namespace std;int main()char a20120;gets(a); int b,len=strlen(a);if(a0=0)cout0;return 0;if(a0=-)cout=0;i-)if(f=1|ai!=0)&ai!=-)coutai,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#include#include#includeusing namespace std;int main(void)char a1010100,ch1010;gets(ch);gets(a);for (int i=0;i=a&ai=z) ai=ai-a+A;for (int i=0;i=a&chi=z) chi=chi-a+A;int j=0,ans=0,pl=1111;for(int i=0;istrlen(a);i+)if(ai=chj)j+;else j=0;if(j=strlen(ch)&ai+1= )ans+;if(pl=1111)pl=i-strlen(ch)+1;if(ans!=0)coutans 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 #include int main() int n; scanf(%d, &n); for (int i=2;ii) printf(%dn,n); return 0; else printf(%dn,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 3 1 2 0 3 1 4 0 1 1 5 1 2 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%数据，有 0N1000，0x10000；对于 100%数据，有 0N10000，0M100，0x1,000,000。【算法】利用递推，模拟每一层的情况，我用结构体储存每一间的情况。第二重循环中，k被多加了一次，应在外面去掉。为了形成一个环，每走一步都要模一下房间数。【代码】#include#include#includeusing namespace std;struct nodeint num;int lt;node room10101010;int main()int n,m;scanf(%d%d,&n,&m);for(int i=1;i=n;i+)for(int j=0;jroomij.ltroomij.num;int k,ans=0;cink;for(int i=1;i=n;i+)ans+=roomik.num;int x=0,y=roomik.num;for(;x!=y;+k)k%=m;if(roomik.lt=1)x+;k-;k%=m;coutans;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%数据，有 0n8，0m8，0ai8；对于 50%数据，有 0n20，0m20，0ai20；对于 100%数据，有 0n100，0m100，0 ai100。【算法】用dp解决。有一个规律：当种数固定时，摆m盆花的方案数是从1盆到n-1盆的方案数总和，种数为n时，按照上一个步骤从一盆做到m盆，用得到的新数据加到旧数据上，但一定要从上往下做，否则旧数据会被改变。第一个循环控制种数，第二个从上往下控制盆数，第三个循环为了是为了加上它之前的所有数据。最后记得要把初始值dp0设为1，否则没有数据出得来。【代码】#include#include#include#includeusing namespace std;int a1050,dp1050,n,m;int main() scanf(%d%d,&n,&m); for(int i=1;i=n;i+) scanf(%d,&ai); memset(dp,0,sizeof(dp); dp0=1; for(int i=1;i=0;j-) for(int k=1;k=min(ai,j);k+) dpj=(dpj+dpj-k)%1000007; printf(%d,dpm%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.out11 1 4限制每个测试点1s。【数据说明】 对于 100%的数据，1 n 1,000,000，0 x 9。【算法】这一题数据不大，一个一个找就可以了。关键之处就是用sprintf转化成字符数组一一判断。【代码】#include int main() int n,num,i,j,ans = 0; scanf(%d %d,&n,&num); char s1000010; for(i = 1;i=n;i+) sprintf(s+1, %d,i); for(j = 1;sj;j+) if(sj = num+48) ans+; printf(%dn,ans); return 0;【年份】2013十、【题目】小朋友的数字有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后输出。格式【输入】 输入文件为 number.in。 第一行包含两个正整数 n、p，之间用一个空格隔开。第二行包含 n 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。【输出】 输出文件名为 number.out。 输出只有一行，包含一个整数，表示最大分数对 p 取模的结果。【输入输出样例 1】number.in number.out5 997 211 2 3 4 5【输入输出样例说明】 小朋友的特征值分别为 1、3、6、10、15，分数分别为 1、2、5、11、21，最大值 21，对 997 的模是 21。【输入输出样例 2】number.in number.out5 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 #define f(a) for(int i=1;i=a;i+)using namespace std;int main()long long n,p,score10101,a10101,b10101=0,c10101;/c是特征值 for(int i=1;inp;f(n)cinai;for(int i=1;i=n;i+)for(int j=1;j=i;j+)bi+=aj;for(int i=1;i=n;i+)for(int l=1;l=i;l+)for(int r=l;r=i;r+)ci=max(ci,br-bl-1);score1=c1;for(int i=2;i=n;i+)for(int j=1;ji;j+)scorei=max(scorei,scorej+cj);sort(score+1,score+n+1);int ans=scoren;if(ans0)ans=(ans*-1)%p)*-1;coutans;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.out1+1*3+4 8【输入输出样例 2】expr.in expr.out1+1234567890*1 7891【输入输出样例 3】expr.in expr.out1+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#includeusing namespace std;long long a1000001;char c1000001;int main()int i=2;cina1;int ans=0;while(scanf(%c,&ci+)!=EOF)scanf(%d,&ai+);i-=2;for(int j=i;j0;j-) if(cj=*)aj-1*=aj+1;aj-1%=10000;for(int j=1;j=i;j+) if(cj=+)ans+=aj+1;ans%=10000;cout(ans+a1)%10000;return 0;【年份】2013十二、【题目】珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练， 既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。格式输入格式输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。输出格式输出共一行，包含一个整数，表示测验题答案。样例1样例输入141 2 3 4样例输出12对于 100%的数据，3 n 100，测验题给出的正整数大小不超过 10,000。 【算法】枚举所有加法后得数，稍微更改桶排序，在排序同时去掉多余的数。然后和原数比对。因为得数排过序，所以当得数大于原数时就不用判断了。正常情况用栈做。【代码】#include#include #include#includeusing namespace std;int main()int n,num1010;cinn;for(int i=1;inumi;int pl10101,x=0;for(int i=2;i=n;i+)for(int j=1;ji;j+)pl+x=numi+numj;int ans10101,y=0;bool tong10101;memset(tong,0,sizeof(tong);for(int i=1;i=x;i+)tongpli=1;for(int i=1;i=10001;i+)if(tongi=1)ans+y=i;int sum=0;for(int i=1;i=n;i+)for(int j=1;j=y;j+)if(numi=ansj)sum+;break;if(numiansj)break;coutsum;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，中间用一个空格隔开，表示化简后的比例。样例输入11498 902 10样例输出15 3对于 100%的数据，1 A 1,000,000，1 B 1,000,000，1 L 100，A/B L。【算法】在1L的范围内找出和原比例精度差距最小的一组数字。【代码】#includeusing namespace std;double a,b,aa,bb,l;int gcd(int a,int b)return b=0?a:gcd(b,a%b);int main() cinabl; 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=0&gcd(int)i,(int)j)=1&ans4=ans3)ans3=ans4;aa=i;bb=j; coutaa bbendl; 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样例输入14 2 3样例输出114对于 50%的数据，1 n 100;对于 100%的数据，1 n 30,000，1 i n，1 j n。 【算法】外壳上的数分布是有规律的，可以由左上角的数推出所有的数。在外壳上找不到就把外壳剥掉，在新的矩阵的外壳找，但注意更新左上角的数，可以用递归做。【代码】#include#includeusing 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; cinnij; coutnum(1,n,i,j)endl; return 0;【年份】2014十五、【题目】扫雷游戏（mine.cpp/c/pas）【Online judge】【问题描述】扫雷游戏