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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

第4天的题  

2010-07-23 22:01:12|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOI2010模拟题

题目名称

选举

三角形

领土划分

英文代号

Izbori

Tri

Division

可执行文件名

Izbori.exe

Tri.exe

Division.exe

输入文件名

Izbori.in

Tri.in

Division.in

输出文件名

Izbori.out

Tri.out

Division.out

单个测试点时限

1s

3s

1s

空间限制

256MB

256MB

256MB

测试点个数

10

10

10

单个测试点分值

10

10

10

附加文件

题目类型

传统

传统

传统

是否有部分分

                                                    Source By  Jby

第一题 选举(Izbori)

(Izbori.pas\c\cpp)

题目描述:

有N个政党(从1到N编号)通过选举竞争M个议会席位,总共有V张选票,每张选票都会投给某个政党。假设投票完后第I个政党有VI张票,那么席位将由下面的方式分配:

1. 得票严格小于总票数5%的政党直接被排除在议会之外(不会得到任何席位)。

2. 设第I个政党的当前席位数为SI,开始时每个政党都没有任何席位。即SI=0

3. 对于每个政党,计算其当前的优先级QI=VI/(SI+1)。

4. 优先级最大的政党得到一个席位,如果有多个优先级最大的政党,则编号小的政党得到席位。

5. 将3,4的步骤重复M次即可得到最终的议会选举结果。

现在选举正在进行中,已经统计出了一部分选票。而你的任务是:

对于每个政党,算出其最终可能获得席位数的最大值和最小值。

输入文件(Izbori.in):

第一行3个正整数V,N,M,即总选票数,政党数和席位数。(1<=V<=10000000;1<=N<=100,1<=M<=200)

第二行N个非负整数,第I个数表示标号为I的政党当前获得的选票。这N个数的和不会超过V。

输出文件(Izbori.out):

两行。

第一行N个数,第I个数表示标号为I的政党的最大席位数。

第二行N个数,第I个数表示标号为I的政党的最小席位数。

数字之间用空格隔开。

输入样例1:

20 4 5

4 3 6 1

输出样例1:

3 3 3 2

1 0 1 0

输入样例2:

100 3 5

30 20 10

输出样例2:

4 3 3

1 1 0

数据规模

对于10%的数据,M<=2

对于另外20%的数据,N<=15

对于100%的数据如题目。

第二题  三角形(Tri)

Tri.pas\c\cpp)

题目描述:

在一个平面上,给你N个坐标为正的点,以及M个以原点为顶点的三角形,每个三角形的另外两个顶点都在第一象限内。

现在需要你回答每个三角形内部是否有点(点指的是给出的N个点,不包括三角形顶点)。

输入文件(Tri.in):

第一行两个正整数N,M(N,M<=100000)

下面N行,每行两个正整数X,Y。描述了给出点的坐标(1<=X,Y<=10^9)

再下面M行,每行两对整数X1,Y1,X2,Y2。表示三角形另外两个点的坐标。

(0<=X1,Y1,X2,Y2<=10^9)

数据保证这N个点都不会在三角形的边上

输出文件(Tri.out):

M行,每行一个YN,第I行表示第I个三角形内部有没有点。

输入样例1:

4 3

1 2

1 3

5 1

5 3

1 4 3 3 

2 2 4 1

4 4 6 3

输出样例1:

Y

N

Y

输入样例2

4 2

1 2

1 3

5 1

4 3

0 2 1 0

0 3 5 0 

输出样例2:

N

Y

样例1解释:

样例2解释:

  

数据规模:

20%的数据N,M<=1000。

50%的数据满足所有三角形的两边贴着坐标轴,即X1=0且Y2=0,也即样例2所示

100%的数据如题目。

第三题  领土划分 (Division)

(Division.pas\c\cpp)

题目描述:

有一个国家有N个城市,城市间有M条双向道路连接,很和谐的是:N一定为偶数。每对城市间最多只有一条直接相连的道路,且每对城市都可以间接地通过道路互达,也没有指向自己的道路。

现在这个国家发生了分裂,分裂后人们希望把国家分成若干个小国家,每个小国家由若干个城市组成,且需要满足以下条件:

1. 每个城市属于一个新的国家。

2. 每个新国家至少拥有两个城市。

3. 在每个国家的内部(只经过自己的城市),城市间必须两两能互达,且任意一对城市间只能有一条可行的路径。(i.e新国家的城市构成的子图是一棵树)

现在这个国家的人民希望能找出一种划分方案,这个任务就交给你了。同时他们

还告诉你他们并不在乎最终有多少个新国家。

输入文件(Division.in):

本题有多组数据,输入数据的第一行是一个正整数T(T<=10),表示数据组数。对于每组数据,第一行两个正整数N,M(N<=2000,M<=20000,N为偶数),下面M行,每行一对正整数X,Y1<=X,Y<=N)描述了一条无向边。

输出文件(Division.out):

对于每组数据,如果不能满足他们的要求,则输出一行NO,否则先输出一行YES,接着一行输出任意一个方案。假设你最终的方案中有k个新国家,则输出N个用空格分开的正整数,第i个数表示第i个城市属于哪个新国家,国家的编号由1~k

输入样例:

2

4 3

1 2

2 3

1 4

4 4

1 2

2 3

1 4 

1 3

输出样例:

YES

1 1 1 1

YES

1 2 2 1

数据规模:

20%的数据N<=15

40%的数据N<=50且只有一组数据

60%的数据N<=100


第1题:

求最大值:简单模拟

求最小值:2分+dp


第2题:

先极角排序,再用线段树维护一个极角区间内的点的下凸线,

最后对每条边扫描/二分均可


第3题:

永远不可能输出no

简单证明:如果当前图有割点,分治即可;否则,随便删一对点。

具体方法:生成一个dfs树,之后从叶子到根递归处理。


恶搞方法:试图把dfs树中每个节点和他的孩子凑成新国家。可以证明除了根,所有的节点都必定有归属。

如果根没有归属,那么随机换一个根重新dfs

  评论这张
 
阅读(741)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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