做题记录 26.1.21

· · 个人记录

\textcolor{black}\odot P14398 [JOISC 2016] 三明治 / Sandwich

对于两种形式，都令左边的一块编号 0，右边编号 1，每一块记为 (i,j,0/1)

对于一个格子 (i,j)，考虑分别求出先取 (i,j,0) 和 (i,j,1) 的答案，两者取较小值即为 (i,j) 的答案

每个 (i,j,0/1) 建立一个点，表示它先于同一格中另一块取出

对于某一块，要先取出它，则需要取出它两条直角边分别对应的块，而要取出它们，需要先取出两者斜边对应的块，因此每个块向其直角边相邻格子中与之不相邻的块连边

每一块的答案即为可达点的两倍，成环则无解

暴力实现时间复杂度为 O(n^2m^2) 或 O(\frac{n^2m^2}\omega) 的，无法通过

发现对于每个 i 必然存在依赖链 (i,m,0)\to (i,m-1,0)\to(i,m-2,0)\to\cdots 和 (i,1,1)\to (i,2,1)\to(i,3,1)\to\cdots，每条链容易 O(nm)

总时间复杂度 O(n^2m)，容易做到 O(nm\min(n,m))

代码

\textcolor{black}\odot P9385 [THUPC 2023 决赛] 阴阳阵法

令 f_{n,m} 表示 (n,m) 的答案，则 f_{i,0}=(n+m)^i，考虑从 f_{i,j-1} 转移到 f_{i,j}，然后减去最后一个黑点所在环上黑白点数量都是奇数的方案数

f_{i,j}=nf_{i,j-1}-\sum_{y\le i,2\nmid y} \sum_{x\le j,2\nmid x} \binom iy \binom {j-1}{x-1} \binom yx(y-1)!x! f_{i-y,j-x}

暴力实现为 O(n^4)，考虑组合意义优化

后面减去部分本质上是枚举从 i 个白点中选择奇数个，从 j-1 个黑点中选择偶数个，组成一条每个黑点前都有白点的链，剩余部分权值为 f

$$ f_{i,j}=nf_{i,j-1}-g_{i,j-1,1,0,0} $$ $$ g_{i+1,j,1,0,0}\gets (i+1)f_{i,j} $$ $$ g_{i+1,j,p\oplus 1,q,0}\gets(g_{i,j,p,q,0}+g_{i,j,p,q,1})(i+1) $$ $$ g_{i,j+1,p,q\oplus 1,1}\gets (j+1)g_{i,j,p,q,0} $$ 时间复杂度 $O((n+m)^2)

代码

参考

\textcolor{black}\odot AT_agc025_e [AGC025E] Walking on a Tree

令 c_i 表示 (i,fa_i) 被路径覆盖的次数，显然答案上界为 \sum_i \min(c_i,2)，称 (i,fa_i) 的贡献为 \min(c_i,2)

依次加入路径，若某一时刻存在一条期望贡献为 2 的边，目前为止其贡献为 1，且恰好存在一条路径覆盖这条边，则强制定向这条路径，否则任选一条定向

正确性：若不存在合法的路径，对于一种最优解，翻转剩余边也是合法情况，因此无论随机选的边如何定向，必然存在一种最优解包括它

时间复杂度 O(m(n+m))

代码

参考

\textcolor{black}\odot CF325E The Red Button

当 n 为奇数时，0 和 n-1 的非自环入边都来自 \frac{n-1}2，显然不可能存在曼哈顿回路

当 n 为偶数时，令 m=\frac n2，对于任意 0\le i<m，i 和 i+m 都连到 2i 和 2i+1，必然为 i\to 2i,i+m\to 2i+1 或交换之

先按 i\to 2i,i+m\to 2i+1 连边，显然得到若干环，再枚举一遍，若 i 和 i+m 不在同一环内则交换两者出边，从而将两个环合并

时间复杂度 O(n\alpha(n))

代码

参考

\purple\odot P14945 不想玩原神

对行猫树分治，转化为若干次每个位置加入一个数和查询区间内数的出现情况，线段树每个结点保存一个 bitset，区间长度不超过 B 时暴力修改，超过 B 时 \text{push\_up}

时间复杂度 O(n\log n(\frac nB\cdot \frac n\omega+n\log B)+q\log n\cdot \frac n\omega)，取 B=O(\frac{n}{\omega\log n}) 可以做到 O(n^2\log^2 n+\frac{nq\log n}\omega)

代码

参考

P14860 [ICPC 2021 Yokohama R] Cancer DNA

依次加入 s_{1\sim m}，加入 s_i 时求出 p_i 表示一个与 s_i 匹配的字符串不与 s_{1\sim i-1} 匹配的概率，则答案为 \sum_i p_i \cdot 4^{n-k_i}，其中 k_i 为 s_i 中 ? 的数量

由于要求答案误差不超过 5\%，等价于要求每个 p_i 误差不超过 5\%

设真实值为 p'_i，蒙特卡洛式随机得到的值为 p_i，相对误差不超过 \delta=5\%，进行 x 次操作误差在给定范围的概率不小于 1-\exp(-\frac{np'_i\delta^2}2)-\exp(-\frac{np'_i\delta^2}{2+p'_i})，进行 \frac{10^7}{m^2n} 次足够

代码

参考