做题记录 25.8.28
szt100309
·
·
个人记录
\textcolor{black}\odot P5979 [PA 2014] Druzyny
暴力 dp 显然为
f_i=\max_{0\le j<i,\;i-j\in \bigcap_{k=j+1}^i [c_k,d_k]} f_j+1
考虑 \text{CDQ} 分治，设目前处理区间 [l,r]，中心为 M，则需要处理所有 l\le j\le M<i\le r 的转移 j\to i
令 lmxl_i = \max c_{i\sim M}，lmnr_i = \min d_{i\sim M}，rmxl_i = \max c_{M+1\sim i}，rmnr_i = \min d_{M+1\sim i}
则转移变为
f_i=\max_{l\le j\le M,lmxl_{j+1}\le i-j\le lmnr_{j+1},rmxl_i\le i-j \le rmnr_j} f_j+1
枚举 i，i=lmxl_{j+1}+j 时加入 f_j，i=lmnr_{j+1}+j+1 时删去 f_j，线段树维护目前加入的 f_j 的区间和，则查询 [i-rmnr_i,i-rmxl_i]
时间复杂度 O(n\log^2 n)
代码
参考
\textcolor{black}\odot P11714 [清华集训 2014] 主旋律 \quad UOJ #37. 【清华集训2014】主旋律
令 e(s,t)\;(s,t\subset [1,n]\cap\mathbb N) 表示 u\in s,v\in t,(u,v)\in E 的 (u,v) 的数量
令 f_s 表示点集 s 的导出子图中选择边的子集使得 s 为 \text{SCC} 的方案数
若子集 s 的导出子图不是 \text{SCC}，则它缩点后得到一张 \text{DAG}，设这张 \text{DAG} 中入度为 0 的点在原图上对应的点集为 t（即 t\subset s，t 中点 \text{SCC} 缩点后得到若干独立 \text{SCC}）
对于一个 s，对于它的一种划分 P（P 为集族），其中每个 b\in P 组成一个 \text{SCC}，整体构成一张 \text{DAG}
令 h_S\;(S\subseteq P) 表示钦定 S 中 \text{SCC} 缩点后入度为 0 的方案数
令 h'_S\;(S\subseteq P) 表示缩点后入度为 0 的 \text{SCC} 的集合恰好为 S 的方案数
显然这组 P 对 f_s 的贡献为
\sum_{S\subseteq P,S\ne\mathbb\emptyset} h'_S
显然有
h_S=\sum_{S\subseteq T\subseteq P} h'_T
子集反演得
h'_S=\sum_{S\subseteq T\subseteq P}(-1)^{|S|-|T|} h'_T
令 P^\ast(s) 表示 s 的划分的集合，则
\begin{aligned}
f_s=&2^{e(s,s)}-\sum_{P\in P^\ast(s)}\sum_{S\subseteq P,S\ne\mathbb\emptyset} \sum_{S\subseteq T\subseteq P}(-1)^{|S|-|T|} h'_T\\
=&2^{e(s,s)}-\sum_{P\in P^\ast(s)}\sum_{T\subseteq P,T\ne\mathbb\emptyset}(-1)^{|T|}h'_T\sum_{S\subseteq T,S\ne\mathbb\emptyset}(-1)^{|S|}\\
=&2^{e(s,s)}-\sum_{P\in P^\ast(s)}\sum_{T\subseteq P,T\ne\mathbb\emptyset}(-1)^{|T|+1}h'_T\\
\end{aligned}
令 g_t 为将 t 划分为若干 \text{SCC}，划分得到的数量为奇数的方案数减去偶数的方案数
显然
f_s=2^{e(s,s)}-\sum_{t\subseteq s,t\ne\mathbb\emptyset} 2^{e(s,s/t)}g_t\\
g_s=f_s-\sum_{t\subseteq s,t\ne\mathbb\emptyset,\min s=\min t} g_{s/t} f_t
其中 g 的转移为枚举 \min s 所在 \text{SCC} 的点集
特别地，g_s 贡献到 f_s 时不需要加上第一项 f_s，这样也解决了 f_s,g_s 互相依赖的关系，即
g_s\gets -\sum_{t\subseteq s,t\ne\mathbb\emptyset,\min s=\min t} g_{s/t} f_t\\
f_s\gets 2^{e(s,s)}-\sum_{t\subseteq s,t\ne\mathbb\emptyset} 2^{e(s,s/t)}g_t\\
g_s\gets f_s+g_s
发现只用到了 e(s,s) 和 e(s,s/t)，数量为 O(3^n) 的，容易 O(3^n) 处理用到的位置
总时间复杂度 O(3^n)，容易做到空间复杂度 O(2^n)
luogu \quad UOJ
参考
\purple\odot CF1558D Top-Notch Insertions
一次操作 (x,y) 相当于取出第 x 个元素，插入第 y-1 个和第 y 个元素之间，设插入的值为 u，则 a_{x-1}\le u<a_x
对于最终得到的 a_{1\sim n}，a_i\le a_{i+1}
因此实际上得到的大小关系为 a_1\;\; (\le /<)\;\; a_2 \;\;(\le / <)\;\;\cdots
设其中 c 个为 <，则方案数为 \binom{2n-1-c}n
问题转化为求 c 的数量
倒序模拟这一过程，即限制当前 a_{y-1}\le a_y< a_{y+1}，然后删除 a_y
令 S 为满足最初的 a_i<a_{i+1} 的 i 的集合，则一次 (x,y) 相当于找出剩余数字中第 y 大的，加入 S 并删除该数字
线段树模拟该过程即可
实际可以先插入所有数，处理完一组数据之后撤销
时间复杂度 O(n+\sum m\log n)
代码
参考