分类: 题解

58 篇文章

P7474 -「C.E.L.U-02」学术精神
对于每个点 $i$ 随机与 $[1, n]$ 中的一点连无向边,若连向自己,则保留该边并再次连边,一直重复至连到别的点上为止,求边数与连通块个数期望。
Luogu – P7568 -「MCOI-05」追杀
有 $m$ 位玩家 $1\sim m$,初始血量均为 $3$。玩家活着当且仅当生命值大于 $0$.
有 $n$ 次按时间顺序给定的追杀操作,每次形如 $(u_k,v_k)$,追杀操作按顺序进行。
执行操作 $u$ 追杀 $v$ 时,若二者都活着,那么 $v$ 的生命值减 $1$;否则不执行该操作。
现在有一名特殊玩家 $0$ 号,可以选取任意 $(i,v)$,其中 $1\leq i\leq n+1$,$1\leq v\leq m$,表示时空穿越到第 $i$ 次追杀前,并追杀玩家 $v$。
显然 $(i,v)$ 共有 $(n+1)\times m$ 个不同的选择方法,且不同的 $(i,v)$ 会导致最终存活玩家的集合不同。
对每个 $0\leq x\leq m$,求有多少种 $(i,v)$ 的选取方法,使最终恰有 $x$ 位玩家存活,输出 $m+1$ 个数。
Luogu – P7287 -「EZEC-5」魔法
给定数列 $a_1, a_2, \cdots, a_n$,可以对其进行下列操作。
  1. 花费 $a$ 魔法值,选择 $A$ 中的一个区间 $[l,r]$,将 $a_l, a_{l+1},\cdots, a_r$ 全部 $+1$.
  2. 花费 $b$ 魔法值,选择 $A$ 中的一个区间 $[l,r]$,将 $a_l, a_{l+1},\cdots, a_r$ 全部 $\times 2$.
现在可以做若干次操作,使得序列 $a$ 存在一个子区间,其元素之和不小于 $s$.
求需要花费的最小魔法值。
Luogu – P1450 – [HAOI2008]硬币购物
共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。
某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚第 $i$ 种硬币,想购买价值恰好为 $s$ 的东西。
多次询问,每次询问形如 $(d_1,d_2,d_3,d_4,s)$,求付款方法数。
$1\leq c_i,d_i,s\leq 10^5$,$1\leq n\leq 1000$.
CodeForces – 1623D – Robot Cleaner Revisit
地板有 $n$ 行 $m$ 列,一个机器人被安置在坐标 $(r_b, c_b)$,还有一个障碍位于 $(r_d, c_d)$。
每过一秒,机器人的坐标会 $(r, c)\rightarrow (r+d_r, c+d_c)$。
初始时 $d_r=d_c=1$,当机器人到达边界后,$d_r,d_c$ 会变化:
  • 若机器人碰到上/下边界($r=1$ 或 $r=n$),下一秒 $d_r\leftarrow -d_r$,
  • 若机器人到达左/右边界($c=1$ 或 $c=m$),下一秒 $d_c\leftarrow -d_c$.
每一秒内,位于 $(r,c)$ 的机器人有 $\frac{p}{100}$ 的概率,成功清理掉位于第 $r$ 行和第 $c$ 列的障碍,之后,它将按照上面的规则进行移动。
若每次清理的结果相互独立,求清理掉障碍物 $(r_d, c_d)$ 所需的期望时间。