2024.7.26 模拟赛
Whitely
·
·
题解
2024.7.26 模拟赛
A
给 a_{1\dots n}，一种重排方案 a_{p_1},a_{p_2},\dots a_{p_n} 合法当且仅当其奇偶交替，其代价为 \sum_{i=1}^{n}|i-p_i|，求所有代价最小的合法重排方案中字典序最小的一个，n\le 10^5,a_i\le 10^9。
Sol
- 要求满足代价最小条件下字典序最小的方案，先求出一种代价最小的方案，尝试调整。
- 交换调整，找可以和 a_i 交换的 a_j 中最优的，尝试转变视角，从小到大枚举 a_j，贡献给尽量靠前的 i。
- 要记录 p_i 表示 i 在原数组中位置，此时要保证原数组中数两两不同，有相同则离散化钦定顺序。
先不考虑字典序，一种代价最小的方案是不改变 a 中值为奇/偶的位的内部顺序，设这样得到的序列为 b_{1\dots n}。在此基础上，你想进行若干次交换 b_i,b_j 的操作，每次操作后需保证 b 合法，且代价不变。
设 i 在 a 中的位置为 p_i，则初始 b 对应的代价为 \sum_{i=1}^n|i-p_{b_i}|，交换 b_i,b_j 则这两位代价改为 |i-p_{b_j}|+|j-p_{b_i}|（这里 b_i,b_j 是交换前的值），交换的前提是 b_i\equiv b_j(\bmod 2) 且 i\equiv j(\bmod 2)。
对 i 为奇和 i 为偶两类位置分别处理。钦定 i<j，你发现交换后代价不变的充要条件为 p_{b_i},p_{b_j}<i 或 p_{b_i},p_{b_j}>j（不会有 p_{b_i}=p_{b_j} 情况），以两者均 <i 的情况为例。
从前到后处理 i，每次和后面位交换让能交换到的最小的 b_j 和 b_i 交换。这里只交换一次，因为多次能成功一次也可以，同时现在不需要最小化后面的字典序，这样 O(n^2) 解决问题。要优化，就不能每次处理一个 b_i，而是对一段同奇偶的 i 一并处理。但是对每个 i，合法 j 的段不尽相同，于是你改变视角，用 b_j 贡献给最靠前，交换后更优且合法的位置 i。
交换后更优这个条件不易处理，你想到从小到大处理 b_j，将交换看作 b_j 填入位置 i，这样你只需要记录未填数的位置集 s，找最小的 i 满足 i\in s,p_{b_j}<i，可以 lower_bound。
另一类交换同理，这样可以 O(n\log n) 。
最后注意可能有初始 a_i=a_j 的情况，而 \forall a_i\neq a_j 是记录 p 数组的前提，此时离散化，手动钦定顺序，最后再对应回去。
B
#### Sol
> 难以使用任何数据结构维护/性质极少的问题，想根号分治。
以操作开关 $i$ 对应灯在操作前均为关为例，则本次操作的贡献为 `操作灯数 - 所有操作灯相邻的已开灯(不含同开关灯)数 - 操作灯中相邻对数`，设 $S_i=\{j|l_j=i\}$，则显然可以 $O(|S_i|)$ 维护一次操作。
定义 $|S_i|>B$ 的开关 $i$ 为大开关，否则为小开关。则操作小开关的情况暴力维护，操作大开关的情况将相邻分为与其余大开关相邻 $^1$，和与其余小开关相邻 $^2$。
对于 $^1$，直接处理出所有大开关对的相邻灯对数，可以 $O(n)-O(\frac{n}{B})$。对于 $^2$，考虑在操作对应小开关时维护，可以 $O(B)-O(1)$，这样 $B$ 取 $\sqrt n$ 时最优，复杂度 $O(n\sqrt n)$。
### C
$m$ 棵有根树，一个源点。棋子在源点时可以选择一棵没有走过的树，将棋子移动到树根；在某棵树的叶子上时，移动回源点；否则移动到这个点的一个子节点，不能操作者输。保留一部分树使得先手必胜，求方案数，$m\le 10^5,\sum n\le 10^5$。
#### Sol
一棵树的信息可以压缩成二元组 $(a,b)(a,b\in \{0,1\})$，分别表示，树内无路可走分别看作负/胜，棋子初始放在树根，树内第一次移动棋子的人是/否必胜。
对应到原题，定义走到当前树根（选择这棵树）的人为当前先手，$a=1$ 相当于当前后手有策略保证自己成为下一棵树时的先手，$b=1$ 相当于当前后手有策略保证自己成为下一棵树时的后手，为 $0$ 相当于先手有策略可以保证对应状态。
赢得游戏相当于选完所有数后是后手，接下来讨论 $(a,b)$ 四种取值时，先手选择这棵树对局势的影响。
- 若为 $(0,0)$，先手可以选择之后成为先手或后手，而对于余下的树，那时的先手和后手必有一者必胜，当前先手选择这一方，可以必胜。
- 若为 $(0,1)$，若这棵树之后的先手必胜，当前先手会想方设法阻止当前后手成为后续先手，否则当前后手也不会想成为后续先手，这样可知这棵树不影响局势。
- 若为 $(1,0)$，同理，先后手互换，胜负互换。
- 若为 $(1,1)$，同理知后手必胜。
现在想树集确定情况下先手会如何选择下一棵树。若有 $(0,0)$，选择后可以胜；若有非 $(1,1)$，不会选 $(1,1)$；而 $(1,0)$ 和 $(0,1)$ 选时哪一方是先手并不影响，所有这样的树的影响可以表示为 $1/0$ 表示是否交换先后手。
若无 $(0,0)$ 有 $(1,1)$，必会先执行翻转先后手，翻转后的先手必败，多个 $(1,1)$ 当前后手不断选择后手即可（$(1,1)$ 和 $(0,0)$ 同时存在不影响 $(0,0)$，因为先手一定会先选这个），此时 $(1,0)$ 个数需要为奇。无 $(0,0)$ 无 $(1,1)$，同样需要 $(1,0)$ 个数为奇。
这样你知道，若选奇数个 $(1,0)$，必胜；否则需要 $(0,0)$，其余两种树并不关心，这样可以 $O(m)$。
### D
$n$ 个人，给定 $p\in (0,1)$，表示 $i,j(i<j)$ 两人比赛时，$i$ 胜出概率为 $p$。所有人两两比赛，对所有 $k=1\dots n-1$，求能选出一个恰 $k$ 个人的集合（称这个集合为胜者组），满足集合内任一个人和集合外任一个人对战均胜出的概率，其中 $n\le 10^6$。
#### Sol
考虑 `DP`，每次加入一个人，设 $f_{i,j}$ 为前 $i$ 个人内部比赛，得以选出恰 $j$ 人的胜者组的概率，则 $f_{i,j}=f_{i-1,j}\cdot p^j+f_{i-1,j-1}\cdot (1-p)^{i-j}$，难以化简，知 $^1f_{i,j}=f_{i,i-j}$。
考虑组合意义，定义败者组为组内一人与组外一人比赛，组内人均失败，则胜者组的补集和败者组一一对应，选出 $j$ 人胜者组和选出 $i-j$ 人败者组的概率相等，结合 $^1$ 式可知，选出 $i-j$ 人败者组或胜者组的概率相同。
若定义 $g_{i,j}$ 为选 $j$ 个人败者组概率，其递推式中与 $f$ 的区别在于 $p$ 和 $1-p$ 调换，又 $f_{i,j}=g_{i,j}$，则 $f_{i-1,j}\cdot p^j+f_{i-1,j-1}\cdot (1-p)^{i-j}=f_{i-1,j}\cdot (1-p)^{j}+f_{i-1,j-1}\cdot p^{i-j}$，你想知道 $f_{n,1\dots n-1}$ 的值，于是你想知道 $f_{i,j}\to f_{i+1,j}$ 和 $f_{i,j}\to f_{i,j+1}$ 的 $O(1)$ 转移，上式化简可得。
一种极重要的特殊情况是（场上这里细节错误），$p=\frac{1}{2}$，此时将 $p$ 和 $1-p$ 调换并不能简化问题，不妨当作另一个 `subtask`。此时的性质是不关心编号前后，则对于一个确定的 $k$，答案为 $\binom{n}{k}p^{k\cdot (n-k)}$。