NOIP2001

NOIP2014提高组复赛精彩试题(卷)

CCF全国信息学奥林匹克联赛（NOIP2014）复赛 提高组 day1 1．生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势： 斯波克：《星际迷航》主角之一。 蜥蜴人：《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。 表一石头剪刀布升级版胜负关系 现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……” 已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。 【输入】 输入文件名为rps.in。 第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。 第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。数与数之间以一个空格分隔。

Noip2001年普及组复赛题目

NOI’2001第七届全国青少年信息学（计算机）奥林匹克分区联 赛复赛试题 普及组 题一数的计算(20分) 问题描述 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理: 1.不作任何处理; 2.在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3.加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 输出: 6 题二最大公约数和最小公倍数问题(20分) 问题描述 输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数 条件: 1.P,A是正整数 2.要求P,Q以x0为最大公约数,以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 样例 输入:x0=3 yo=60 输出:4 说明(不用输出)此时的P Q 分别为: 3 60 15 12 12 15 60 3 所以:满足条件的所有可能的两个正整数的个数共4种. 题三求先序排列（30分） 问题描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不

同的大写字母表示，长度<=8）。 样例 输入：BADC BDCA 输出：ABCD 题四装箱问题（30分） 问题描述 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n ＜＝30＝，每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 样例 输入： 24一个整数，表示箱子容量 6一个整数，表示有n个物品 8接下来n行，分别表示这n 个物品的各自体积 3 12 7 9 7 输出： 0一个整数，表示箱子剩余空间。

NOIP2001提高组初赛试题答案

第七届分区联赛提高组初赛 (提高组PASCAL语言二小时完成) 一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分) 1、中央处理器CPU能访问的最大存储器容量取决于( ) A)地址总线B)数据总线C)控制总线 D)内存容量 2、计算机软件保护法是用来保护软件( )的。 A)编写权B)复制权C)使用权D)著作权 3、64KB的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF 4、在树型目录结构中，不允许两个文件名相同主要指的是( ) A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 5、下列设备哪一项不是计算机输入设备( ) A)鼠标B)扫描仪C)数字化仪D)绘图仪 6、在计算机硬件系统中，cache是( )存储器 A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲 7、若我们说一个微机的CPU是用的PII300，此处的300确切指的是( ) A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 8、Email邮件本质上是一个( ) A)文件B)电报C)电话D)传真 9、2KB的内存能存储( )个汉字的机内码 A)1024 B)516 C)2048 D)218 10、以下对Windows的叙述中，正确的是( ) A)从软盘上删除的文件和文件夹，不送到回收站 B)在同一个文件夹中，可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 11、运算式(2047)10—(3FF)16+(2000)8的结果是( ) A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16 12、TCP/IP协议共有( )层协议 A)3 B)4 C)5 D)6 13.若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是( ) A)i B)n-1 C)n-i+1 D)不确定 14.计算机病毒是( ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 15.下面关于算法的错误说法是( ) A)算法必须有输出B)算法必须在计算机上用某种语言实现

NOIP2008提高组复赛试题及题解

全国信息学奥林匹克联赛（NOIP2008）复赛 提高组 一、题目概览 二、提交源程序文件名 三、编译命令（不包含任何优化开关） 四、运行内存限制 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用大写。 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。

