2-sat原题。
50pts直接拆点n^2暴力建边。
考虑优化边数,前缀关系可以体现在trie树的祖先关系上,开点表示是否前缀被选,子树同理。
题意:给定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还是不够快。
题意: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/2f[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\)
原文:https://www.cnblogs.com/hzoi-yzh/p/12266888.html