- 扑克牌
description
将 52 张扑克牌洗牌以后，从第一张开始翻，直到出现第一个 A。 问下一张牌是黑桃 A 和是梅花 2 的概率哪个大？solution
可以考虑枚举所有情况，发现概率是相同的。
- 删树
description
n 个点的有根树。 每次操作，随机选择一个结点，把以它为根的整个子树删去。 一直到删完为止。 问操作次数的期望。solution
考虑每个节点对答案的贡献，即每个节点出现在操作序列中的概率\(\times 1\)。 而概率恰是它的深度，即最后的答案是\(\sum{depth_u}\)
- 开关灯
description
n 个灯的开关排成一排。最初，所有灯是关的。 每次操作，随机选择一个至少两个开关的区间 \([l, r]\)，改变区间中所有灯的开关状态（选择任何区间的概率等于 \(\frac{1}{C_n^2}\)）。 问 m 次操作以后亮着的灯的数目的期望。\(n \leqslant 10^3, m \leqslant 10^9\).solution
考虑每盏灯对答案的贡献，每盏灯\(i\)一次操作后改变状态的概率\(p\)很容易计算，然后可以得到一个递推式，可以用矩阵快速幂计算。
- 石头剪刀布
description
n 个人玩石头剪刀布。 每个人每个回合随机出招。若一个回合能分成胜负两方则分开，分开后两方各自继续游戏。直到分成 n 个人时游戏结束。 求期望的游戏回合总数。solution
用\(f(n)\)表示\(n\)个人的期望次数，\(f(n)=\sum_{i=0}^{n/2}f(i)f(n-i)p(n,i),p(n,i) = C_n^iC_3^2(0 < i < n)\)
- 迷宫
description
n 个点、m 条边的无向图，点 1 为迷宫出口。 你随机出生在某个点。每次操作，可以移动到一个相邻的结点，也可以选择随机传送到某一个结点（有可能仍在原先结点）。 问最优策略下到达出口步数的数学期望。solution
有一些点的最优策略是直接走最短路，那么我们从点1开始bfs，并记录已经到达了c个点，那当前这个点考虑使用传送的期望步数是\(\frac{n}{c}ave\)
- 三角形
description
平面上有 n 个点，问有多少个三元组组成： Q1. 直角边平行于坐标轴的等腰直角三角形； Q2. 斜边平行于坐标轴的等腰直角三角形。\(n \leqslant 10^5\).solution
可以通过坐标轴转化将两个问题用同样的方式处理。 按大小分治，时间复杂度\(O(n\sqrt{n})\)
- 骑士
description
\(n\) 个点的无根树，每个点上有一些权值。\(q\) 次询问。要么修改某个权值 \(x_i\)，要么将某个权值移动到另一个点上，要么询问一条路径上最大的 \(k\) 个权值。\(n, m \leqslant 4\times 10^4, q \leqslant 10^5, k \leqslant 20, x_i \leqslant 10^3\).solution
用括号序列维护到跟路径，用树状数组（权值）套线段树（括号序列）维护信息，每次在树状数组上问第k大。 时间复杂度\(O(q\log{n}\log{maxw})\)，不知为啥貌似比3个\(\log\)的还慢？
- 路径
description
n 行 m 列的地图，每个格子上有个 0..20 之间的整数。 每个格子与上下左右四连通。 问有多少条恰好 21 个格子的路径，使得 0..20 在路径上分别出现一次。 n, m <= 21.solution
meet in the middle
- 传单
- description P 校有 n 个新生，学号为 1 ~ n。以及 m 个社团。 社团活动日，第 i 个社团会给学号为 ai, ai + ci, ai + ci * 2, …, ai + ci * ki 的新生发传单。 已知恰好有一个学生收到的传单数为奇数。请问是谁？\(n, m \leqslant 10^6\)
- solution 二分答案
- 招聘
description
公司的 A 部门招聘 n1 人，B 部门招聘 n2 人。 n 个人来应聘。经过面试，对每个人有四个评估分数：q1, q2, c1, c2。 你要决定录取哪 n1+n2 个人以及分到哪个部门，使得 (∑q1 + ∑q2) / (∑c1 + ∑c2) 尽量大。 即分到 A 部门的 n1 个人的q1 之和加上分到 B 部门的 q2 之和，除以对应的 c1、c2 之和最大。 1 <= n1+n2 <= n <= 500, 1 <= c1, c2 <= 50，1 <= q1, q2 <= 2000.solution
分数规划之后费用流或dp即可。
-
description
n 个数 a1, a2, ..., an. 你可以删去其中的至多 k 个数。 求最小的正整数 m，使得存在一种删数的方法，在删数过后，对任意的 \(i \neq j\) 有 \(a_i\mod m \neq a_j\mod m\).\(n \leqslant 5000，k \leqslant 4，0 \leqslant a_i \leqslant 10^6\).solution
枚举\(m\)时，判断一下模\(m\)为\(0\)的数对是否超过\(\frac{k(k+1)}{2}\)，超过则一定无解。
- 统计
- description n 个数 a1, a2, …, an。 问有多少个三元组 (i, j, k)，满足 1 <= i < j < k <= n 且 ai < ak < aj。\(n \leqslant 10^5\).
- solution 枚举最高点（下标位于中间的点），那么只用考虑所有比他小的点，对于每一对ai < aj，在i的地方+1，j的地方-1，对于枚举到的最高点，问下前缀和即可。 具体操作可以用线段树实现。
- 方程
- description n 元不定方程 x1 + x2 +… + xn = m. xi 均为整数，且 li <= xi <= ri。 问有多少组可行解？（模 109+7）
- solution 容斥+隔板法
- 狐狸(SRM 498 Div1.)
description
有只狐狸在坐标 (0, 0) ，必须跳恰好 r 步到坐标 (tx, ty)。 设一步从 (x, y) 跳到 (x+dx, y+dy)，则须满足 0 <= dx <= mx，0 <= dy <= my，且 dx, dy 不能同时为 0。 此外，存在若干个数 bad[1..n]，每次跳时 dx 和 dy 不能同时等于任意一个 bad[i]。 问方案数，模10,007。 n <= 50，tx, ty, mx,my, bad[i] <= 800，r <= 1600.solution
行列分开考虑，然后按至少i步走了bad进行容斥，复杂度就是\(O(r)\)的而不是\(O(2^n)\)的