1. 笨小猴 (word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。 【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer; s:string; l,i,max,min,n:integer; ch:char;flag:boolean; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(s);

NOIP2013提高组复赛Day2

CCF全国信息学奥林匹克联赛（NOIP2013）复赛 提高组 day2 （请选手务必仔细阅读本页内容） 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+， 2.71GHz，内存2G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在NOI Linux下进行。

1．积木大赛 (block.cpp/c/pas) 【题目描述】 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是?i。 在搭建开始之前，没有任何积木（可以看成n块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块到第R块之间（含第L块和第R块）所有积木的高度分别增加1。 小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。 【输入】 输入文件为block.in 输入包含两行，第一行包含一个整数n，表示大厦的宽度。 第二行包含n个整数，第i个整数为?i。 【输出】 输出文件为block.out 仅一行，即建造所需的最少操作数。 【样例解释】 其中一种可行的最佳方案，依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 【数据范围】 对于30%的数据，有1≤n≤10； 对于70%的数据，有1≤n≤1000； 对于100%的数据，有1≤n≤100000，0≤?i≤10000。

noip2017提高组复赛解题报告

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”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。注:本题中为了书写方便，在描述复杂度时，使用大

NoiP2003提高组复赛试题分析

第一题：神经网络 【试题分析】 一、题意分析 1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。输出输出层中信号大于零的节点编号和信号大小。（节点编号由小到大）如果没有满足条件的编号则输出NULL。 信号传递公式： ∑ ∈- = E i j i j ji i U C W C ), ( 公式中的W ji （可能为负值）表示连接j号神经元和i号神经元的边的权值。 当C i 大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于 兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为C i 。 2、输入： 两个整数n（1≤n≤20）和p。n表示节点的个数；p表示有向边的条数。 下面n行表示1-n号节点的状态和阈值。 下面p行表示有向边及其权值。 3、输出： 输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！ 若输出层的神经元最后状态小于等于0，则输出NULL。 二、问题分析 1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。所以不必进行拓扑排序，一层一层的向下传递信号即可。输出最后一层中信号大于零的节点编号。 2、可以建立一个队列，将输入层节点入队。 3、取队首节点出队，寻找此节点有向边，如果有有向边： 1）则记录此节点不是输出层； 2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。再出队再传递，直至全部出队。 注意：1）输入层可以是输出层。2）信号传递公式中只减一次U[i]。 【程序清单】 Program network; Const InName='network.in'; OutName='network.out';

noip2001初赛试题及答案

〓〓第七届全国青少年信息学奥林匹克联赛(NOIP2001)初赛试题〓〓 (普及组PASCAL语言二小时完成) ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分) 1.在计算机内部，一切信息存取、处理和传递的形式是() A)ASCII码B)BCD码C)二进制D)十六进制 2.在树型目录结构中，不允许两个文件名相同主要指的是() A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下C)同一个磁盘的同一个目录下 3.WORD是一种() A)操作系统B)文字处理软件C)多媒体制作软 件D)网络浏览器 4.计算机软件保护法是用来保护软件()的。 A)编写权B)复制权C)使用权D)著作权 5.下面关于算法的错误说法是() A)算法必须有输出B)算法必须在计算机上用某种语言实现 C)算法不一定有输入D)算法必须在有限步执行后能结束 6.解释程序的功能是() A)将高级语言程序转换为目标程序B)将汇编语言程序转换为目标程序 C)解释执行高级语言程序D)解释执行汇编语言程序 7.与二进制数101.01011等值的十六进制数为() A)A.B B)5.51C)A.51 D)5.58 8.断电后计算机信息依然存在的部件为() A)寄存器B)RAM存储器C)ROM存 储D)运算器

9.2KB的内存能存储()个汉字的机内码 A)1024B)516C)2048D)218 10.DOS暂驻区中的程序主要是用于() A)执行DOS内部命令B)执行DOS外部命令 C)执行DOS所有命令D)基本输入输出 11.若我们说一个微机的CPU是用的PII300，此处的300确切指的是() A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 12.运算17MOD4的结果是() A)7B)3C)1D) 4 13.应用软件和系统软件的相互关系是() A)后者以前为基础B)前者以后者为基础 C)每一类都以另一类为基础D)每一类都不以另一类为基础 14.以下对Windows的叙述中，正确的是() A)从软盘上删除的文件和文件夹，不送到回收站 B)在同一个文件夹中，可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 15.Email邮件本质上是一个() A)文件B)电报C)电话D)传真 16.计算机病毒是() A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合

NOIP2001普及组初赛试题与答案

