标签：pre 记录 text sum len 2023.1 2017 dp

部分题解

CF 1770 E（树，期望）

考虑每一条边的贡献。

如果每条边的方向已经确定，那么可以得到最后关键点的情况，设 \(sz_i\) 表示 \(i\) 子树的关键点的个数，那么贡献就是 \(\sum_{i}sz_i(k-sz_i)\)。

但是，每条边的方向是不确定的，且所有的情况数是指数级别的，然后就不会做了。

这里可以使用一个经典技巧（以前见过，但印象不深刻，这道题加深了对这个技巧的印象）：如果一种确定的方案不好维护，那么可以考虑维护期望，最后再反解出总的方案数。

设 \(p_i\) 表示节点 \(i\) 是关键点的概率，对于一条边 \((u,v)\)，不妨设 \(u\) 是 \(v\) 的父亲，那么新的 \(p_u'=p_v'=\frac{p_u+p_v}{2}\)。

又由于 \(sz_i\) 的改变量最大为 \(1\)，因此我们可以在删掉一条边 \((u,v)\) 的时候直接维护 \(sz_v(k-sz_v)\) 的期望值。

易错点：不能维护 \(sz_i\) 的期望值再相乘，还需要维护 \(sz_i^2\) 的期望值，即 \(E(sz_i(k-sz_i))=-E(sz_i^2)+kE(sz_i)\)。

NOI 2009 管道取珠（转化，dp，公式推导）

方法一

先说一下题解做法。

可以发现要求的答案可以转化为执行两个操作最后颜色序列相等的方案数。

直接设 \(f(i,j,x)\) 第一个操作取了上面的 \(i\) 个，下面的 \(j\) 个，第二个操作取了上面的 \(x\) 个，下面的 \(i+j-x\) 个的方案数。

直接转移就是 \(\mathcal{O}(n^3)\)。

方法二

我太菜了，做复杂了，是暴力推的式子。

先考虑最后答案的颜色序列固定的时候怎么做，假设颜色序列为 \(c_i\)。

直接设 \(dp(i,j)\) 表示上面取了 \(i\) 个，下面取了 \(j\) 个，与当前的颜色序列匹配的方案数，转移就是

\[dp(i,j)=[c_{i+j}=a_i]dp(i-1,j)+[c_{i+j}=b_j]dp(i,j-1) \]

那么这种颜色序列对答案的贡献就是 \(dp^2(n,m)\)。

最后的颜色序列是指数级别的，肯定不能直接枚举，于是考虑对最后的颜色序列 dp。

令 \(S_{len}\) 为所有长度等于 \(len\) 的颜色序列构成的集合，对于 \(c\in S_{len}\)，令 \(dp(c,i,j)\) 表示颜色序列为 \(c\) 时，上面取了 \(i\) 个，下面取了 \(j\) 个，与当前的颜色序列匹配的方案数。

设

\[f(i,j)=\sum_{c\in S_{i+j}}dp^2(c,i,j) \]

带入之前的递推式进行公式推导，得

\[\begin{aligned} &f(i,j)=\sum_{v=0}^{1}\sum_{c\in S_{i+j-1}}[v=a_i]dp^2(c,i-1,j)+[v=b_j]dp^2(c,i,j-1)+2[v=a_i][v=b_j]dp(c,i-1,j)\cdot dp(c,i,j-1)\\ &=\left(\sum_{v=0}^{1}[v=a_i]f(i-1,j)+[v=b_j]f(i,j-1)\right)+2[v=a_i][v=b_j]\sum_{v=0}^{1}\sum_{c\in S_{len-1}}dp(c,i-1,j)\cdot dp(c,i,j-1) \end{aligned} \]

发现最右边的那一堆式子不好直接递推，于是可以考虑令

\[g(len,i,j)=\sum_{c\in S_{len}}f(i,len-i)\cdot f(j,len-j) \]

于是

\[f(i,j)=\sum_{v=0}^{1}[v=a_i]f(i-1,j)+[v=b_j]f(i,j-1)+2[v=a_i][v=b_j]g(len,i-1,i) \]

下面考虑 \(g\) 的转移，同样可以根据递推式推导，化简得

\[g(len,i,j)=\sum_{v=0}^{1}[v=a_i][v=a_j]g(len-1,i-1,j-1)+[v=a_i][v=b_{len-j}]g(len-1,i-1,j)\\ +[v=b_{len-i}][v=a_j]g(len-1,i,j-1)+[v=b_{len-i}][v=b_{len-j}]g(len-1,i,j) \]

于是总复杂度为 \(\mathcal{O}(n^3)\)。

JXOI 2017 数列（性质，dp）

正难则反，考虑倒着构造。

