水题记录1.2

28/50

水题记录1.2

T1.BZOJ1801[AHOI2009]中国象棋

给你一个\(n \times m\)的矩阵, 你可以随便放一些炮, 保证每行每列的炮的个数都小于等于二求方案数

考虑一下 \(dp\) , 设\(f_{i,j,k}\) 表示考虑了前 \(i\) 行有 \(j\) 列放了一个 \(k\) 列放了两个的方案数

然后我们枚举一下这一行放的炮的个数, 然后讨论一下放在哪

转移显然 \[ f_{i,j,k} \to \begin{cases} f_{i + 1,j,k} \\ f_{i + 1, j + 1, k} \ \ \ \ \ \ if\ m - j - k \ge 1\\ f_{i + 1, j - 1, k + 1} \ \ if \ \ j \ge 1 \\ f_{i + 1, j, k + 1} \ \ \ \ \ if \ \ m - j - k \ge 1 \ \ and \ \ j \ge 1 \\ f_{i + 1, j + 2, k} \ \ \ \ \ if\ \ m - j - k \ge 2 \\ f_{i + 1, j - 2, k + 2} \ \ if \ \ j \ge 2\end{cases} \]

T2.LUOGUP4948 数列求和

\[ S_n(k) = \sum _ {i = 1} ^ {n} i^k \cdot a^i \]

\(S_n(k) \ \ mod (10^9 + 7)\)

\(n \le 10^{18}, k \le 2000, a \le 10^9\)

考虑化一下式子 \[ a \cdot S_n(k) = 0^k \cdot a^1 + 1^k \cdot a^2 + \cdots + (n - 1)^k \cdot a^n + n^k \cdot a^{n + 1} \]

\[ S_n(k) = 1^k \cdot a^1 + 2^k \cdot a^2 + \cdots + n^k \cdot a^n \]

两式相减得 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot ((i - 1)^k - i ^ k) \] 二项式定理展开一下 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot (\sum _ {j = 0} ^ {k} \binom{k}{j}i^j(-1)^{k - j} - i^k) \]

\[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot \sum _ {j = 0} ^ {k - 1} \binom{k}{j}i^j(-1)^{k - j} \]

改变一下求和顺序 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {j = 0} ^ {k - 1} \binom{k}{j}(-1)^{k - j}\sum _ {i = 1} ^ {n}a^i \cdot i ^ j \] 发现 \(\sum_{i = 1}^n a^i \cdot i^j\) 其实就是 \(S_n(j)\)

所以 \[ S_n(k) = \frac{n^k \cdot a^{n + 1} + \sum _ {j = 0} ^ {k - 1} \binom{k}{j}(-1)^{k - j} \cdot S_n(j)}{a - 1} \] \(O(k ^ 2)\) 递推一下就好了

好了终于推完了, 但是我们又发现了一个问题当 \(a = 1\)时这个式子是不成立的

所以我们再分类讨论一波

\(a = 1\)\[ S_n(k) = \sum_{i = 1} ^ {k} i ^ k \] 发现是个自然数幂, 对我们可以直接伯努利数啊

假的其实并不会, 那就继续推一下 \[ S_n(k) = \sum _ {i = 1} ^ n (i + 1) ^ k - (n + 1) ^ k +1 \]

\[ S_n(k) = \sum _ {i = 1} ^ n \sum _ {j = 0} ^ k \binom{k}{j} \cdot i^j - (n + 1) ^ k + 1 \]

改变求和顺序 \[ S_n(k) = \sum _ {j = 0} ^ k\binom{k}{j} \cdot\sum _ {i = 1} ^ n i^j - (n + 1) ^ k + 1 \]

\[ S_n(k) = \sum _ {j = 0} ^ k\binom{k}{j} \cdot S_n(j) - (n + 1) ^ k + 1 \]

\[ \sum _ {j = 0} ^ {k - 1} \binom{k}{j} \cdot S_n(j) = (n + 1) ^ k - 1 \]

