3028 Shoot-out
一群牛仔,依次射击,每人有固定命中率
轮到某人射击时他会选一个人去射,要使如果命中的话,自己有最大的胜利几率,如果有多个满足条件的,就随机选择
每个人都知道别人的命中率以及策略,并且不能故意不打中
求每人的胜利几率(最后活下来的)
人数<=13
一个状态压缩dp,优化再优化
一开始我以为只要选择命中率最高的人去射就行了,找到了数据后才发现我原来想错了…
其实是每人准备射击时,会先计算一下如果命中某个人,自己的存活概率是多少,选择最大的那个作为目标,当然如果有相同的就在此之中随机选择
这样一来,寻找目标时还要计算一次存活率…这样复杂度就上去了…
看了标程的方法后,自己写了一个…
dp[state][shooter][i]=在活下来的人为state时,轮到shooter射击,第i人存活可能性
先计算shooter的目标,就是找到使得 { dp[state^j][(shooter+1)%n][shooter] , j在state中 } 最大的i
然后计算在一圈内的存活概率:
sum{ dp[state^j][(shooter_now+1)%n][i] / target_count * accuracy[shooter_now] * multiply{ 1-accuracy[k] , k在shooter_now之前的人 } , j是shooter_now的目标 , shooter_now从shooter到一圈结束 }
至于会有环,则是在这个一圈的基础上除以(1-所有人都没有命中的概率),这个结果就是dp[state][shooter][i]
直接这样做的话还是会超时
于是在计算dp[state][shooter][i]的时候顺便把其他shooter的情况一起填了
这样才终于过了
下面是代码:
16860K,2000MS,1865B
tags: PKU, acm author: ben1222 comments: No Comments
军训提前结束了…因为流感暴发…几百人倒下了…我也是其中一个…
高烧39度以上…现在已经好的差不多了…
话说我发烧那天正好是pku月赛…
看到某人说B很简单,后来他又总超时过不了…于是来做了下这道题…
顺便说下,pku上消失了一道题,题号是3698,因为我写的一个pku上拉下每个volume页面里的数据的程序在vol27就停住了…然后answer发现少了这题…
说了这么多无关的…下面开始正文
3741 Number System Converter
题意是有两个进制转换器,其中P可以把数字当作P进制转换成10进制,不过不会检查输入数据的有效性,另一个是Q,可以把10进制数转换成Q进制
给定初始值N0,依次进入P,Q,P,Q,…如此循环,直到最后这两者输出的都是相同的数字…
1<P<Q<37
N0不超过5,000,000位
其实中间不应该是10进制,而是大于等于Q的进制,否则不会一定有解了…
因为十进制比较好理解,所以用十进制当作中间量了吧…
可以改一下描述,变成一个转换器,是把P进制转换成Q进制,然后不断自己输出给自己输入直到数字不变
不过还是采用原先的描述吧,无视那个恶心的地方…
当测试了几组小数据后可以发现一个规律…虽然没有证明…
考察做了第一步转换后得到的数字N1
我把N1当作起点,因为十进制比较好处理
让N1按递增顺序给出[1,2,3,...],可以看到答案是一个[1,...,P,...,Q-1,P,...,Q-1,P,...]
后半部分就一直循环下去,类似无限循环小数的样子
于是就好办了,先把输入数据转换成十进制数,再对循环节取余得到正确的数字
不过位数太长的话会很慢,所以只对<P的数进行转换,大的数直接做转换后的取余值,这样就不需要高精度作为中间变量了
下面是我的代码:
tags: PKU, acm author: ben1222 comments: 1 Comment
1259 The Picnic
一些点,二维的,要画一个凸多边形,顶点在这些点上,多边形内不能有别的点,求满足这条件的最大凸多边形面积
求最大凸洞
话说凸洞这词是谁发明的?我是从zy那听来的
dp,枚举凸洞最下的点,然后dp[最后点][倒数第二点]=最大值
直接做要O(n^4),可以优化
O(n^3)的做法可以参考这里
这可以做一个模板…不过这种模板估计很少会用到吧…
感觉这篇没什么含金量…
下面是我的代码:(借鉴了上面那个网址里的方法)
tags: PKU, acm, 模板 author: ben1222 comments: No Comments
1986 Distance Queries
描述部分和1984 Navigation Nightmare一样
要求变成了树上两节点间的距离
经典的LCA问题…
又是一个可以用来做模板的题目…lca/rmq的模板
话说这篇是不是有点水…就好象为了贴代码和说一声模板的事而发的…
或许是为了上面那个链接?
下面是我的代码:
tags: PKU, acm, 模板 author: ben1222 comments: 1 Comment
1984 Navigation Nightmare
有很多农场,一些农场之间有路相连,每个农场最多东西南北四个方向有路
路都是笔直的,路的两端总有2个农场
现在有一列数据,每个数据描述一条路的信息
在绘制地图的过程中,还有询问,每次询问两个农场间的曼哈顿距离
如果询问时信息还不够回答,则回答不知道
农场<=40000,路<=40000,询问<=10000
乍看之下感觉有点复杂…
稍微想想就不觉得了…
因为只要求曼哈顿距离…只要固定一个原点,然后用相对的关系算出各自的坐标就能直接回答了
不过这必须等整个地图都画完时才能确定所有点的坐标
而询问时不一定所有信息都有了…因此坐标还没法建立
再想想就不难发现…只要知道当时那两点是否已经连通了就能判断是否回答不知道了…
于是并查集就派上用场了
下面是我的代码:
tags: PKU, acm author: ben1222 comments: No Comments
1981 Circle and Points
用单位圆包住最多的点
点数<=300
说到计算几何,模板是最多的了
这是一道可以制作和改进模板的题
模板内容是:求过两点的直径为给定值的圆
我手算了个公式…好累…不过还是没能避免开平方…
这道题O(n^3)能过,枚举2点和扫一遍所有点
不过貌似有更好的方法?没想出来
下面是我的代码:
tags: PKU, acm, 模板 author: ben1222 comments: No Comments