刚开始，\(a_n\) 和 \(a_{n-1}\) 可以在范围内任意取。

考虑 \(a_{n-2}\)，它不能在 \(a_{n-1}\) 和 \(a_{n}\) 之间，但是可以等于 \(a_n\)。

同理，对于 \(a_{n-3}\)，它不能在 \(a_{n-2}\) 和 \(a_{n-1}\) 之间（因为之前的限制，所以它不能等于 \(a_{n-1}\)）。

因此，不能选择的区间长度单调不增，且一定是包含关系。

这就可以考虑 dp。

设 \(f(i,l,r)\) 表示考虑了 \(i\) 到 \(n\)，不能选的区间为 \([l,r]\) 的方案数。

注意有一种情况是 \(a_n=a_{n-1}=a_{n-2}=a_{n-3}=\cdots=a_{n-p}=0\)，这种情况需要特殊处理，dp 再记录一维状态即可。

总复杂度是 \(\mathcal{O}(nV^3)\)。

HAOI 2017 字符串（AC 自动机，树状数组）

先考虑如何判断字符串 \(S\) 和 \(T\) “相等”。

条件为 \(|S|=|T|\) 且 \(\text{LCP}(S,T)+\text{LCS}(S,T)+k\geq |S|\)。

可以发现，最后的答案和 \(p_i\) 的前缀或后缀在 \(s\) 中的出现情况有关，于是可以考虑 AC 自动机。

建出所有 \(p_i\) 的正串和反串的 AC 自动机（一个），然后考虑一个单独的字符串 \(p_i\) 的贡献。

假设 \(p_i\) 的长度为 \(\text{len}\)，如果 \(p_i\) 在 \(s\) 中恰好能够匹配前 \(j\) 个字符，那么 \(p_i\) 至少从 \(j+k+1\) 开始的后缀都必须在 \(s\) 对应的位置匹配。

发现如果有条件中有”恰好“并不好计算贡献，因此我们不妨先不考虑“恰好”，让前后缀都先至少满足条件。

假设 \(p_i\) 的前缀 \(j\) 在 AC 自动机上的节点为 \(u\)，后缀 \(j+k+1\) 为 \(v\)，对于 \(s\) 中以 \(pos\) 结尾的后缀，在 AC 自动机上的节点为 \(x\)，以 \(pos+k+1\) 开始的前缀节点为 \(y\)，那么，\(p_i\) 有贡献当且仅当在 fail 树上，\(x\) 在 \(u\) 的子树中且 \(y\) 在 \(v\) 的子树中。

于是相当于是先遍历 \(u\) 子树的所有 \(x\)，在所有的 \(y\) 上打上标记，最后再查询 \(v\) 的子树有多少标记，这可以用树状数组维护。

现在还有个问题是，我们算的是至少，一个合法的答案可能会算多次，这可以用 \(k-1\) 的答案去减，但是要注意一下边界。

CQOI 2017 小Q的表格（转化，莫比乌斯反演，分块）

第一步很关键，考虑转化一下 \(b\times f(a,a+b)=(a+b)\times f(a,b)\)，发现两边同时乘上 \(a\) 之后就可以化为

\[\frac{f(a,b)}{a\times b}=\frac{f(a,a+b)}{a\times (a+b)} \]

这是一个辗转相减的形式，令 \(d=\gcd(a,b)\)，最后的结果为

\[f(a,b)=\frac{ab}{d^2}f(d,d) \]

考虑答案的公式

\[\sum_{d=1}^{k}f(d,d)\sum_{i=1}^{\lfloor\frac{k}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{k}{d}\rfloor}ij[\gcd(i,j)=1] \]

再令

\[g(x)=\sum_{i=1}^{x}\sum_{j=1}^{x}ij[\gcd(i,j)=1] \]

莫比乌斯反演一下得

\[g(x)=\sum_{d=1}^{x}\mu(d)d^2\left(\frac{\lfloor\frac{x}{d}\rfloor(\lfloor\frac{x}{d}\rfloor+1)}{2}\right)^2 \]

直接预处理是 \(\mathcal{O}(k\sqrt{k})\) 的。

还能不能再化简呢？

这里必须引入一个技巧

\[\lfloor\frac{n}{i}\rfloor-\lfloor\frac{n-1}{i}\rfloor=[i\mid n] \]

于是我们把 \(g(x)\) 差分后就可以惊奇地发现

\[g(x)-g(x-1)=\sum_{i\mid x}\mu(i)i^2(\frac{x}{i})^3=x^2\varphi(x) \]

而 \(g(0)=0\)，因此

\[g(x)=\sum_{i=1}^{x}i^2\varphi(i) \]