NOIP2001普及组初赛试题 (普及组PASCAL语言二小时完成) 一、选择一个正确答案代码(A/B/C/D)，填入每题的括号内(每题1.5分，多选无分，共30分) 1.在计算机内部，一切信息存取、处理和传递的形式是( ) A)ASCII码 B)BCD码 C)二进制 D)十六进制 2.在树型目录结构中，不允许两个文件名相同主要指的是( ) A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 3.WORD是一种( ) A)操作系统 B)文字处理软件 C)多媒体制作软件 D)网络浏览器 4.计算机软件保护法是用来保护软件( )的。 A)编写权B)复制权C)使用权D)著作权 5.下面关于算法的错误说法是( ) A)算法必须有输出B)算法必须在计算机上用某种语言实现 C)算法不一定有输入 D)算法必须在有限步执行后能结束 6.解释程序的功能是( ) A)将高级语言程序转换为目标程序B)将汇编语言程序转换为目标程序 C)解释执行高级语言程序D)解释执行汇编语言程序 7.与二进制数101.01011等值的十六进制数为( ) A)A.B B)5.51 C)A.51 D)5.58 8.断电后计算机信息依然存在的部件为( ) A)寄存器 B)RAM存储器 C)ROM存储 D)运算器 9.2KB的内存能存储( )个汉字的机内码 A)1024 B)516 C)2048 D)218 10.DOS暂驻区中的程序主要是用于( ) A)执行DOS内部命令B)执行DOS外部命令 C)执行DOS所有命令D)基本输入输出 11.若我们说一个微机的CPU是用的PII300，此处的300确切指的是( ) A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 12.运算17 MOD 4的结果是( ) A)7 B)3 C)1 D)4 13.应用软件和系统软件的相互关系是( ) A)后者以前为基础B)前者以后者为基础 C)每一类都以另一类为基础D)每一类都不以另一类为基础 14.以下对Windows的叙述中，正确的是( ) A)从软盘上删除的文件和文件夹，不送到回收站 B)在同一个文件夹中，可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 15.Email邮件本质上是一个( ) A)文件B)电报C)电话D)传真 16.计算机病毒是( )

NOIP2012提高组复赛试题

全国信息学奥林匹克联赛（2012）复赛提高组2 2． 1 ·同余方程 〖问题描述〗 求关于的同余方程三1 (句的最小正整数解。 输入〗 输入文件为 输入只有一行，包含两个正整数用一个空格隔开 输出〗 输出文件为 输出只有一行，包含一个正整数№即最小正整数解。输入数据保证一定有解。 〖输入输出样例〗 对于40％的数据，2 L000：对于60％的数据， 2 50，000，000： 对于100％的数据，2，2，000，000，000。 2 ·借教室 (. ) 问题描述〗 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问 题。

我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借个教室。 我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改 输入〗 输入文件为 第一行包含两个正整数n，m,表示天数和订单的数量。 第二行包含n个正整数，其中第i个数为，表示第i天可用于租借的教室数量。 接下来有m行，每行包含三个正整数]，t]，表示租借的数量，租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。 〖输出〗 输出文件为 如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数一1 ,第二行输出需要修改订单的申请人编号。 〖输入输出样例〗

1112 求先序排列【NOIP2001普及组】 1113 装箱问题【NOIP2001普及组】

求先序排列【NOIP2001普及组】 Time Limit:10000MS Memory Limit:65536K Total Submit:4 Accepted:4 Description 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<= 8）。 样例输入： BADC BDCA 样例输出： ABCD Input Output Sample Input BADC BDCA Sample Output ABCD Source

?var ? s1,s2:string; ?procedure dfs(s1,s2:string); ?var ch:char; ? p:longint; ?begin ? if length(s1)=0 then exit; ? ch:=s2[length(s2)]; ? write(ch); ? p:=pos(ch,s1); ? dfs(copy(s1,1,p-1),copy(s2,1,p-1)); ? dfs(copy(s1,p+1,length(s1)-p),copy(s2,p,length(s2)-p)); ?end; ? ?begin ? readln(s1); ? readln(s2); ? dfs(s1,s2); ?end.

