NOIP2010普及组第四题《三国游戏》解题报告
NOIP2010普及组第四题
三国游戏解题报告
(sanguo.pas/c/cpp)
【问题描述】
小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。
在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有N位武将（N 为偶数且不小于4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。
已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略，例如，游戏中一共有6个武将，他们相互之间的默契值如下表所示
（武将默契值关系表）
双方选将过程如下所示
小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？
假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。
【输入】
输入文件名为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.in sanguo.out
6
5 28 1
6 29 2
7 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。结果为小涵胜，并且这个组合是小涵用尽所有方法能取到的最好组合。
【数据范围】
对于40%的数据有N≤10。
对于70%的数据有N≤18。
对于100%的数据有N≤500。
【解题思路】
解答本题，必须看清题意，知道以下几点：
一、只需要选两次，由于比胜负靠的是双方武将中默契值最大的一对，所以除了默契值最大的一对，其他的武将都是没用的。并因为小涵先选，并且题目要求输出默契值尽量大的。所以必须两次定胜负，只要一开始选择最优方案，之后也就可以不用考虑了。
二、再深入分析，就会发现，小涵是输不了的。这是因为小涵永远掌握主动权，计算机一直都只是应付小涵，且大家可以举例证明——小涵选一个将，计算机选走搭配默契值最大的武将，然后小涵选走默契值次大的武将，计算机把小涵选走的两个武将中剩下搭配方案里默契值最大的选走。到这里就已经定下了胜负。此时，如果计算机的最大默契值比小涵的小，那么毫无疑问小涵就赢了。而如果计算机的武将搭配默契值比小涵的大，那么小涵完全可以换方法选，从计算机的方案的角度选，得到更优方案。依此类推，必定能赢。所以无论如何，小涵总会赢，我们可以直接把那个“1”输出来。大家如果光看我的描述不能理解，可以自己举例子仿照样例画一张表，就能理解了。
三、逐步分析所有情况，会发现。在一个武将和其他所有武将的搭配方案中，默契值最大的是拿不到的。因为小涵不能一下选两个，计算机又要和小涵抢。得到默契值最大的搭配方案，那是不可能的，想都别想。但是，小涵也没有这么悲剧，这个游戏规则也有对小涵有利的一面。在一个武将和其他武将的搭配中，默契值次大的那对，小涵可以稳拿。因为计算机会死板地被默契值最大的那对引开。这样搭配后默契值次大的武将，小涵就可以轻而易举地获得。
四、让我们看一下上方题目里的武将默契值关系表。我们先读入一个和它一样的默契值关系方阵。然后枚举行（也就是先枚举武将i，然后考虑他和其他武将搭配的默契值情况），让计算机取掉最大值所在的列（计算机必定会取走搭配默契值最大的武将），然后让小涵取次大值所在的列（选择默契值次大的搭配方案）。但如果小涵先取列呢？那就是先枚举列，让计算机取走最大值所在的行，小涵再取次大值所在的行。实际上，没有这个必要，默契值关系方阵是沿对角线对称的，每一列都有一行和它对应，而且数据相同。所以就不必考虑列的情况，直接枚举行就可以了。
想到这里，思路就出来了。搭配武将就可以简化成取次大的默契值。因为题目要求输出默契值
最大的组合，并由于小涵只能选择默契值次大的组合。这个题目就简化成了求次大值中的最大值，也就是最大的次大值。
【标准程序】
var a:array[1..500,1..500]of longint;
i,j,n,max1,max2,maxall:longint;
begin
assign(input,'sanguo.in');
assign(output,'sanguo.out');
reset(input);
rewrite(output);
readln(n); ｛以下这段是读入默契值｝
for i:=1 to n-1 do ｛读入武将i和其他武将搭配的默契值｝
for j:=i+1 to n do ｛只要读入序号在i之后的搭配默契值即可，否则会有重复｝
begin
read(a[i,j]);
a[j,i]:=a[i,j]; ｛读的是一个三角形，在读的时候转换成n*n的方阵（方阵沿对角线对称）｝end;
maxall:=0; ｛maxall用来存放次大值中的最大值｝
for i:=1 to n do ｛枚举武将i和其他武将搭配的情况｝
begin
max1:=0;max2:=0; ｛max1是武将i和其他武将搭配情况中的最大值，而max2是次大值｝for j:=1 to n do ｛枚举武将i和武将j搭配的情况｝
if j<>i then ｛自己不能和自己搭配｝
begin
if a[i,j]>max1 then ｛默契值[i,j]比最大默契值大的情况｝
begin
max2:=max1; ｛最大值和次大值依次迭代掉｝
max1:=a[i,j]; ｛最大值变为次大值，然后取新的最大值｝
end;
if (a[i,j]>max2)and(a[i,j] max2:=a[i,j]; ｛迭代次大值即可，最大值不变｝ end; if max2>maxall then maxall:=max2; ｛枚举j结束后，次大值打擂台，选出最大的一个｝end; ｛枚举下一个武将i｝ writeln(1); ｛小涵必胜，所以输出“1”｝ writeln(maxall); ｛输出次大值中的最大值｝ close(input); close(output); end. 第十八届全国青少年信息学奥林匹克联赛初赛 （普及组C++语言试题） 竞赛时间：2012年10月13日14:30~16:30 选手注意： ●试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料 一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1．计算机如果缺少（），将无法正常启动。 A．内存B．鼠标C．U盘D．摄像头 2．（）是一种先进先出的线性表。 A．栈B．队列C．哈希表（散列表）D．二叉树 3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。 A．硅B．铜C．锗D．铝 4．十六进制数9A在（）进制下是232。 A．四B．八C．十D．十二 5．（）不属于操作系统。 A．Windows B．DOS C．Photoshop D．NOI Linux 6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。 A．ABC B．CBA C．ACB D．BAC 7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。 A．显示器B．CPU C．内存D．鼠标 8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。 A．0 B．5 C．10 D．15 9．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。 A．电子管B．晶体管C．集成电路D．超大规模集成电路 10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。 A．中国公司的经理与波兰公司的经理交互商业文件 棋盘解题报告（noip2017普及组第三题）上次写了Linux用vim进行C++编程的配置和操作入门后，今天再给棋盘写个解题报告试试。 题目描述 有一个m ×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1 个金币。另外，你可以花费2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。 现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入输出格式 输入格式： 数据的第一行包含两个正整数m，n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。 接下来的n 行，每行三个正整数x，y，c，分别表示坐标为（x，y）的格子有颜色c。 其中c=1 代表黄色，c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标为（1, 1），右下角的坐标为（m, m）。 棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（1，1）一定是有颜色的。 输出格式： 输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。输入输出样例 输入样例#1： 5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0 输出样例#1： 8 输入样例#2： 5 5 NOIP2011 普及组复赛 1 .数字反转(reverse.cpp/c/pas ) 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为 零，否则反转后得到的新数的最高位数字不应为零。(参见样例2) 【输入】 输入文件名为reverse. in 。 输入共一行，一个整数No 【输出】 输出文件名为reverse.out 。 输出共1行，一个整数，表示反转后的新数。 【输入输出样例1】 -1,000,000,000 < N< 1,000,000,000 。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及但测试数据没出)。 -0 , 【法一】字符串处理 Var i,l,k:i nteger; s:stri ng; p:boolea n; begin assig n(i nput, 'reverse.i n'); reset(i nput); assig n(o utput, 'reverse.out'); rewrite(output); readl n( s); l:=le ngth(s); k:=1; if s[1]=' -' the n begin write('-'); k:=2; en d; p:=true;; for i:=l dow nto k do begin if(p)a nd((s[i]='0')) the n continue else begin write(s[i]); p:=false;; en d; en d; close(i nput); close(output); en d. 【法二】数字处理 Var f:i nteger; n,an s:lo ngint; begin assig n(i nput, 'reverse.i n'); reset(i nput); assig n(o utput, 'reverse.out'); rewrite(output); readl n(n); if n<0 the n begin f:=-1; n :=-n; 第十六届全国青少年信息学奥林匹克联赛初赛试题 （ 提高组 C++ 语言 两小时完成 ） ? ? 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ?? 、单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确选项。 ） 1．与十六进制数 A1.2 等值的十进制数是（ ) A ． 101.2 B ． 111.4 C ． 161.125 D ． 177.25 &主存储器的存取速度比中央处理器 （CPU ）的工作速度慢的多，从而使得后者的效率受到影响。而 根据局部性原理，CPU 所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统 整体的执行 效率，在 CPU 中引入了（ ）。 A ．寄存器 B ．高速缓存 C ．闪存 D ．外存 9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当 存放在数组中的（ ）号位置。 A ．2k B ．2k+1 C ．k/2 下取整 D ．（k+1）/2 2．一个字节（ byte ）由（ ）个二进制组成。 A ．8 B ．16 上都有可能 3．以下逻辑表达式的值恒为真的是（ ）。 A . P V （n P A Q ）V （n P 心 Q ） B C . P V Q V （ P A n Q ）V （n P A Q ） D 4 ． Linux 下可执行文件的默认扩展名是 （ ） 。 A. exe B. com 都不是 C ． 32 D .以 Q V( n P A Q )V (P A n Q ) P V n Q V( P A n Q V (n P A n Q) C. dll D. 以上 5 ．如果在某个进制下等式 7*7=41 成立，那么在该进制下等式 12*12= （ A. 100 B. 144 C. 164 ）也成立。 D. 196 6 ．提出“存储程序”的计算机工作原理的是（ A. 克劳德 ?香农 B. 戈登?摩尔 ）。 C. 查尔斯 ?巴比奇 D. 冯?诺依曼 7 ．前缀表达式“ + 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 6 1. 话说去年苹果们被陶陶摘下来后都很生气，于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上，准备摘取。摘取的规则是，一个苹果只能摘一个陶陶，且只能在它所能摘到的高度以下（即是小于关系）的最高的陶陶，如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度，求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数，分别为苹果的数量n和陶陶的数量m（n,m<=2000）以下的n行，分别为各个苹果能够到的最大高度。再接下来的m行，分别为各个陶陶的高度。高度均不高于300。 当然了，摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。 【输出格式】输出仅有一个数，是剩下的陶陶的数量 【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前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】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264 1.珠心算测验 注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同 的)数之和。这样的题意加上100的规模，建议暴力3个for: #include 第十七届全国青少年信息学奥林匹克联赛初赛试题 （提高组 Pascal语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。） B 1．在二进制下，1100011 +（）= 1110000。 A．1011 B．1101 C．1010 D．1111 B 2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66 B．5A C．50 D．视具体的计算机而定 A 3．右图是一棵二叉树，它的先序遍历是（）。 A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF D 4．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） B 5．广度优先搜索时，需要用到的数据结构是（）。 A．链表B．队列C．栈D．散列表 A 6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。 A．程序运行时理论上所占的内存空间 B．程序运行时理论上所占的数组空间 C．程序运行时理论上所占的硬盘空间 D．程序源文件理论上所占的硬盘空间 C 7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。 A．O(n2)B．O(n log n)C．O(n) D．O(1) D 8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C） 第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组 竞赛用时：3小时） 第一题 Cantor 表（30分） 现代数学的著名证明之一是Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 我们以Z 字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，… 输入：整数N （1≤N ≤10000000） 输出：表中的第N 项 样例： INPUT OUTPUT N=7 1/4 第二题 回文数（30分） 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N 进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N （2<=N<=10，N=16）进制数M ，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible ！” 样例： INPUT OUTPUT N = 9 M= 87 STEP=6 第三题 旅行家的预算（40分） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C （以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P 和沿途油站数N （N 可以为零），油站i 离出发点的距离Di 、每升汽油价格Pi （i=1，2，…，N ）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution ”。 样例： INPUT … 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … 4/1 4/2 … 5/1 … … NOIP2015 普及组解题报告 From 贴吧id u007zzt 金币 国王将金币作为工资，发放给忠诚的骑士。 第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。 请计算前K天里，骑士一共获得了多少金币。 输入格式 输入包含一个正整数K，表示发放金币的天数。 输出格式 输出一个正整数，即骑士收到的金币数。 样例1 样例输入1 6 样例输出1 14 样例2 样例输入2 1000 样例输出2 29820 对于全部数据，1≤K≤10000。 这种题目，简直就属于水题狂做的那种。不多说，附C++代码。 #include "stdio.h" int k,ans=0; int main(){ freopen("coin.in","r",stdin); freopen("coin.out","w",stdout); scanf("%d",&k); int i=1; while(k){ if(k>=i){ ans+=i*i; k-=i; }else{ ans+=k*i; k=0; } i++; } printf("%d\n",ans); return 0; } 扫雷游戏 扫雷游戏是一款十分经典的单机小游戏。 在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。 玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。 注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。 输入格式 第一行用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。 接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符?'表示相应的格子是地雷格，字符(?)`表示相应的格子是非地雷格子。相邻字符之间无分隔符。 输出格式 输出文件包括n行，每行m个字符，描述了整个雷区。用?表示地雷格，用周围地雷格数表示非地雷格。相邻字符之间无分隔符。 样例1 样例输入1 3 3 *?? ??? ?*? 样例输出1 *10 221 1*1 样例2 样例输入2 2 3 ?*? *?? 样例输出2 2*1 *21 CCF全国信息学奥林匹克联赛（NOIP2015）复赛 普及组 （请选手务必仔细阅读本页内容） 一、题目概况 中文题目名称金币扫雷游戏求和推销员 coin mine sum salesman 英文题目与子目 录名 可执行文件名coin mine sum salesman 输入文件名coin.in mine.in sum.in salesman.in 输出文件名coin.out mine.out sum.out salesman.out 每个测试点时限1秒 测试点数目10 每个测试点分值10 附加样例文件有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类型传统 运行内存上限128M 二、提交源程序文件名 对于C++语言coin.cpp mine.cpp sum.cpp salesman.cpp 对于C语言coin.c mine.c sum.c salesman.c 对于Pascal语言coin.pas mine.pas sum.pas salesman.pas 四、注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm)II x2240processor，2.8GHz，内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 1.金币 (coin.cpp/c/pas) 【问题描述】 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K天里，骑士一共获得了多少金币。 【输入格式】 输入文件名为coin.in。 输入文件只有1行，包含一个正整数K，表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1行，包含一个正整数，即骑士收到的金币数。 【输入输出样例1】 coin.in coin.out 614 见选手目录下的coin/coin1.in和coin/coin1.ans。 【输入输出样例1说明】 骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。 【输入输出样例2】 coin.in coin.out 100029820 见选手目录下的coin/coin2.in和coin/coin2.ans。 【数据说明】 对于100%的数据，1≤K≤10,000。 【最新整理，下载后即可编辑】 历年noip普及组初赛试题汇编 芜湖县实验学校NOIP初赛复习资料 第十五届全国青少年信息学奥林匹克联赛初赛试题(2009) （普及组C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸 上一律无效●● 一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 1、关于图灵机下面的说法哪个是正确的： A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作，图灵机运行速度很慢。 C)图灵机是英国人图灵发明的，在二战中为破译德军的密码 发挥了重要作用。 D)图灵机只是一个理论上的计算模型。 2、关于计算机内存下面的说法哪个是正确的： A)随机存储器（RAM）的意思是当程序运行时，每次具体分 配给程序的内存位置是随机而不确定的。 B)1MB内存通常是指1024*1024字节大小的内存。 C)计算机内存严格说来包括主存（memory）、高速缓存（cache） 和寄存器（register）三个部分。 D)一般内存中的数据即使在断电的情况下也能保留2个小时 以上。 3、关于BIOS下面说法哪个是正确的： A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输 入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文 件管理功能。 4、关于CPU下面哪个说法是正确的： A)CPU全称为中央处理器（或中央处理单元）。 B)CPU可以直接运行汇编语言。 C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。 D)CPU最早是由Intel公司发明的。 5、关于ASCII，下面哪个说法是正确的： A)ASCII码就是键盘上所有键的唯一编码。 B)一个ASCII码使用一个字节的内存空间就能够存放。 C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的 编码。 D)ASCII码是英国人主持制定并推广使用的。 6、下列软件中不是计算机操作系统的是： A) Windows B) Linux C) OS/2 D) WPS 7、关于互联网，下面的说法哪一个是正确的： A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B)互联网的入网主机如果有了域名就不再需要IP地址。 C)互联网的基础协议为TCP/IP协议。 D)互联网上所有可下载的软件及数据资源都是可以合法免 费使用的。 8、关于HTML下面哪种说法是正确的： A）HTML实现了文本、图形、声音乃至视频信息的统一编码。 B）HTML全称为超文本标记语言。 C）网上广泛使用的Flash动画都是由HTML编写的。 D）HTML也是一种高级程序设计语言。 NOIP2015 普及组解题报告 南京师范大学附属中学树人学校CT 1.金币（coin.cpp/c/pas） 【问题描述】国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金 币；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金 币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K 天里，骑士一共获得了多少金币。【输入格式】 输入文件名为coin.in 。 输入文件只有1行，包含一个正整数K，表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1 行，包含一个正整数，即骑士收到的金币数。 【数据说明】 对于100%的数据，1 < K < 10,000 【思路】 模拟 【时空复杂度】 O(k) ，O(1) 2 、扫雷游戏（mine.cpp/c/pas ） 【问题描述】 扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。 【输入格式】 输入文件名为mine.in 。 输入文件第一行是用一个空格隔开的两个整数n和m分别表示雷区的行数和列数。 接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’* '表示相应格子是地雷格，字符' ?'表示相应格子是非地雷格。相邻字符之间无分隔符。【输出格式】输出文件名为mine.out 。 输出文件包含n行，每行m个字符，描述整个雷区。用’* '表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。 【数据说明】 对于100% 的数据，1< n W 1Q01< me 100 【思路】 模拟 【技巧】 可将数组多开一圈，省去边界条件的判断 【时空复杂度】 O(mn)，O(mn) N O I P2011普及组复赛 1．数字反转（c/pas） 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。（参见样例2） 【输入】 输入文件名为。 输入共一行，一个整数N。 【输出】 输出文件名为。 输出共1行，一个整数，表示反转后的新数。 -1,000,000,000≤N≤1,000,000,000。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题（以及-0，但测试数据没出）。 【法一】字符串处理 Var i,l,k:integer; s:string; p:boolean; begin assign(input, ''); reset(input); assign(output, ''); rewrite(output); readln(s); l:=length(s); k:=1; if s[1]='-' then begin write('-'); k:=2; end; p:=true;; for i:=l downto k do begin if(p)and((s[i]='0')) then continue else begin write(s[i]); p:=false;; end; end; close(input); close(output); end. 【法二】数字处理 Var f:integer; n,ans:longint; begin assign(input, ''); reset(input); 精心整理 NOIP2015普及组解题报告 南京师范大学附属中学树人学校CT 1.金币(coin.cpp/c/pas) 【问题描述】 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天） 放模式会一直这样延续下去：当连续N 续N+1天里，每天收到N+1枚金币。 请计算在前K 【输入格式】 输入文件名为coin.in。 输入文件只有1 【数据说明】 对于100%的数据，1≤K≤10,000。 【思路】 模拟 【时空复杂度】 O(k)，O(1) 2、扫雷游戏（mine.cpp/c/pas） 【问题描述】 扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m 向上与之直接相邻的格子。 【输入格式】 输入文件名为mine.in。 接下来n行，每行m 雷个数表示非地雷格。相邻字符之间无分隔符。 【数据说明】 对于100%的数据，1≤n≤100，1≤m≤100。 【思路】 模拟 【技巧】 可将数组多开一圈，省去边界条件的判断。【时空复杂度】 O(mn)，O(mn) 3.求和(sum.cpp/c/pas) 【问题描述】 一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color i（用[1，m]当中的一个整数表示），并且写了一个数字number i。 定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： 1.x,y,z都是整数,x NOIP2011 （普及组 C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．在二进制下，1011001 + （）= 1100110。 A．1011 B．1101 C．1010 D．1111 2．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。 A．39 B．57 C．120 D．视具体的计算机而定 3．一片容量为8G的SD卡能储存大约（）张大小为2MB的数码照片。 A．1600 B．2000 C．4000 D．16000 4．摩尔定律（Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电驴的集成度大约每（）个月翻一番。A．1 B．6C．18 D．36 5．无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。 A．7 B．21 C．42 D．49 6．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。 A．10 B．11 C．12 D．13 8．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A．快速排序B．插入排序C．冒泡排序D．归并排序 9．一个正整数在二进制下有100位，则它在十六进制下有（）位。 A．7 B．13 C．25 D．不能确定 10．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（）。 A．正确的，将文件放入回收站以为着彻底删除、无法恢复 B．不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C．不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D．不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除 第二十三届全国青少年信息学奥林匹克联赛初赛 普及组C++语言试题 竞赛时间：2017年10月14日14:30~16:30 选手注意： ●试题纸共有7 页，答题纸共有2 页，满分100 分。请在答题纸上作答，写在试题纸上的一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共20 题，每题 1.5 分，共计30 分；每题有且仅有一个正确选项） 1. 在8 位二进制补码中，10101011 表示的数是十进制下的（）。 A. 43 B. -85 C. -43 D. -84 2. 计算机存储数据的基本单位是（）。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是（）。 A. POP3 B. SMTP C. WTO D. IMAP 4. 分辨率为800x600、16 位色的位图，存储图像信息所需的空间为（）。 A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB 5. 计算机应用的最早领域是（）。 A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制 6.下列不属于面向对象程序设计语言的是（）。 A. C B. C++ C. Java D. C# 7. NOI 的中文意思是（）。 A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛 C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机协会 8. 2017 年10 月1 日是星期日，1999 年10 月1 日是（）。 A. 星期三 B. 星期日 C. 星期五 D. 星期二 9.甲、乙、丙三位同学选修课程，从4 门课程中，甲选修2 门，乙、丙各选修3门，则不同的选修方案共有（）种。 A. 36 B. 48 C. 96 D. 192 10. 设G 是有n 个结点、m 条边（n ≤ m）的连通图，必须删去G 的（）条边，才能使得G 变成一棵树。 A. m – n + 1 B. m - n C. m + n + 1 D. n – m + 1 11. 对于给定的序列{ak}，我们把(i, j) 称为逆序对当且仅当i < j 且ai > aj。那么 序列1, 7, 2, 3, 5, 4 的逆序对数为（）个。 A. 4 B. 5 C. 6 D. 7 12. 表达式a * (b + c) * d 的后缀形式是（）。 A. a b c d * + * B. a b c + * d * C. a * b c + * d D. b + c * a * d 13.向一个栈顶指针为hs 的链式栈中插入一个指针s 指向的结点时，应执行（）。 A.hs->next = s; B.s->next = hs; hs = s; C.s->next = hs->next; hs->next = s; D.s->next = hs; hs = hs->next; 14. 若串S = “copyright”，其子串的个数是（）。 A. 72 B. 45 C. 46 D. 36 15. 十进制小数13.375 对应的二进制数是（）。 A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01 NOIP复赛普及组试题 ————————————————————————————————作者：————————————————————————————————日期： CCF全国信息学奥林匹克联赛（NOIP2013）复赛 普及组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称计数问题表达 式求 值 小朋友的 数字 车站分 级 英文 题目 与子 目录 名 count expr number level 可执行 文件名 count expr number level 输入文 件名 count.in expr.in number.in level.in 输出文count.out expr.out n umber.out level.out 件名 每个 测试 点时 限 1 秒 1 秒 1 秒 1 秒 测试点 数目 10 10 10 10 每个 测试 点分 值 10 10 10 10 附加样 例文件 有有有有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类 型 传统传统传统传统 运行内 存上限 128M 128M 128M 128M 二．提交源程序文件名 对于 C++语 言 count.cpp expr.cpp number.cpp level.cpp 对于 C 语 言 count.c expr.c number.c level.c 对于 pascal 语言 count.pas expr.pas number.pas level.pas 三．编译命令（不包含任何优化开关） 对于C++语言 g++ -o count count.cpp -lm g++ -o expr expr.cpp –lm g++ -o number number.cpp -lm g++ -o level level.cpp -lm 对于C 语言gcc -o count gcc -o expr gcc-o number gcc -o level noip2017提高组复赛解题报告 定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，融科教育信息学竞赛培训等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！以下解题思路及代码未经官方评测，仅供参考，复赛成绩以官方（CCF）评测结果为准。 Day1 1.小凯的疑惑(math.cpp/c/pas)【问题描述】小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为math.in。输入数据仅一行，包含两个正整数a 和b，它们之间用一个空格隔开，表示小凯手中金币的面值。【输出格式】输出文件名为math.out。输出文件仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例1】math.in3 7 math.out11【数据规模与约定】对于30%的数据: 1 ≤a，b ≤50。对于60%的数据: 1 ≤a，b ≤10,000。对于100%的数据:1 ≤a，b ≤1,000,000,000。数学太差只找规律吧。 设：其中一个数为2则：2、3=>1；2、5=>3；2、7=>5；2、11=>9得：2、n=>n-2设：其中一个数为3则：3、5=>7；3、7=>11；3、11=>19；3、13=>23得：3、n=>2n-3设：其中一个数为5则：5、7=>23；5、11=>39；5、13=>47；5、17=>63得：5、n=>4n-5所以：m、n=>(m-1)n-m #includeusing namespace std;int main(){ long long a,m,n; scanf('%lld %lld',&m,&n); a=(m-1)*n-m; printf('%lld',a); return 0;} 2.时间复杂度(complexity.cpp/c/pas)【问题描述】小明正在学习一种新的编程语言A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。A++语言的循环结构如下:其中“F i x y”表示新建变量(i 变量i 不可与未被销毁的变量重名)并初始化为x，然后判断i 和y 的大小关系，若i 小于等于y 则进入循环，否则不进入。每次循环结束后i都会被修改成i +1，一旦i 大于y 终止循环。x和y 可以是正整数(x 和y 的大小关系不定)或变量n。n 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于100。“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。注:本题中为了书写方便，在描述复杂度时，使用大 数字反转题目描述 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形 式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【数据范围】 -1,000,000,000 ≤ N≤ 1,000,000,000。 输入格式 输入共 1 行，一个整数N。 输出格式 输出共 1 行，一个整数，表示反转后的新数。 样例输入： 123 －380 样例输出： 321 －83 统计单词数题目描述 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位 置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章 中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。 【数据范围】 1 ≤ 单词长度≤ 10。 1 ≤ 文章长度≤ 1,000,000。 【输入输出样例 1 说明】 输出结果表示给定的单词To 在文章中出现两次，第一次出现的位置为0。 【输入输出样例 2 说明】 表示给定的单词to 在文章中没有出现，输出整数-1。 输入格式 第 1 行为一个字符串，其中只含字母，表示给定单词； 第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。 输出格式 只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开， 分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字 母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。 样例输入： [sample 1] To to be or not to be is a question [sample 2] to Did the Ottoman Empire lose its power at that time 样例输出： [sample 1] 2 0 [sample 2] -1 瑞士轮题目描述 2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第2K-1名和第2K名、……、第2N-1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。我 们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。 输入格式 输入的第一行是三个正整数N、R、Q，每两个数之间用一个空格隔开，表示有2*N名选手、R轮比赛，以及我们关心的名次Q。 第二行是2*N个非负整数s1，s2，…，s2N，每两个数之间用一个空格隔开，其中si表示编号为i 的选手的初始分数。 第三行是2*N个正整数w1，w2，…，w2N，每两个数之间用一个空格隔开，其中wi表示编号为i 的选手的实力值。 输出格式NOIP2012初赛普及组C++题目及答案
棋盘解题报告(noip2017普及组第三题)
NOIP2011普及组复赛(试题+源程序)
(完整word)NOIP2010提高组初赛试题及详细解析
noip普及组复赛模拟试题18
noip2014普及组复赛题解
noip2011初赛试题及答案(完美Word版)
NOIP1999普及组(复赛)
NOIP2015普及组解题报告
NOIP2015普及组复赛试题
历年noip初赛普及组试题(完整资料).doc
NOIP普及组复赛解题报告
NOIP普及组复赛试题源程序
NOIP2015普及组复赛解题报告
noip2011 初赛普及组c++试题及答案
NOIP2017初赛普及组C++试题及答案
NOIP复赛普及组测试试题
noip2017提高组复赛解题报告
NOIP2011普及组
- 08普及组复赛+解题报告
- NOIP2008普及组复赛试题与解题报告
- NOIP2017普及组解题报告非官方
- NOIP2013普及组复赛试题+解题报告
- 棋盘解题报告(noip2017普及组第三题)
- NOIP2014普及组复赛试题解答
- noip2017提高组复赛解题报告
- noip2015普及组题解最终
- 2012全国信息学联赛复赛普及组解题报告
- NOI普及组复赛解题报告
- NOIP 2006年普及组解题报告
- noip普及组复赛解题报告
- NOIP2015普及组复赛解题报告
- NOIP2012普及组复赛试题及解答
- NOIP2005普及组复赛试题(附题解)
- NOIP2015普及组复赛解题报告
- NOIP2012普及组复赛解题报告c++版本
- NOIP2014复赛普及组第一题题解
- noip2016普及组解题报告
- NOIP2015普及组解题报告