C
有 \(n\) 个点,一开始 \(s\) 点是白色,其余黑色,你可以花费 \(p_i\) 的代价使 \(i\) 点的颜色变成 \(a_i\) 点的颜色。
若第 \(i\) 个点为白色,那么会有 \(w_i\) 的代价,问贡献减去代价最大是多少。\(n\le 5000\)。
不难发现这是一个外向基环树的形式。如果 \(s\) 不在环上,就是一个树的形式。
树很简单,因为白点一定与根节点联通,只需要设计一个 \(O(n)\) 的 dp 即可。
但是环不一样,因为数据范围支持 \(O(n^2)\),所以其中必有蹊跷。
我们注意到一个非常致命的问题,也就是环上的点变成了 \(1\) 之后,它还可以变为 \(0\)。
所以现在树的部分变成这样:设 \(f_{u,i}\) 表示 \(u\) 子树里,变换了 \(u\) 次的代价。这个是 \(O(n^2)\) dp。
现在考虑环上的部分怎么办?我们可以得到环上每个点变化了 \(t\) 次,其子树内的最大贡献。
考虑在环上能合法的 \(t\) 集合是怎么样的呢?我们从 \(s\) 开始,\(t\) 序列不增,且极差 \(\le 2\)。
于是 dp 就做完了。
B
有一个 01 串 \(s\),\(q\) 次询问,问一个区间的所有子序列的权值和。
权值和的意思是:问至少多少次反转一个区间,使得其权值为 01 交替的形式。
\(n,q\le 5e6\)。
如果我们已知一个序列,考虑差分,反转一个区间,也就是反转差分数组的两个端点。
最后你要使得序列变成 01111... 或 11111...,权值显然是除去第一位,\(0\) 的个数除以二向上取整的值。
所以我们可以设计一个 dp,\(f_{0/1,0/1},g_{0/1,0/1}\) 表示的状态是当前是否钦定第一位,当前 \(0\) 的个数奇偶性。
\(f,g\) 分别方案数和贡献和,我们可以设计一个动态 dp 来处理该过程,前缀矩阵积和前缀逆矩阵积即可。
但是常数需要带上 \(216\),无法通过。
以下是题解做法:把权值写成 \(w=\sum_{i=l}^{r-1}[s_i=s_{i+1}]\),我们相当于要求 \(\frac{1}{2}\sum w+[2\not |w]\)。
我们先算 \(\sum w\),考虑拆贡献,若 \(s_i=s_j(i<j)\),那么会有 \(2^{r-l-j+i}\) 的贡献。
那么,贡献也就是 \(2^{r-l}\times \sum_{s_i=s_j,i,j\in[l,r].i<j} 2^{i-j}\),差分,预处理 \(\sum_{i,j\le l,s_i=s_j},2^{i-j}\),\(\sum_{i\le l,l<j\le r.s_i=s_j}2^{i-j}\)。
再算 \(\sum [2\not |w]\),\(w\) 的奇偶性也就是子序列长度和 \([s_{st}=s_{ed}]\) 之和的奇偶性,考虑计算每对 \(st,ed\) 的贡献。
对于 \(ed-st\le 1\) 的特判,其他的,子序列长度奇偶个数相同,有 \(2^{ed-st-2}\) 种。