装箱问题【NOIP2001普及组】 Time Limit:10000MS Memory Limit:65536K Total Submit:23 Accepted:20 Description 有一个箱子容量为V（正整数，0 ＜＝V ＜＝20000），同时有n个物品(0 ＜n ＜＝30)，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 Input 24一个整数，表示箱子容量 6一个整数，表示有n个物品 8接下来n行，分别表示这n 个物品的各自体积 3 12 7 9 7 Output 0一个整数，表示箱子剩余空间。 Sample Input 24 {一个整数，表示箱子容量} 6 {一个整数，表示有n个物品} 8 {接下来n行，分别表示这n 个物品的各自体积} 3 12 7 9 7 Sample Output

NOIP2018提高组复赛试题day2

CCF全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day2 （请选手务必仔细阅读本页内容） 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存 32GB。上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。

1．旅行 (travel.cpp/c/pas) 【问题描述】 小Y是一个爱好旅行的OIer。她来到X国，打算将各个城市都玩一遍。 小Y了解到，X国的 n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且，从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小Y只能通过这些道路从一个城市前往另一个城市。 小Y的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小Y回到起点时，她可以选择结束这次旅行或继续旅行。需要注意的是，小Y要求在旅行方案中，每个城市都被访问到。 为了让自己的旅行更有意义，小Y决定在每到达一个新的城市（包括起点）时，将它的编号记录下来。她知道这样会形成一个长度为 n 的序列。她希望这个序列的字典序最小，你能帮帮她吗？ 对于两个长度均为 n 的序列A和B，当且仅当存在一个正整数x，满足以下条件时，我们说序列A的字典序小于B。 ?对于任意正整数1≤i

NOIP2016提高组复赛试题(Day1+Day2)

第22 届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组（复赛）第一试 竞赛时间：2016 年11 月19 日8:30 ～12:00 提交源程序文件名 编译选项 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。 3. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须 是0。 4. 全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor， 2.8GHz，内存4G，上述时限以此配置为准。 5. 只提供Linux 格式附加样例文件。 6. 评测在NOI Linux 下进行。 7. 编译时不打开任何优化选项。

玩具谜题（toy) 【问题描述】 小南有一套可爱的玩具小人，它们各有不同的职业。 有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图： 这时singer 告诉小南一个谜题：“眼镜藏在我左数第3 个玩具小人的右数第1 个玩具小人的左数第2 个玩具小人那里。” 小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。 小南一边艰难地辨认着玩具小人，一边数着： “singer 朝内，左数第3 个是archer。 “archer 朝外，右数第1 个是thinker。 “thinker 朝外，左数第2 个是writer。 “所以眼镜藏在writer 这里！” 虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为： 有n 个玩具小人围成一圈，己知它们的职业和朝向。现在第1 个玩具小人告诉小南一个包含m 条指令的谜题，其中第i 条指令形如“左数/右数第s i个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。

NOIP+提高组复赛试题汇编(1998-2009)

NOIP 1998 1．火车从始发站（称为第1站）开出，在始发站上车的人数为a ，然后到达第2站，在第2站有人上、 下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a 人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N 个车站，始发站上车的人数为a ，最后一站下车的人数是m （全部下车）。试问x 站开出时车上的人数是多少？2．设有n 个正整数（n ≤20），将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213又如：n=4时，4个整数7，13，4，246联接成的最大整数为：74246133．著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。例如： 其含义为： L+L=L ，L+K=K ，L+V=V ，L+E=E K+L=K ，K+K=V ，K+V=E ，K+E=KL E+E=KV 根据这些规则可推导出：L=0，K=1，V=2，E=3 同时可以确定该表表示的是4进制加法 NOIP 1999 第一题拦截导弹 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例：INPUT OUTPUT 38920715530029917015865 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数） 输入：a ，n ，m 和x 输出：从x 站开出时车上的人数。 程序输入：n n 个数 程序输出：联接成的多位数 程序输入： n （n ≤9）表示行数。 以下n 行，每行包括n 个字符串，每个字串间用空格隔开。（字串仅有一个为‘+’号，其它都由大写字母组成） 程序输出： ①各个字母表示什么数，格式如：L=0，K=1，…… ②加法运算是几进制的。 ③若不可能组成加法表，则应输出“ERROR ！”

NOIP2001提高组

第七届（2001）分区联赛复赛解题报告（提高组） 第一题：一元三次方程求解(p1.pas p1.in p1.out) 问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，若存在2个数x1和x2，且x1