\[ \sum _ {j = 0} ^ {k - 2} \binom{k}{j} \cdot S_n(j) + S_n(k - 1) \cdot \binom{k}{k - 1} = (n + 1) ^ k - 1 \]

\[ k \cdot S_n(k - 1) = (n + 1) ^ k - 1 - \sum _ {j = 0} ^ {k - 2} \binom{k}{j} \cdot S_n(j) \]

\(k = k + 1\) 便有 \[ (k + 1) \cdot S_n(k) = (n + 1) ^ {k + 1} - 1 - \sum _ {j = 0} ^ {k - 1} \binom {k + 1}{j} S_n(j) \]

\[ S_n(k) = \frac{(n + 1) ^ {k + 1} - 1 - \sum _ {j = 0} ^ {k - 1} \binom {k + 1}{j} S_n(j)}{k + 1} \]

也是 \(O(k ^ 2)\) 递推即可

T3.LUOGUP1415 拆分数列

正着 \(dp\) 一遍求出以 \(i\) 作为结尾字符的递增序列时最小末尾的起始位置

反着 \(dp\) 一遍求出以 \(i\) 作为起始字符的递减序列时最大末尾的结束位置

注意正着 \(dp\) 结束后可能会有前导零, 我们可以贪心的将前导零分到最后一个数字的前面, 因为这样不会改变大小, 但是如果把这些零分到前面的数字后面会使前面的数字变大, 但又因为要小于最后一个数字所以会使答案变劣

最终复杂度 $O(n^3) $

可以预处理出 \(lcp\) 让复杂度降到 \(O(n ^ 2)\)

T4.BZOJ1725 [USACO06NOV]玉米田Corn Fields

状压\(DP\)

\(f_{i,S}\) 表示考虑了前 $i - 1 $ 行, 第 \(i\) 行的状态为\(S\)

预处理一下哪些状态有相邻的草

然后暴力枚举母集, 大力转移就好了

复杂度 \(O(3^n \cdot n)\)

T5.BZOJ1226[SDOI2009]学校食堂

\(f_{i,k,S}\) 表示前 $ i - 1 $ 个同学已经吃了, 上一吃的同学的位置和 \(i\) 同学的位置的差值为 \(k, i\) 同学的后面 \(7\) 个同学的状态为 \(S\)

但是有个很严重的问题我们怎么保证前 \(i - 1\) 个同学都吃了呢 ? 我们只要保证我们转移是合法的就可以了, 所以可能会出现 \(f_i\)\(f_i\) 中的状态转移

所以我们枚举 \(S\) 的时候要从小到大枚举保证不会循环转移

关于转移的话, 我们枚举一下下一个选 \(i\) 号同学后面的第 \(j\) 个同学

  • \(f_{i, k, S} \to f_{i + 1, S >> 1, k - 1}\)\(S \& 1 = 1\)
  • \(f_{i,k,S} \to f_{i,j,S|1<<j}\)\(S\&1\ne1\)

注意能够选的范围是随着你选的人而实时更新的

T6.BZOJ4555[HEOI2016/TJOI2016]求和

\[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ i S(i,j)\times 2^j \times j! \]

求上述式子的值, \(n \le 10^5\)

首先我们得知道当 \(i < j\) 时 $S(i,j) =0 $

所以为了方便我们修改一下上界 \[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n S(i,j)\cdot 2^j \cdot j! \] 用第二类斯特林数的公式展开一下 \[ S(i, j) = \frac{1}{j!} \cdot \sum _ {k = 0} ^ j (-1) ^ k\cdot \binom{j}{k} \cdot (j - k) ^ i \]

\[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n 2^j \cdot \sum _ {k = 0} ^ j (-1) ^ k\cdot \binom{j}{k} \cdot (j - k) ^ i \] 交换求和顺序 \[ f(n) = \sum_{j = 0} ^ n 2^j \cdot \sum _ {i = 0} ^ {n} \sum _ {k = 0} ^ j (-1) ^ k \frac{j! \cdot (j - k)^i}{k! \cdot (j - k) !} \]

