-
扑克牌
-
description
将 52 张扑克牌洗牌以后，从第一张开始翻，直到出现第一个 A。
问下一张牌是黑桃 A 和是梅花 2 的概率哪个大？ -
solution
可以考虑枚举所有情况，发现概率是相同的。
-
-
删树
-
description
n 个点的有根树。
每次操作，随机选择一个结点，把以它为根的整个子树删去。
一直到删完为止。
问操作次数的期望。 -
solution
考虑每个节点对答案的贡献，即每个节点出现在操作序列中的概率( imes 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(nsqrt{n}))
-
-
骑士
-
description
(n) 个点的无根树，每个点上有一些权值。
(q) 次询问。要么修改某个权值 (x_i)，要么将某个权值移动到另一个点上，要么询问一条路径上最大的 (k) 个权值。
(n, m leqslant 4 imes 10^4, q leqslant 10^5, k leqslant 20, x_i leqslant 10^3). -
solution
用括号序列维护到跟路径，用树状数组（权值）套线段树（括号序列）维护信息，每次在树状数组上问第k大。
时间复杂度(O(qlog{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
-
招聘
-
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 eq j) 有 (a_imod m eq a_jmod 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
-
方程
- description
n 元不定方程 x1 + x2 +… + xn = m.
xi 均为整数，且 li <= xi <= ri。
问有多少组可行解？（模 109+7） - solution
容斥+隔板法
- description
-
狐狸(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))的
-