1
给定一个带权有向无环图，\(Q\) 次询问，每次询问删掉某个点后 \(1\) 到 \(n\) 的最短路
sol：
求拓扑序后优先队列维护
2
给定 \(a[1…n]\)，求有几个区间 \([L,R]\) 满足 \(a[L] or a[L+1]…or a[R] > max(a[L…R])\) \(N<=3*10^5\)，\(a[i]<2^30\)
sol：
分治，每一层暴力枚举\(30\)个不同情况
3
给定 \(n\) 个点，第 \(i\) 个点的点权是 \(a[1…n]\)，现在定义边 \((i,j)\) 的权值是 \(a[i] xor a[j]\)，求最小 \(xor\) 生成树
sol：
分成最高为为0和1两个集合分别在内部连边（分治），最后在两个集合间连一条边（trie）
4
求所有区间的 gcd 之和
sol：
for R=1 to N
stack[R]=stack[R+1]
stack[R].push{seg(R,R,a[R])}
for x in stack[R]
x.w=gcd(x.w,a[R])
stack[R]中w相同的合并 5
缺 \(1\) 背包问题：给定 \(n\) 个物品的重量 \(W[i]\) 和价值 \(V[i]\)，\(Q\)次询问，每次询问对除了第 \(i\) 个物品以外的物品 \(01\) 背包后重量不超 过 S 的最大价值 \(n,W,V<=2000\)，\(Q<=1000000\)
sol：
\(CDQ\)分治了解......
6
给出一棵树，其中每条边的长度有 \(0.5\) 的概率是 \(1\)，\(0.5\)的概率是 \(0\)，求直径的期望 \(1\leq n\leq 200\)
sol：
设\(g(x)\)表示直径\(=x\)的概率，\(f(x)\)表示直径小于等于\(x\)的概率
枚举\(x\)，\(dp(i,j)\)表示已做到\(i\)点，向下最大深度为\(j\)的概率
如果最大深度已经超过当前的\(x\)，则直接丢掉，否则按直径方法更新答案
复杂度\(O(n^3)\)
7
有 \(n\) 个球，一开始颜色是 \(c[1…n]\)，每次随机选一对数 \((i,j)\) 然后 \(c[j]=c[i]\)，求让 \(c\) 全部相同的期望步数 \(1\leq n\leq 1000000\)
8
给定一个长度为 \(n\) 的 \(01\) 串，每次随机一个区间将里面所有元素翻转，求 \(m\) 次操作后 \(1\) 的期望个数 \(n\leq 100000\)，\(m\leq 10^9\)
9
一个游戏有 \(n\) 个人，规则是这样的：
(1)随机选择一个还没死的人，让他活着离开
(2)活着离开之前，他会向剩下所有人开一枪，有 \(p\) 的概率致死
重复以上步骤直到所有人要么死了要么离开了
求一个人活着离开且一共被开了 \(k\) 枪的概率 \(1\leq n\leq 2000\)
sol：
\(dp(i,j)\)表示考虑了i个人，已走了\(j\)个人（即已开了j枪）的概率
\(dp(i,j)=dp(i-1,j-1)\times (1-(1-p)^{(j-1)})+dp(i-1,j)\times (1-p)^j\)
10
有 \(n\) 堆石头，第 \(i\) 堆个数为 \(a[i]\)，每次随机选一个石头然后把那一整堆都扔了，求第 \(1\) 堆石头期望第几次被扔
第一堆石头期望第几次被扔即第一堆石头排名为i的概率\(\times i\)
11
LOJ PKUWC2018 随机游走
12
BZOJ2169 连边