这样，\(g(x)\) 就可以 \(\mathcal{O}(k)\) 预处理了。

于是答案为

\[\sum_{d=1}^{k}f(d,d)g(\lfloor\frac{k}{d}\rfloor) \]

设 \(f(d,d)\) 区间查询复杂度为 \(\mathcal{O}(Q(k))\)，单次修改复杂度为 \(\mathcal{O}(U(k))\)。

那么总复杂度为 \(\mathcal{O}(m(\sqrt{k}Q(k)+U(k)))\)。

需要支持快速查询，但修改的复杂度可以不那么优的数据结构来维护，自然而然想到分块。

使用分块可以做到 \(\mathcal{O}(1)\) 查询，\(\mathcal{O}(\sqrt{k})\) 修改，于是总复杂度为 \(\mathcal{O}(m\sqrt{k})\)。

SNOI 2017 遗失的答案（容斥，子集反演）（状压 dp，FMT）

子集反演的好题！

不同的质因子数小于等于 \(8\)，很明显可以状压。

于是我的想法是把 \(1\) 到 \(n\) 的数按照不同的状态分组，设 \(f(i,S)\) 和 \(g(i,S)\) 分别表示前 \(i\) 组或后 \(i\) 组状态为 \(S\) 的方案数，查询的时候 \(\text{FMT}\) 合并。时间复杂度很劣。

更好的方法是考虑容斥，设 \(f(S)\) 表示按位或起来为 \(S\) 的方案数，\(g(S)\) 表示按位或起来是 \(S\) 的子集的方案数。

那么

\[g(S)=\sum_{T\subseteq S}f(T) \]

子集反演一下得

\[f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T) \]

于是这道题中，如果需要查询数代表的集合为 \(X\)，那么

\[g(S)=[X\subseteq S]2^{\text{sum}(S)-1} \]

其中 \(\text{sum(S)}\) 表示集合 \(S\) 中的数的个数。

每次查询的复杂度为 \(\mathcal{O}(2^{2\omega(n)})\)，总共需要查询的集合数与约数个数有关，无论是时间复杂度还是空间复杂度都比之前的方法更优。

SDOI 2017 苹果树（转化，树形依赖背包）

首先问题可以转化为可以免费选一条从根出发的链，再对剩下部分做一次树形依赖背包。

先考虑一般的树形依赖背包怎么做。

求出 \(\text{dfs}\) 序后设 \(f(i,j)\) 表示 \(\text{dfs}\) 序上 \(i\) 到 \(n\)，选择 \(j\) 个物品的最大值，有转移

\[f(i,j)=\max(f(i+\text{sz}(i),j),\max_{k>0}f(i+1,j-k)) \]

能这样转移是因为在 \(\text{dfs}\) 序上一个点子树的 \(\text{dfs}\) 序对应一段区间。

下面再来思考这道题怎么做。

由之前的分析，树形依赖背包需要在 \(\text{dfs}\) 序上 \(\text{dp}\)，那么我们可以考虑设 \(f(i,j)\) 表示 \(\text{dfs}\) 序考虑到点 \(i\)，选了 \(j\) 个需要花费空间的物品的最大值，且根到 \(i\) 的这条链作为免费链，依赖关系只考虑了非免费链上的点。

接下来考虑点 \(u\) 怎么转移到其它点，假设 \(v\) 是 \(u\) 的儿子。

首先，如果 \(v\) 是 \(u\) 的第一个儿子，那么 \(v\) 肯定也在免费链上，直接 \(\mathcal{O}(k)\) 多重背包转移即可（要用双端队列优化）。

如果 \(v\) 不是 \(u\) 的第一个儿子，很明显我们不能直接转移，因为前面的子树内的点不在免费链上，我们需要考虑它们的依赖关系。

我们考虑在 \(\text{dfs}\) 完 \(u\) 的一个儿子后修改 \(f(u,*)\)，即考虑那个儿子与它的依赖关系。

注意到这样一个性质，免费链的端点一定是一个叶子，于是我们可以直接修改 \(f(u,*)\)（其实新开一个数组也可以，这样写只是为了实现方便）。

设 \(b_i\) 表示节点 \(i\) 的权值，于是有转移

\[f(u,i)=\max(f(u,i),f(v,i-1)+b_v) \]

即我们钦定必须选择一个节点 \(v\)（结合代码理解）。

总复杂度 \(\mathcal{O(nk)}\)。

六省联考 2017 分手是祝愿（性质，期望 dp）

需要观察到一个关键性质：每种按键不会被其它组合键代替。

于是可以倒着扫一遍，计算出哪些按键要按奇数次。

