NOIP2013普及组模拟试题2.doc

全国信息学奥林匹克联赛（NOIP2013）复赛模拟 普及组全国信息学奥林匹克联赛（NOIP2013）复赛模拟普及组一.题目概览中文题目名称mirrors刷墙算周长饥饿的奶牛英文题目名称mirrorspainttruthhunger可执行文件名mirrorspainttruthhunger输入文件名ruth .inhunger .in输出文件名mirrors.outpaint.outtruth.outhunger.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010比较方式全文比较全文比较全文比较全文比较题目类型传统传统传统传统二.提交源程序文件名对于pascal语言mirrors.paspaint.pastruth.pashunger.pas对于C语言mirrors.cpaint.ctruth.chunger.c对于C+语言mirrors.cpppaint.cpptruth.cpphunger.cpp三.编译命令（不包含任何优化开关）对于pascal语言fpc queue.pasfpc windows.pasfpc s4.pasfpc book.pas对于C语言gcc o queuequeue.cgcc o windowswindows.cgcc o s4s4.cgcc o bookbook.c对于C+语言g+ o queuequeue.cppg+ o windowswindows.cppg+ o s4s4.cppg+ o bookbook.cpp四.运行内存限制运行内存上限50M50M50M50M注意事项：1、文件名（程序名和输入输出文件名）必须使用小写。2、C/C+中函数main（）的返回值类型必须是int，程序正常结束时的返回值必须是0。mirrors(mirrors.pas/c/cpp)【问题描述】 Farmer John的奶牛在农场周围制造了很多麻烦，所以他想要更加密切地关注它们。通过在农场的不同位置安装N块反光栅栏(1 = N = 200)，他希望能够从他的房间（在（0,0）位置）看得到谷仓中（a，b）的位置。在Farmer john农场的2D地图上，栅栏i用一条短线段表示，这条线段的中心在整型数位置（x_i,y_i）并且倾斜45度，如/和。例如，一根形如/在（3,5）的栅栏可以被表示成一根从（2.9,4.9）到（3.1,5.1）线段。每根栅栏（也包括整个谷仓的位置）都在不同的整数坐标范围内 -1,000,000.1,000,000。没有一根栅栏在（0,0）或者（a，b）。Farmer John计划坐在他的房间（0,0）里，直接向右看（在+x方向）。当他的目光从农场上一些反光栅栏上掠过，他希望能看到点（a，b）。不幸的是，Farmer John认为他将一根栅栏的方向安装得不正确（例如，是，而不是/）。请输出在Farmer John列表上需要更改的第一根栅栏的序号，修改它的方向后（在/和之间修改，或反之亦然），Farmer John能够看见点（a，b）。如果Farmer John不改变任何栅栏的方向就可以看见点（a，b），请输出0。如果在改变了一个栅栏后仍然看不见（a，b），则输出-1。【输入格式】 *第1行：三个空格隔开的整型数，N，a和b。*第2 .1+N行：第i+1行描述了第i根栅栏，表示为x_i y_i / 或者 x_i y_i 。其中，(x_i, y_i)是该栅栏中心的位置，/或表明它的方向。 【输出格式】 5 6 23 0 /0 2 /1 2 /3 2 1 3 输入详情：农场的地图如下（H表示Farmer John的房子和B表示谷仓）3 . 2 /.B 1 . 0 H./. 0123456。 【输入样例】5 6 23 0 /0 2 /1 2 /3 2 1 3 输入详情：农场的地图如下（H表示Farmer John的房子和B表示谷仓）3 . 2 /.B 1 . 0 H./. 0123456【输出样例】4输出详情：通过改变在（3,2）位置的栅栏，Farmer John可以看见点（a，b）。地图上显示为：3 . 2 /./-B 1 .|. 0 H-/. 0123456 刷墙（paint.pas/c/c+）【问题描述】Farmer John已经设计了一种方法来装饰谷仓旁边的长栅栏（把栅栏认为是一根一维的线）。他把一只画刷绑在他最喜爱的奶牛Bessie身上，之后就去喝一杯冰水，而Bessie隔着栅栏来回走，当她走过某个地方，这里的一段栅栏就被刷上了涂料。Bessie从栅栏上的位置0开始，并且遵循着一个N次移动的次序(1 = N = 100,000)。例如“10 L”表示Bessie向左移动了10个单位长度，“15 R”表示Bessie向右移动了15个单位长度。现给出Bessie所有移动的列表，Farmer John想要知道哪些区域的栅栏至少涂了两层涂料（只涂一层涂料的区域可能在大雨中被洗掉）。Bessie在她的行走中最远到达距起始点1,000,000,000个单位长度。【输入格式】第1行：一个整型数N。第2 。1+N行：每行描述了Bessie的N次移动中的一次，例如“15 L”。【输出格式】1行：被至少涂了两层涂料的区域总数。【输入样例】62 R6 L1 R8 L1 R2 R输入详情：Bessie从位置0开始，向右移动2个单位长度，向左移动6个单位长度，向右移动1个单位长度，向左移动8个单位长度，最后向右移动3个单位长度。【输出样例】6输出详情：6个单位区域至少被涂了两层涂料，是 -11,-8, -4,-3, 0,2这些区域。来自/index.php/Translate:URAL/1033Liars and Truth Tellers (truth.pas/c/c+)【问题描述】 在花了许多时间陪伴奶牛之后，Farmer John开始理解它们的语言。而且，他注意到在他的N头奶牛中(2 = N = 1000)，一些总是说真话，而一些总是说假话。FJ仔细地听了奶牛们的N段陈述，每段陈述的格式为“x y T”，表示“奶牛x声称奶牛y总说真话”，或者“x y L”，表示“奶牛x声称奶牛y总说假话”。每段陈述包括两头不同的奶牛，相同对的奶牛可以出现在不同的陈述里。不幸的是，FJ相信他可能在他的列表里写了一些不正确的，所以可能没有一个有效的方法去划定每头奶牛是说真话还是假话并且与FJ列表上M条陈述都一致。为了帮助FJ抢救尽可能多的列表，请计算能够以有效方法划定每头奶牛是说真话还是假话的陈述的最大值。输入格式：*第1行：两个空格隔开的整型数，N和M。*第2 。1+M行：每行的格式为“x y L”或者“x y T”，描述奶牛x对奶牛y的陈述。输入样例（文件 truth.in）：4 31 4 L2 3 T4 1 T输入详情：现在有4头奶牛和3段陈述。奶牛1说奶牛4说假话，奶牛2说奶牛3说真话，奶牛4说奶牛1说真话。输出格式：*第1行：能够以有效方法划定每头奶牛是说真话还是假话的陈述的最大值。输出样例（文件 truth.out）：2输出详情：陈述1和陈述3不能同时满足，但是陈述1和陈述2可以，此时我们让奶牛1,2,3说真话，奶牛4说假话。饥饿的奶牛 (hunger.pas/c/c+)【问题描述】 牛在饲料槽前排好了队。饲料槽依次用1到N(1=N=2000)编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。 约翰提供B个区间的清单。一个区间是一对整数start-end,1=start=end=N，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到