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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

20090716做的题  

2009-07-16 14:28:43|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天是杨弋大牛出的题

平面上有一些炸弹。每个炸弹有四个属性:中心横坐标Xi,中心纵坐标Yi,半径Ri,爆炸范围Ei。如果炸弹i爆炸了,且炸弹i和炸弹j的中心的距离不超过Ri+Ei+Rj,那么炸弹j就会被引爆。你现在可以手工引爆炸弹,手工引爆炸弹的费用就是它的爆炸范围Ei

 

现在让你设计一个引爆炸弹的序列,要求:

1. 所有炸弹最终都被引爆。

2. 一个炸弹在爆炸后,不管是被你引爆还是被其他炸弹引爆,你就不能再次去引爆它。

3. 你的方案的平均花费(即总手工引爆的费用除以手工引爆的炸弹数)应该尽量小。

 

【输入格式】

第一行一个N,接下来有N组数据。

每组数据第一行有一个n是炸弹个数,后面有n行,第i行是Xi,Yi,Ri,Ei。每组数据之后有一个空行。

 

【输出格式】

每组数据输出一行,即引爆炸弹的序列,用空格隔开。炸弹的编号是从0n-1的。如果有多解,你可以任选一个输出。

 

【输入样例】

1

3

4 7 2 2

8 5 1 0

3 -3 1 1

 

【输出样例】

1 0 2

 

【数据范围】

20%的数据n不超过10

100%的数据N不超过100n不超过300

 

【注】

数据除了RE都是非负以外不保证其他性质,输入数据规模不大,用int读绰绰有余。



欧拉函数定义为不超过n的与n互质的正整数的个数。如果n可以写成,其中为各不相同的素数,那么就可以被写成

 

    

现在你的任务是对于给定的x,求出所有满足n

 

【输入格式】

输入文件包含若干行,每行有一个数字即x

 

【输出格式】

对于输入中的每一行:如果不存在这样的n,输出一行“No solution.”(不包含双引号)。

如果存在这样的n,请依升序输出这些n,相邻的两个值之间有恰好一个空格。

 

【输入样例】

1

3

6

 

【输出样例】

1 2

No solution.

7 9 14 18

 

【数据范围】

40%的数据满足n不超过105

100%的数据满足n不超过109



输入一个N,让你在N*N的网格里(左下角是(0,0),右上角是(N,N))通过连结线段来作一个凸多边形。所有线段的端点坐标都是整数,这个凸多边形必须在旋转90度后与自己重合。在满足上面条件的基础上,希望你输出的凸多边形的边越多越好。

 

输入格式:

一个整数N

 

输出格式:

以逆时针顺序输出这个凸多边形的顶点,每行一个,格式为“x,y”。

 

样例输入1

1

 

样例输出1

0,0

1,0

1,1

0,1

 

样例输入2

3

 

样例输出2

1,0

2,0

3,1

3,2

2,3

1,3

0,2

0,1

 

数据范围:

 

40%的数据中N不超过100

所有数据中N不超过100000




2N个球队,每个球队有个实力值s(x)。对于两支球队AB,在他们之间举行一场比赛(因为是淘汰赛所以没有平局),则AB的概率为s(A)/(s(A)+s(B))。一场淘汰赛的安排方案可以用一个长度为2N的数字串表示,那么第一轮比赛过程将是这个串的第一个队和第二个队之间的比赛,第三个队和第四个队之间的比赛,等等;第二轮比赛将是前两个队的胜者对第三第四个队的胜者,第五第六个队的胜者对第七第八个队的胜者;以此类推;决赛将在前2N-1个队的胜者和后2N-1个队的胜者之间展开。你的球队是第k支球队,你希望它能有尽量大的概率获得第一。对于获得第一的概率相同的方案,你应该输出字典序最小的方案。

 

注:字典序最小的方案指的是,方案的数字串的第一个数尽量小;第一个数相同的情况下第二个数尽量小;以此类推。

 

【输入格式】

第一行一个正整数N,不超过7

第二行一个正整数K,不超过2N

接下来一行有2N个数,第i个数表示s(i)

 

【输出格式】

一共2N个数,为1~2N的一个排列,即比赛的安排。输出的两个数字之间应恰好有一个空格隔开。

 

【输入样例】

3
5
8 9 8 9 7 8 9 8

 

【输出样例】

1 2 4 7 3 5 6 8
 

【输入样例2

2
1
7 3 1 9

 

【输出样例2

1 3 2 4

一共骗来了80分......

我的笔记:

笔记

1.wheelgood

枚举线段,斜率排序。

2.bomb

缩圈(强连通分量-》点)

入度为0:必须干掉
二分
拓扑排序

3.etf

想法1
for (a,b)=1
Euler(ab)=Euler(a)*Euler(b)
想法2
Euler(x)<x<=2*Euler(x)
想法3
枚举最小质数
AC!

4.worldcup

贪心,用子树比较来找字典序


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

历史上的今天

评论

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

页脚

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