然后设 \(f(i)\) 表示还有 \(i\) 个需要按奇数次的键，变成 \(i-1\) 个需要按奇数次的键的期望次数。

于是有等式

\[f(i)=\frac{i}{n}+\frac{n-i}{n}(f(i)+f(i+1)+1) \]

得

\[f(i)=\frac{n+(n-i)f(i+1)}{i} \]

设 \(\text{cnt}\) 表示需要按奇数次的键的个数，如果 \(\text{cnt}\leq k\)，那么答案为 \(\text{cnt}\)，否则答案为 \(\sum_{i=k}^{\text{cnt}}f(i)\)。

CTSC 2017 密钥（性质，转化）

先考虑 \(X\) 的位置固定了之后怎么检验，很明显可以记一个前缀和 \(\text{pre}\)，把 \(A\) 视为 \(+1\)，\(B\) 视为 \(-1\)，那么答案特征值就是满足 \(\text{pre}_i>0\) 且第 \(i\) 个位置为 \(A\) 的 \(i\) 的个数。

再来考虑 \(X\) 的顺时针移动，如果下一个位置是 \(B\)，那么相当于是所有前缀和 \(+1\)，如果是 \(A\)，相当于是除了这个位置以外的所有位置 \(-1\)，还要特殊考虑一下这个位置的值。

于是可以开一个桶维护前缀和等于某个值的前缀个数，用一个指针指向当前值为 \(0\) 的位置，再记一个变量表示当前大于 \(0\) 的前缀和的个数，这些都可以 \(\mathcal{O}(1)\) 动态维护。

于是现在 \(1\)、\(2\) 问已经解决了，第三问完全可以用类似的方法维护，但不用这么麻烦。

有一个结论是：一个由 \(k\) 个 \(1\) 和 \(k\) 个 \(-1\) 组成的前缀和，\(k\) 个 \(1\) 中前缀和大于 \(0\) 的个数加上 \(k\) 个 \(-1\) 中前缀和小于 \(0\) 的个数等于 \(k\)。

因此第 \(3\) 问可以直接判断大于 \(0\) 的前缀和个数是否等于 \(k-S\)。

代码实现很精妙，感觉很有收获。

CTSC 2017 网络（树的直径，结论，二分答案，排序，双指针）

首先，有个结论是选择的两个端点一定在直径上。

于是最后的答案只和一个点到直径某个端点的距离 \(\text{pre}_i\)，和它挂着的最长链的长度 \(\text{val}_i\) 有关。

假设二分的答案为 \(x\)，加的边的长度为 \(m\)，对于任意的 \(j<i\)，如果满足 \(\text{pre}_i-\text{pre}_j+\text{val}_i+\text{val}_j>x\)，那么必须满足存在一个点对 \(b<a\)，使得

\[|\text{pre}_j-\text{pre}_b|+|\text{pre}_i-\text{pre}_a|+\text{val}_i+\text{val}_j+m\leq x \]

把绝对值拆开，也就是要找到一个 \(b<a\)，满足

\[x-m+\text{pre}_a+\text{pre}_b\geq \text{val}_i+\text{pre}_i+\text{val}_j+\text{pre}_j=A\\ x-m-\text{pre}_a+\text{pre}_b\geq \text{val}_i-\text{pre}_i+\text{val}_j+\text{pre}_j=B\\ x-m+\text{pre}_a-\text{pre}_b\geq \text{val}_i+\text{pre}_i+\text{val}_j-\text{pre}_j=C\\ x-m-\text{pre}_a-\text{pre}_b\geq \text{val}_i-\text{pre}_i+\text{val}_j-\text{pre}_j=D \]

可以先尝试找到最大的 \(A,B,C,D\) 来简化问题。

考虑对每个 \(i\) 计算答案，我们需要满足那个限制，于是可以考虑开两个数组，一个以 \(\text{val}_i+\text{pre}_i\) 为关键字从小到大排序，一个以 \(\text{val}_j-\text{pre}_j\) 为关键字从大到小排序，双指针一下即可得到 \(A,B,C,D\) 的最大值。

这样做可能有个问题：排了序之后就不一定满足 \(j<i\) 的限制了，但其实是不影响的因为如果存在 \(j>i\) 满足那个限制，那么 \(j<i\) 时也一定满足那个限制。

找到 \(A,B,C,D\) 的最大值之后可以考虑对于每个 \(a\) 计算 \(b\) 的合法区间，根据单调性维护 \(4\) 个指针，然后求一下区间交即可判断。

时间复杂度 \(\mathcal{O}(n\log V)\)。

标签：pre,记录,text,sum,len,2023.1,2017,dp
From： https://www.cnblogs.com/yanchengzhi/p/17060675.html

2023.1 做题记录

目录