\[ f(n) = \sum_{j = 0} ^ n 2^j \cdot j! \cdot \sum _ {i = 0} ^ {n} \sum _ {k = 0} ^ j \frac{(-1) ^ k\cdot (j - k)^i}{k! \cdot (j - k) !} \]

\[ f(n) = \sum _ {j = 0} ^ {n} 2^j \cdot j! \cdot \sum_{k = 0} ^ j \frac{(-1) ^ k}{k!} \frac{\sum_{i = 0} ^ {n} (j - k)^i}{(j - k)!} \]

然后设 \[ h(i) = \frac{(-1)^i}{i!} \]

\[ g(i) = \frac{\sum_{j = 0} ^ ni^j}{i!} = \frac{i^n - 1}{(i - 1)i!} \] 特别的关于边界 \[ h(1) = -1, g(0) = 1, g(1) = n + 1 \] 然后 \[ f(n) = \sum _ {j = 0} ^ n 2^j \cdot j! (h * g)(j) \] 跑一遍 \(NTT\) 就好了

T7.LUOGUP1070 道路游戏

\(DP\) 很裸

\(f_i\) 表示第 \(i\) 时刻的最大收益

直接枚举一个时间, 枚举当前时刻在哪个工厂, 往后走几步

则有转移 \[ f_i - c_x + calc(x, i, p) \to f_{i + p} \] 关于 \(calc(x,i,p)\) 表示从在 \(i\) 时刻从 \(x\) 往后走 \(p\) 步的收益, 维护一个前缀和就可以 \(O(1)\) 求出来了

复杂度的 \(O(n ^ 3)\) , 那单调队列搞一搞可以优化成 $ O( n ^ 2 ) $

T8.BZOJ1047 [HAOI2007]理想的正方形

先拿 \(a\) 个单调队列维护一下每行的最值, 并且只考虑 \(n\)

然后把这些单调队列的队头看成一个元素, 用另外一个单调队列去维护这些队头, 从第一行扫到最后一行

然后再移动列的指针维护一下每一行的单调队列的队头就好了, 这样一直循环下去

复杂度 \(O(ab)\)

T9.LUOGUP2219[HAOI2007]修筑绿化带

把每个点的权值看成以这个点为左上角的 \(c \times d\) 的矩阵内的元素的和

然后按照 \(T8\) 的方法搞一下就好了

但是要注意一下边界问题

T10.BZOJ1804[SCOI2005]最大子矩阵

首先 \(O (k \cdot n^4)\) 的暴力 \(DP\) 是可以过去的

我们考虑一下正确的 \(DP\)

\(f_{i,j,S}\) 表示考虑完了前 $i- 1 $ 行选了 \(j\) 个矩阵, 第 \(i\) 行的状态是 \(S (S < 5)\) 时的最大收益

讲一下这个地方的 \(S\) 表示的含义

  • \(S= 0\) 表示这一行空着
  • \(S = 1\) 表示这一行选了第一列, 第二列空着
  • \(S = 2\) 表示这一行选了第二列, 第一列空着
  • \(S = 3\) 表示这一行两个都选了并且这两个都来自同一个矩阵
  • \(S = 4\) 表示这一行两个都选了但这两个来自两个不同的矩阵

知道了状态, 转移就大力讨论一下就好了

如果只有一列的话, 那就把第二列中所有的元素都看成 \(0\) 就好了

注意 : 这个状态的精髓就在于在第 \(i\) 选择的元素, 可以和之间的拼起来, 而不增加矩阵的个数

复杂度 \(O(nk)\)

T11.LUOGUP4918信仰收集

我们可以把瞬移拆成走 \(a\) 步和走 \(b\) 步, 然后考虑 \(dp\)

