PKUWC

P5299 [PKUWC2018] Slay the Spire 洛谷：P5299 [PKUWC2018] Slay the Spire LOJ：#2538. 「PKUWC2018」Slay the Spire 前言：请分清楚 使用 和 抽取。九条要 抽取 \(m\) 张牌，但只会 使用 \(k\) ......

## 题目描述 猎人杀是一款风靡一时的游戏“狼人杀”的民间版本，他的规则是这样的： 一开始有 $n$ 个猎人，第 $i$ 个猎人有仇恨度 $w_i$ ，每个猎人只有一个固定的技能：死亡后必须开一枪，且被射中的人也会死亡。 然而向谁开枪也是有讲究的，假设当前还活着的猎人有 $[i_1\ldots i_ ......

[洛谷传送门](https://www.luogu.com.cn/problem/P5644 "洛谷传送门") 感觉跟 [CF Gym 102978H Harsh Comments](https://codeforces.com/gym/102978/problem/H) 很像。 考虑容斥，钦定 $ ......

[P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298) ## 前言 顺着线段树合并的标签找到这道题，感觉可做，但一写写了整整一天/kk。 ## 题意 给出一个以 $1$ 为根的 $n$ 个节点的二叉树，每个叶子上有一个权值 ......

# P5643 [PKUWC2018]随机游走 [洛谷：P5643 [PKUWC2018]随机游走](https://www.luogu.com.cn/problem/P5643) ## Solution 对点集 $S$，记 $\max(S)$ 表示将 $S$ 中所有点都遍历过的步数，$\min(S ......

### 题意 给出一棵 $n$ 结点树，从结点 $x$ 出发，每次从当前点的所有边中选一条走过去，$Q$ 次询问给定一个点集 $S$，随机游走直到经过 $S$ 中的每一个点至少一次的期望总步数，出发点 $x$ 默认在开始时已经被经过。 $n\le 18, Q\le 5000$ ### 解法 萌新第一 ......

概率的分母在不断变化很麻烦，我们不妨令它可以打到已死的人。由于还活着的人概率之比没有变，显然是不会影响答案的。 考虑容斥，设 $p(S)$ 表示集合 $S$ 中的人在 $1$ 后被打的方案数，那么答案就是 $\sum_{S}(-1)^{|S|}p(S)$。$p(S)$ 实际上就是无限开枪，每次不打 ......

原题链接 题意 给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。 有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。 特别地，点 $x$（即起点）视为一开 ......