十三联测 #9
B
给出 \(n\) 个长度为 \(m\) 的不同的 \(01\) 串 \(s_i\)。定义长度 \(nm\) 的好的字符串每 \(m\) 位都是某个 \(s_i\)，且 \(i\) 互不相同。
你有打字机，有两种操作，一种是 \(p\) 的概率打出 \(1\)，\(1-p\) 概率打出 \(0\)；第二种把 \(01\) 交换。
问最佳操作下，能打出好的字符串的概率。
将 \(01\) 字典树建出来，好的字符串充要条件就是每个点向左走 \(siz_{ls}\) 次，向右走 \(siz_{rs}\) 次。
这里将一个条件拆成了 \(n\) 个限制。因为每个限制都是独立的，所以贡献相乘即可。
计算 \(f_{l,r}\) 表示向左走 \(l\)，向右走 \(r\) 的概率。\(f_{l,r}=\max(pf_{l-1,r}+(1-p)f_{l,r-1},(1-p)f_{l-1,r}+pf_{l,r-1})\)。
D
有两行点，每行有 \(n\) 个。连一条跨越的边（线段）的贡献是 \(w_{u,v}\)，一个点可以被边连的代价是 \(-v_u\)。
\(q\) 次询问区间 \([a,b]\) 与 \([c,d]\) 的点可以连边，且边不能再中间相交，可以在点上相交。
\(n\le 300,q\le 10^5\)。
考虑 dp，设 \(f_{i,j}\) 表示已经连接 \([a,i)\) 与 \([b,j)\) 的答案。
\(g_{i,j}\) 表示已经在付 \(i\) 的代价，连接 \([a,i],[b,j)\) ；\(h_{i,j}\) 表示已经付 \(j\) 的代价，连接 \([a,i),[b,j]\) 的答案。
之所以这么设状态是因为 \(i,j\) 最多只有一个点可以向后面连边。
转移的话：\(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},g_{i-1,j},h_{i,j-1})\)。
\(g_{i,j}=\max(f_{i,j}-v_i,g_{i,j-1},g_{i,j-1}+w_{i,j-1}-v_{j-1},h_{i,j-1}+w_{i,j-1}-v_i)\)。
\(h_{i,j}=\max(f_{i,j}-v_j,h_{i-1,j},h_{i-1,j}+w_{i-1,j}-v_{i-1},g_{i-1,j}+w_{i-1,j}-v_j)\)。
这玩意儿可以转化为 DAG 上最长路问题。
共 \(O(n^2)\) 个点 \(O(n^2)\) 条边，每次问两点之间最长路。考虑分治。
对于 \(mid\)，若 \(mid\in[a,b]\)，那么必然存在一个点 \(j\) 经过 \(h_{mid,j}\)，枚举这个点求最长路再递归下去即可。