全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
全国信息学奥林匹克联赛（NOIP2013）复赛模拟
普及组
一.题目概览 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 题目类型
lignment lignment lignment lignment.in lignmentout 1秒 10 10 全文比较 传统 消息传递 relay relay relay.in relay.out 1秒 10 10 全文比较 传统 Cow Crossings crossings crossings crossings.in crossings.out 1秒 10 10 全文比较 传统 算周长 perimeter perimeter perimeter.in perimeter.out 1秒 10 10 全文比较 传统 二.提交源程序文件名 对于pascal语言 对于C语言 对于C++语言 alignment pas alignment.c alignment.cpp relay.pas relay.c relay.cpp crossings.pas crossings.c crossings.cpp perimeter.pas perimeter.c perimeter.cpp 三.编译命令（不包含任何优化开关） 对于pascal语言 对于C语言 对于C++语言 fpc queue.pas gcc –o queue queue.c g++ –o queue queue.cpp fpc windows.pas gcc –o windows windows.c g++ –o windows windows.cpp fpc s4.pas gcc –o s4 s4.c g++ –o s4 s4.cpp fpc book.pas gcc –o book book.c g++ –o book book.cpp 四.运行内存限制 运行内存上限 50M 50M 50M 50M 注意事项：
1、文件名（程序名和输入输出文件名）必须使用小写。
2、C/C++中函数main（）的返回值类型必须是int，程序正常结束时的返回值必须是0。
第 1 页 共 6 页
全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
alignment
(alignment.pas/c/cpp)
【问题描述】
北欧风光无限好啊无限好，北欧天气无比冷啊无比冷，北欧题目超级水啊超级水（??表示不解），这不，来了一些北欧oier在一起做起来题目。题目中有许多信息，每行一条信息，信息由字符串构成，可是大家对其中太多的空格略感不爽，便希望这些信息越短越好。我们在这里定义一种“缩句”规则。 每一行的信息由许多单词构成，这里单词可以是常规单词，也可以是非空格字符，换句话说，若原信息一个子字符串不包含空格，且两端为空格或文件始末，则其可称为一个单词。 对于每一行的信息，由许多单词构成，我们设第i行第j个单词为aij，则我们要求所有行的信息首末无空格，相邻单词间至少用一个空格隔开。同时若第i行存在第j个单词，则其必须与其他行第j个单词拥有相同的起始位置；若不存在，则不用处理。 现在，输入一些信息，请你将“缩句”后的信息输出。 【输入格式】
文件输入有若干行，对于每一行，是一个字符串（每个字符ascall码不超过200），每行最多100个字符，最多有1000行。 【输出格式】
输出“缩句”后的信息。 【样例输入/输出】
第 2 页 共 6 页
全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
消息传递 (relay.pas/c/cpp)
【问题描述】
Farmer John的N头奶牛(1 <= N <= 1000)被编号成1..N。通过使用基于老式的锡罐和字符串的沟通机制，奶牛们弄清楚了如何在不被FJ发现的情况下互相之间通信。
每头奶牛可以至多给另一头奶牛转发消息：对奶牛i来说，F（i）的值表示奶牛i会转发她接到的任何消息给的奶牛的编号（编号与i不同）。如果F（i）是0，那么奶牛i不转发信息。
不幸的是，奶牛们意识到从某一头奶牛发出的信息最终会陷入死循环中的可能性。如果从某一头奶牛发出的信息最终会陷入死循环中，那么这头奶牛被称为“糊涂的”。奶牛们想要避免“糊涂的”奶牛发消息。请帮助他们计算FJ奶牛中“不糊涂的”奶牛总数。 【输入格式】
第1行：奶牛总数，N。
第2 至1+N行：第i+1行包含F（i）的值。
【输出格式】 1行：“不糊涂的”奶牛总数。
【输入样例】
5 0 4 1 5 4
输入详情：现在有5头奶牛，奶牛1不转发消息，奶牛2转发消息给奶牛4，以此类推 【输出样例】 2
输出详情：因为奶牛1不转发消息，所以“不糊涂”。奶牛3“不糊涂”，因为他转发给不转发消息的奶牛1.其他所有奶牛都是“糊涂”的。
第 3 页 共 6 页
全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
crossings
（crossings.pas/c/c++）
【问题描述】
每天，Farmer John的N头奶牛(1 <= N <= 100,000) 需要穿过农场中间的一条路。根据FJ农场的2D平面图，这条路是水平的，其中一边以y=0表示，另一边以y=1表示。奶牛i通过走一条直线，从一边的位置(a_i, 0) 到 另一边的位置(b_i, 1)来穿过这条路。所有a_i和b_i都是不同的，范围是-1,000,000...1,000,000的整型。
尽管奶牛们相对地有灵活性，FJ经常担心那些路径相交的奶牛们可能会伤害对方。FJ认为一头奶牛是安全的，则其他奶牛的路径不会和她的路径相交。请帮助FJ计算安全奶牛的个数。
【输入格式】
第1行：奶牛总数，N。
第2 ..1+N行：第i行包含整型数a_i和 b_i，表示奶牛i采用的路径。
【输出格式】
仅一行,安全奶牛的数量。
【输入样例】
4 -3 4 7 8 10 16 3 9
输入详情：现在有4头奶牛。奶牛1的路线为从(-3,0)到(4,1)，其他以此类推。
【输出样例】 2
第一头和第三头奶牛的路径不会和其他奶牛路径相交。第二头和第四头奶牛的路径会和其他奶牛路径相交
第 4 页 共 6 页
全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
算周长
(perimeter.pas/c/c++)
【问题描述】
Farmer John在一块区域的中间放上了N个干草包(1 <= N <= 10,000)。如果我们把这块区域当成一个由 1 x 1方格组成的 100 x 100方格的区域，每个干草包占据一个方格（当然两个干草包不能占据同一个方格）。
FJ注意到他的干草包形成一个大的连通区域，意味着从一个干草包开始，通过若干步的东南西北四个方向直接到达相邻的干草包，从而可以到达其他任何的干草包。干草包组成的连通区域可能包含“洞”——被干草包完全包围的空区域。
请帮助FJ确定由干草包形成的区域的周长。注意，那些“洞”不算在周长里。
【输入格式】
第1行：干草包的数量，N。
第2..1+N行：每行包含一个干草包的位置（x,y），x和y是1 。。100范围内的整型数。（1,1）是区域中左下方的方格，（100，100）是右上方的方格。
【输出格式】
连通区域的周长。
【输入样例】
8 5 3 5 4 8 4 5 5 6 3 7 3 7 4 6 5
输入详情：
连通区域包含的干草包如下图： XX X XX XXX
【输出样例】 14
输出详情：
连通区域的周长为14。这块区域的左侧周长为3。观察到中间的洞没有增加周长的长度。
第 5 页 共 6 页
全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组
第 6 页 共 6 页
NOIP2013普及组模拟试题1
