首页 > 其他 > 详细

省选模拟18

时间:2020-02-05 23:52:41      阅读:115      评论:0      收藏:0      [点我收藏+]

A.编码

2-sat原题。
50pts直接拆点n^2暴力建边。
考虑优化边数,前缀关系可以体现在trie树的祖先关系上,开点表示是否前缀被选,子树同理。

B.哈密顿回路

题意:给定n个点的完全图,判断是否存在长度为L的哈密顿回路(经过n个点恰好一次)。n<=14
Meet In The Middle,前后暴力搜n/2,复杂度n的下降n/2次幂。
由于必定过1,所以从1搜即可。
hash表mp[i][s]存结尾为i点集为s的长度集合。
最后扫一遍,开互补集合是否存在即可。
卡常,必须手写hash表。事实证明开了O2的unordered_map还是不够快。

D.猎人杀

题意:n个猎人,一开始向(k-1)%n+1个猎人开枪,猎人有1/2的概率死亡,无论存亡都会逆时针数k个人后开枪,求1号猎人胜利概率。n<=2000
类似约瑟夫问题的套路,倒序dp
为了方便编号-1
设f[i][j]为剩i个人第j个人中枪的概率。
那么f[1][0]=1,目标是f[n][(k-1)%n]
转移考虑第j个人存亡
f[i][j]=1/2(f[i-1][j+k-1]+f[i][j+k]) j!=0
f[i][j]=1/2
f[i][j+k] j=0
转移出环,60~80pts高斯消元。
正解系数递推,适用于解这种简单环,之前做过题。
f[k]=a[k]f[m]+b[k]
f[k]=q*f[k-1]+p
f[k-1]=a[k-1]f[m]+b[k-1]
q p是已知的,所以联立可以解出a[]b[]各自的递推关系。
复杂度\(n^2\)

省选模拟18

原文:https://www.cnblogs.com/hzoi-yzh/p/12266888.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!