NOIP2005提高组复赛第二题 过河分析

过河 【问题描述】在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【输入文件】输入文件river.in的第一行有一个正整数L（1 ≤L ≤109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1≤S≤T≤10，1≤M≤ 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【输出文件】输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。方法1：搜索 ?直叙式搜索不行：搜索桥有困难（桥的长度1..109）；搜索石子更困难,（石头的分布是没有任何规律） ?优化：以桥的长度为对象搜索+巧妙的剪枝 ?分析：从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109)，石头数也为最大值(100)，则中间一定会有很多“空长条” (两个石子中的空地)，关键是如何在处理时把这些“空长条”跳过，使得运算次数降到M次。

NOIP1995提高组复赛试题

NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛 分区联赛复赛试题（高中组） （上机编程，完成时间：210分钟） <1>编码问题： 设有一个数组A:ARRAY[0..N-1] OF INTEGER； 数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。 例如：N=6时，有：A=（4，3，0，5，1，2） 此时，数组A的编码定义如下： A[0]的编码为0； A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）∴上面数组A的编码为：B=（0，0，0，3，1，2） 程序要求解决以下问题： ①给出数组A后，求出其编码。 ②给出数组A的编码后，求出A中的原数据。 <2>灯的排列问题： 设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……N k（k表示不同颜色灯的个数）。 放灯时要遵守下列规则： ①同一种颜色的灯不能分开； ②不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序 B-R顺序

放置的总数为12种。 数据输入的方式为： N P1（颜色，为一个字母）N1（灯的数量） P2 N2 …… Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。 <3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8 如下图所示放置： 其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。 计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的： 计算所用到的计算符为：+，-，?，且无优先级之分（自左向右计算），运算符最多为2个。 如：3+4?5=35 5?4+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的： A=B?C+B 也就是：8=2?3+2，15=3?4+3，……14=2?6+2 程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 ①输入数据不存在出错的情况，同时也不会超过整数的范围。 ②计算时可允许出现以下情况： A=B （即可理解为运算符的个数为零） A=B?B+B （即全部由B产生）

NOIP2012提高组复赛试题

CCF全国信息学奥林匹克联赛（NmP2012）复赛提高组day2 2． 1 ·同余方程 〖问题描述〗 求关于的同余方程三1 (mod句的最小正整数解。 输入〗 输入文件为mod.ino 输入只有一行，包含两个正整数用一个空格隔开 输出〗 输出文件为mod.outo 输出只有一行，包含一个正整数№即最小正整数解。输入数据保证一定有解。 〖输入输出样例〗 对于40％的数据，2 L000：对于60％的数 据，2 50，000，000： 对于100％的数据，2，2，000，000，000。 2 ·借教室 (classroom. cpp/c/pas) 问题描述〗 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问题。 我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借dj个教室。 我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改 输入〗 输入文件为classroom.in 第一行包含两个正整数n，m,表示天数和订单的数量。

NOIP2016提高组复赛试题(Day1+Day2)

第22届全国青少年信息学奥林匹克联赛 2016 提高组（复赛）第一 试 竞赛时间：2016年11月19日8:30 ?12:00 提交源程序文件名 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。 3. 中函数（）的返回值类型必须是，程序正常结束时的返回值必须是0。 4. 全国统一评测时采用的机器配置为：（）x2 240 , 2.8 , 内存4G,上述时限以此配置为准。 5. 只提供格式附加样例文件。 6. 评测在下进行。 7. 编译时不打开任何优化选项。 玩具谜题（）

【问题描述】 小南有一套可爱的玩具小人，它们各有不同的职业。 有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图： 这时告诉小南一个谜题：“眼镜藏在我左数第3个玩具小人的 右数第1个玩具小人的左数第2个玩具小人那里。” 小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。 小南一边艰难地辨认着玩具小人，一边数着： “朝内，左数第3个是。 “朝外，右数第1个是。 “朝外，左数第2个是。 “所以眼镜藏在这里！” 虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为： 有n个玩具小人围成一圈，己知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜题，其中第i条指令形如 “左数/ 右数第个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。