注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

第3天的题  

2010-07-22 14:04:26|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOI2010模拟题

题目名称

最优切割

企鹅岛屿

生成树

英文代号

Cut

Otoci

Mst

可执行文件名

Cut.exe

Otoci.exe

Mst.exe

输入文件名

Cut.in

Otoci.in

Mst.in

输出文件名

Cut.out

Otoci.out

Mst.out

单个测试点时限

1s

4s

1s

空间限制

256MB

256MB

256MB

测试点个数

10

10

10

单个测试点分值

10

10

10

附加文件

题目类型

传统

传统

传统

是否有部分分

                                                    Source By  Jby

 

 

 

 

 

 

 

 

 

 

 

 

 

 

     声明:第二题必须使用在线算法~避免麻烦所以测试时采用离线的输入输出方式测试。但要求实际代码必须是在线的。

                                          

第一题 最优切割(Cut)             

Cut.pas\c\cpp

题目描述:

HURRICANE小组的成员最近去工厂实习,在实习的过程中遇到了这样的一个问题。即要在一个模板内,切割出一个零件。现已知模板和零件都是给定的凸多边形,且零件在模板中的位置已经固定。我们知道,对于零件来说,除相邻的两边外,任何两条边的延长线的交点都在模板之外。

由于工厂的加工条件所限,切割时,每一刀必须沿零件的某一条边所在的直线切下,把模板分成两部分,然后保留含有零件的一部分,再继续切割。现定义每一刀的费用为模板上切痕的长度。问如何选择切割顺序,才能使花费最少?

你的程序需要根据给定的输入,给出符合题意的输出:

l  输入包括模板及零件的形状和坐标;

l  你需要根据给出的输入,计算出把模板切割成为零件的最少花费;

l  输出中只包括一个数,即最少的花费。

 

输入文件(Cut.in)

输入文件包括两个部分,分别描述模板和零件的形状及坐标:

l  第一行为模板的顶点个数n3≤ n≤ 2000)。下面的n行每行两个实数xy-1,000,000<x, y<1,000,000),为按逆时针方向给出模板顶点的坐标。

l  n+2行为零件的顶点个数m3≤ m≤ 2000)。下面的m行每行两个实数xy-1,000,000<x, y<1,000,000)为按逆时针方向给出的零件顶点的坐标。

 

输出文件(Cut.out)

输出文件中只需要包括一个整数,为最少花费四舍五入到整数后的值。

   

输入样例1

4

0 0

0 3

3 3

3 0

4

1 1

1 2

2 2

2 1

 

输出样例1

8

 

输入样例2

4

0 0

3 0

3 3

0 3

4

0 0

2 0

2 3

0 3

 

 

输出样例2

3

 

数据规模

对于30%的数据,1<=N<=300

对于100%的数据如题目

                                                   

第二题  企鹅岛屿(                 )

Otoci.pas\c\cpp                    

题目描述:

某人(据说叫Mirko)在南极开了一家公园,专门让游人去观看企鹅。企鹅都是住在岛屿上的,最开始时有N个岛屿(1N编号),而且都是不相连的(没船坐)。后来Mirko在开始岛屿间修建一些桥梁,以方便游人通行,但由于岛屿太多,以至于他自己往往会忘记岛屿间当前的联通性,所以只好请你帮忙。另一方面,岛屿上的企鹅会由于生病、生小企鹅等各种情况而导致数量的改变。因此你需要解决下面的操作:

1.                bridge A B 表示现在尝试在岛屿A,B间修建一条桥。如果A,B之前不连通则修建并输出yes,否则忽略此次操作并输出no(注意你不需要考虑实际岛屿间的平面图是怎样,桥一定可以被修建)

2.                penguins A X  表示岛屿A上的企鹅数变成了X

3.                excursion A B  表示现在有游人从岛屿A走向岛屿B,需要你回答A,B是否联通,如果能,输出从A走到B的路径上经过岛屿的企鹅总数是多少(包括A,B);否则输出impossible

注意你的程序必须支持在线操作,即对于每个bridge,excursion操作,你必须先回答才能得到下一条操作。

 

输入文件(Otoci.in)

第一行一个N,表示有N个岛屿。(1<=N<=30000)

第二行N个数,表示开始时每个岛屿上的企鹅数。

第三行一个Q,表示操作数。(1<=Q<=300000)

下面Q行,每行一个操作。

注意任意时候任意岛屿上的企鹅数是一个不超过1000的非负整数。

 

输出文件(Otoci.out)

若干行,对于每个bridge,excursion操作,输出其结果。

 

输入样例1               

5

4 2 4 5 6

10

excursion 1 1

excursion 1 2

bridge 1 2

excursion 1 2

bridge 3 4

bridge 3 5

excursion 4 5

bridge 1 3

excursion 2 4

excursion 2 5

 

输出样例1

4

impossible

yes

6

yes

yes

15

yes

15

16

 

输入样例2

6

1 2 3 4 5 6

10

bridge 1 2

bridge 2 3

bridge 4 5

excursion 1 3

excursion 1 5

bridge 3 4

excursion 1 5

penguins 3 10

excursion 1 3

bridge 1 5

 

输出样例2

yes

yes

yes

6

impossible

yes

15

13

no

 

 

数据规模:

20%的数据N<=50,Q<=500

50%的数据没有penguins操作

100%的数据如题目。

 

第三题  生成树(Mst

Mst.pas\c\cpp

题目描述:

给出一个N个点M条边的无向带权图,以及Q个询问,每次询问在图中删掉一条边后图的最小生成树。(各询问间独立,每次询问不对之后的询问产生影响,即被删掉的边在下一条询问中依然存在)

 

输入文件(Mst.in)

第一行两个正整数N,M(N<=50000,M<=100000)表示原图的顶点数和边数。

下面M行,每行三个整数X,Y,W描述了图的一条边(X,Y),其边权为W。保证两点之间至多只有一条边。

接着一行一个正整数Q,表示询问数。(1<=Q<=100000)

下面Q行,每行一个询问,询问中包含一个正整数T,表示把编号为T的边删掉(边从1M按输入顺序编号)

 

输出文件(Mst.out)

Q行,对于每个询问输出对应最小生成树的边权和的值,如果图不连通则输出Not connected

 

输入样例:                 

4 4

1 2 3

1 3 5

2 3 9

2 4 1

4

1

2

3

4

 

输出样例:

15

13

9

Not connected

 

数据规模:

10%的数据N,M,Q<=100

另外30%的数据,N<=1000

100%的数据如题目。

  评论这张
 
阅读(574)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017