haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

NOIP2013普及组模拟试题2

发布时间:2013-10-28 08:03:34  

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

全国信息学奥林匹克联赛(NOIP2013)复赛模拟

普及组

注意事项:

1、文件名(程序名和输入输出文件名)必须使用小写。

2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。

第 1 页 共 6 页

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

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 2

3 0 /

0 2 /

1 2 /

3 2 \

1 3 \

输入详情:

农场的地图如下(H表示Farmer John的房子和B表示谷仓)

3 .\.....

2 //.\..B

1 .......

0 H../...

0123456。

【输入样例】

5 6 2

3 0 /

第 2 页 共 6 页

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

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

第 3 页 共 6 页

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

刷墙

(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行:被至少涂了两层涂料的区域总数。

【输入样例】

6

2 R

6 L 1 R

8 L

1 R

2 R

输入详情:

Bessie从位置0开始,向右移动2个单位长度,向左移动6个单位长度,向右移动1个单位长度,向左移动8个单位长度,最后向右移动3个单位长度。

【输出样例】

6

输出详情:

6个单位区域至少被涂了两层涂料,是 [-11,-8], [-4,-3], [0,2]这些区域。

第 4 页 共 6 页

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

Liars 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 3

1 4 L

2 3 T

4 1 T

输入详情:

现在有4头奶牛和3段陈述。奶牛1说奶牛4说假话,奶牛2说奶牛3说真话,奶牛4说奶牛1说真话。

输出格式:

*第1行:能够以有效方法划定每头奶牛是说真话还是假话的陈述的最大值。

输出样例(文件 truth.out):

2

输出详情:

陈述1和陈述3不能同时满足,但是陈述1和陈述2可以,此时我们让奶牛1,2,3说真话,奶牛4说假话。

第 5 页 共 6 页

全国信息学奥林匹克联赛(NOIP2013)复赛模拟 普及组

饥饿的奶牛

(hunger.pas/c/c++)

【问题描述】

牛在饲料槽前排好了队。饲料槽依次用1到N(1<=N<=2000)编号。每天晚上,一头幸运的牛根据约翰的规则,吃其中一些槽里的饲料。

约翰提供B个区间的清单。一个区间是一对整数start-end,1<=start<=end<=N,表示一些连续的饲料槽,比如1-3,7-8,3-4等等。牛可以任意选择区间,但是牛选择的区间不能有重叠。

当然,牛希望自己能够吃得越多越好。给出一些区间,帮助这只牛找一些区间,使它能吃到最多的东西。

在上面的例子中,1-3和3-4是重叠的;聪明的牛选择{1-3,7-8},这样可以吃到5个槽里的东西。

输入

第一行,整数B(1<=B<=1000)

第2到B+1行,每行两个整数,表示一个区间,较小的端点在前面。

输出

仅一个整数,表示最多能吃到多少个槽里的食物。

样例

HUNGER.IN

3

1 3

7 8

3 4

HUNGER.OUT

5

第 6 页 共 6 页

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com