\(f_{i,k}\) 表示到第 \(i\) 个点还剩 \(k\) 步的最大收益

然后直接在 \(DAG\)\(dp\) 就好了

注意一定要拓扑排序, 不然转移顺序会出问题

复杂度 \(O(n \cdot b)\)

T12.BZOJP1925[SDOI2010]地精部落

\(f_{i, j, 0/1}\) 表示考虑前 \(i\) 个数, 最后一个数为 \(j\) 并且它和上一个数组成的序列是上升或者下降的总方案数

我当时就只想到了这一步, 但是我否定了它, 觉得只考虑前 \(i\) 个好像并不能考虑到所有方案, 但实际上\(f_n\) 是考虑到所有的数了的, 所以并没有问题

然后有转移 \[ f_{i - 1, k, 0} \to f_{i,j, 1} | k < j \] 但考虑到其实你把 \(i \to n + 1 - i\) 会发现其实上升和下降其实是等价的 \[ f_{n, i, 1} = f_{n, n + 1 - i, 0} \] 所以转移变成了 \[ f_{i - 1, i - k, 1} \to f_{i, j, 1} | k < j \] 所以其实最后那一维 \(0/1\) 是多余的

这样复杂度是 $ O(n ^ 3) $ 的

前缀和优化一下就变成了 $ O (n ^ 2) $ 了

T13.BZOJ3126[USACO13OPEN]照片Photo

为啥大家都说这个题是差分约束黑人问号

考虑 \(dp\) , 设 \(f_i\) 表示必须选择第 \(i\) 个点的最优解

然后我们维护一个 \(In[i], Out[i]\)

\(In[i]\) 表示覆盖第 \(i\) 个点的线段的左端点的最小值 - 1

\(Out[i]\) 表示右端点小于 \(i\) 的线段的最端点的最大值

能够所有能够转移到 \(i\)\(j\) 应该满足大于等于 \(Out[i]\) 并且 大于等于 \(In[i - 1]\) 小于等于 $ In[i] $

这个东西维护一个单调队列就好了

T14.LUOGUP2698 [USACO12MAR]花盆Flowerpot

你可以二分一下然后在用单调队列维护一下最大最小值

复杂度 $ O(nlogn) $

但是我们考虑一个更优秀的做法

我们先确定一个左端点, 然后把右端点一直向右移动, 移动到左右端点组成的区间满足条件, 然后移动左端点, 直到不符合条件, 然后跟新答案, 然后这样反复进行下去, 不断的更新答案就好了

可以证明这是对的

复杂度 $ O(n) $

T15.BZOJ4033[HAOI2015]树上染色

考虑 \(dp\)

我一开始想得是 \(f_{i,j}\) 表示以 \(i\) 号节点为根的子树中选 \(j\) 个黑色节点的这颗子树的答案

但是这个 \(dp\) 是有后效性的, 我们考虑换一下状态

\(f_{i,j}\) 表示考虑以 \(i\) 号节点为根的子树中的所有边整颗树的最优贡献

这样就没问题了, 然后我们树上背包一下

注意树上背包的时候要在更新子节点的子树大小之前 \(dp\) , 这样可以保证复杂度的正确性

为什么呢, 这样的话相当于每个节点都只会在 \(LCA\) 处被枚举到, 所以 \(dp\) 的过程相当于枚举了树上的两两点对复杂度为 $ O( n ^ 2 ) $

T16.LUOGUP1410子序列

比较有趣的一道 \(dp\)

我们设 \(f_{i,j,0/1}\) 表示考虑了前 \(i\) 个数字第一个/第二个集合选了 \(j\) 个另一个集合结尾数字的最小值

对于 $ f_{i, j, S} $ 有转移

\(T = S \ xor \ 1\)

  • $f_{i + 1, j + 1, S} = min { f_{ i, j, S } }     if   a_{i + 1} > a_i $
  • $f_{i + 1, i - j + 1, T} = min { a_i }     if   a_{i + 1} > f_{i, j, S} $

相当于在两个串当中相互转换

T17.BZOJ1296[SCOI2009]粉刷匠

考虑到行与行之间互不影响, 我们考虑预处理每行的最优解

\(h[j][k][0/1]\) 表示对于每一行的前 \(j\) 列, 刷了 \(k\) 次, 这一行的第 \(j\) 列刷的是红色或蓝色的最优解

转移显然

\(S (0 / 1), T = S \ \ xor 1\), 行号为 \(i\)

  • \(h[j][k][S] = max(h[j - 1][k][S], h[j - 1][k - 1][T]) + (s[i][j] == S)\)

\(g[i][j]\) 表示第 \(i\) 行刷了\(j\) 次的最优解, \(f[i][j]\) 为前 \(j\) 行, 刷了 \(i\) 次的最优答案

则有转移

  • \(f[i][j] = max(f[i - k][j - 1] + g[j][k])\)

总复杂度 \(O(n \cdot m^2 + Tnm)\)

T18.BZOJ4005[JLOI2015]骗我呢

组合数 + 神仙容斥, 见 Link

T19.BZOJ1190[HNOI2007]梦幻岛宝珠

考虑到每个重量都可以写成 \(a \times 2^b\) 的形式

我们考虑把 \(b\) 相同的宝石放在一起先 \(dp\) 一下

\(f[i][j]\) 表示 \(b = i\) 时, 选出来的宝石的 \(a\) 值的和为 \(j\) 的最大收益, 这个东西跑一下背包就好了

问题在于如何合并

我们再设 \(g[i][j]\) 表示选出来的宝石的重量形如 \(2^i + w \& ((1<<i) - 1)\) 时的最大收益

有转移 : \[ g[i][j] = max \{f[i][j - k] + f[i - 1][min(2 \times k + (w >> i - 1) \& 1, \sum a_i)]\} \] \(PS:\) 注意更新答案的时候要保证状态合法, 因为这个我WA了一年

T20.BZOJ4813[CQOI2017]小Q的棋盘

\(WA\) 又膜了 \(Edt\) 的题解, 我太菜辣, 每天被暴打

首先一个 \(dp\) 数组是没办法表示全部的状态的

我们设 \(f[i][j]\) 表示当前到了 \(i\) 节点, 并且这个子树中走了 \(j\) 要回到 \(i\) 的最大覆盖点数

\(g[i][j]\) 则表示不需要回到 \(i\) 点的最大覆盖点数

则有转移 \[ g[i][j + k + 1] = max\{f[i][k] + g[v][j]\}\\ g[i][j + k + 2] = max\{g[i][k] + f[v][j]\}\\ f[i][j + k + 2] = max\{f[i][k] + f[v][j]\} \] 啊啊啊啊啊啊, 我好菜啊

T21.BZOJ4987Tree

首先我们得知道一个结论

选出来的 \(k\) 个节点一定是一个联通块, 并且答案就是这个联通块中的边权和 \(\times 2\) 减去直径

然后又被 \(Edt\) 秒掉了

因为我不会, 只好去抄一波题解了

考虑 \(dp\) , 设 \(f[i][j][0/1/2]\) 表示在以 \(i\) 为根的子树中选出 \(j\) 个节点的并且在其中确定了 \(0/1/2\) 个直径端点的最优解

转移方程如下 : \[ f[i][k][0] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][0] \\ f[i][k][1] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][1] \\ f[i][k][0] + f[son_i][j][1] + w_i \to f[i][k + j][1] \\ f[i][k][1] + f[son_i][j][1] + w_i \to f[i][k + j][2] \\ f[i][k][2] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][2] \\ f[i][k][0] + f[son_i][j][2] + 2 \times w_i \to f[i][k + j][2] \]

T22.LUOGU2915[USACO08NOV]奶牛混合起来Mixed Up Cows

裸的状压 \(dp\) , 设 \(f[S][i]\) 表示考虑了的牛的集合为 \(S\) , 并且最后一个考虑的为 \(i\)

直接转移就好了 \[ f[S][i] \to f[S \cup \{j\}][j], |h[i] - h[j]| > k \]

T23.BZOJ1293 [SCOI2009]生日礼物

\(T14\) , 拿两个指针扫一下就好辣

T24.BZOJ1855[SCOI2010]股票交易

先考虑暴力 $O(n^3) $ 的 \(dp\)

\(f[i][j]\) 表示考虑了前 $ i $ 天, 手上持有 \(j\) 个股票的最大收益

然后有转移 \[ f[i][j] = f[i - 1][j] \\ f[i][j] = - AP[i] \times j \ \ \ \ \ if(j \le AS[i]) \\ f[i][j] = max\{ f[i - W - 1][j] + AP[i] \times (k - j) | k \in [max(0, j - AS[i]), j]\} \\ f[i][j] = max\{ f[i - W - 1][j] + BP[i] \times (k - j) | k \in [min(j + BS[i], MaxP)]\} \] 发现能转移的区间长度是固定的, 直接单调队列搞一下就好了

详见滑动窗口

T25.BZOJ4591[SHOI2015]超能粒子炮·改

这题比较有趣, 题意就是求一下下面这个式子的值 \[ \sum_{i = 0}^k \binom{n}{i} \pmod{2333} \ \ n, k \le 10^{18} \] 考虑卢卡斯定理, 那么式子变成了这样(设 \(P = 2333\)) \[ \sum_{i = 0} ^ k \binom{n \% P}{i \% P} \cdot \binom{\frac{n}{P}}{\frac{i}{p}} \pmod{P} \] 因为模运算是有循环节的, 考虑把相同的部分提出来, 那么变成了这样 \[ \sum _ {j = 0} ^ {p - 1} \binom{n \% P}{j} \sum _ {i = 0} ^ {\frac{k}{P} - 1} \binom{\frac{n}{P}}{i}+ \binom{\frac{n}{P}}{\frac{k}{P}} \cdot\sum _ {i = 0} ^ {k \% P} \binom{n \% P}{i} \] 然后我们设 \(f[n][k] = \sum_{i = 0} ^ k \binom{n}{i}\)

然后上述式子就变成了 \[ f[n][k] = f[n \% P][p - 1] \cdot f[\frac{n}{P}][\frac{k}{P} - 1] + \binom{\frac{n}{P}}{\frac{k}{P}} \cdot f[n \% P][k \% P] \] 然后这个是个递归式, 就递归一下就好了

我们可以先处处理出 $n, k < P $ 的 \(f\) 值, 那么递归条件就是 \(n < P \ \ and \ \ k < P\)

注意当 \(k < 0\) 时, 这个式子的值是 \(0\)

T26.BZOJ5278[USACO18OPEN]Out of Sorts Gold

我又再一次的抄了题解, 太菜辣

然而看题解还看不懂, 最终在 \(Edt\) 的帮助下我终于搞明白了这道题

考虑一下题面里给的那个东西到底在干嘛, 其实每进行一次这个操作, 对于一个前缀 \([1, r]\) 把排序后本不在这个区间内值移到后面这个 \([r + 1, n]\) 去, 把一个小的换进来

所以我们直接对于每一个前缀的不属于这个前缀的数的个数取个 \(max\) 就好辣

T27.BZOJ5280[Usaco2018OPEN]Milking Order

假如我们不考虑是否合法的问题

我们要知道这道题其实做一个 \(Toposort\) 就好了

那么其实不合法的情况就是这个图里有环, 我们考虑二分一个位置使得将前面所有的边都加入图中都不产生环就好了

T28.BZOJ5281[Usaco2018 Open]Talent Show

\(01\) 规划裸题

二分 + 背包就好辣