Streaming#5 题解报告
T1.珠
题目大意 : 给你一个长度为\(n\)的数字环, 你可顺时针或者逆时针选择一个子序列, 满足子序列的以\(2\)开头, 后面的数字都是\(3\), 求最长子序列
题解 : 我们考虑对于每一个数字为\(2\)的位置向左边和右边二分一个位置, 使得这个位置到数字\(2\)中间全是\(3\), 所以我们必须得先处理处两个数组\(preL, preR\), 表示从一个为\(3\)的位置向左向右全部都是\(3\)的结束位置, 这样就可以二分了, 特别的如果你向右边二分出的位置为这个序列的末尾, 那你必须从这个序列的开头再次二分一个位置, 因为这个是一个环, 头尾可以相接
复杂度为\(O(nlogn)\)
代码 :
1 |
|
T2.免农
题目大意 : 一开始你有两个免子, 下一个时刻, 你的免子会变成当前时刻的两倍, 然后我们会将这些免子分为若干组, \(k\)个为一组, 特别的如果存在一组, 这一组里只有一个免子, 那么这个免子就会死去, 求\(n\)时刻时免子的个数对\(p\)取余的结果
题解 :
- 考虑如果\(k\)为偶数的话, 是不会存在单个免子为一组的, 所以最后的答案就是\(2^{n + 1} \% p\)
- 如果\(k\)为奇数的话, 当\(2^{q} \% k == 1\)的话那么在\(q\)时刻之后, 就不会有免子再会落单了, 并且可以证明在\(k\)个时刻以内, 一定存在一个时刻\(t\), 使得\(2^t \% k == 1\), 所以直接模拟就好了
复杂度\(O(min(k, n))\)
代码 :
1 |
|
T3.高维网络
题目大意 : 现在有一个\(d\)维空间, 起始坐标为\(A(0, 0, ...., 0)\), 结束坐标为\(B(a_1, a_2, ...., a_d)\), 现在有\(p\)个坐标上设有障碍, 并且每一步只能在某一个维度上走一步, 也就是说只能这样转移 : \[ (0, 0, ...., 0) -> (1, 0, ...., 0) or (0, 0,...., 0) -> (0, 1, ...., 0) \] 求从起点走到终点不经过障碍有多少种方案, 输出方案数对\(P\)取余后的结果
题解 :
我们先考虑没有障碍的情况, 从\(x(s_1, s_2, ...., s_d)\)移动到\(y(t_1, t_2, ...., t_d)\)有多少种方案, 首先我们设数组\(tmp_i = t_i - s_i\), 其后缀和为\(S\), 那么我们一定会走\(\sum_{i = 1}^{d}tmp_i\)步, 前\(tmp_1\)步我们可以任意分配就有\(C_{S_1}^{tmp_1}\)种方案, 然后我们依次分配步数就可以知道方案数为 : \[ Paths(x, y) = \prod_{i = 1} ^ {i \leq d} C_{S_i}^{tmp_i} \] 然后如果直接容斥的话复杂度为\(O(2^p \cdot d \cdot logP)\), 实测可以获得\(80\)分的好成绩
我们现在再考虑\(dp\), \(f[i]\)表示从起点到第\(i\)个障碍点并且不经过任何障碍点的方案数, 不难得出转移方程为 : \[ f[i] = Paths(A, i) - \sum_{i \ne j} f[j] * Paths(j, i) \] \(PS\) :
- 注意\(Paths(x, y)\)有方向性, 表示从\(x\)转移到\(y\)可以经过任意障碍的方案数
- 并且这个\(dp\) 的转移顺序必需是从最靠近起点\(A\)的障碍点开始转移, 不然会有问题
\(Update\) : 我们来考虑一下这个\(dp\)的正确性, 我们可能会想这样\(dp\)会不会减掉一些重复的路径, 比如说有三个点\(i, j, k\), \(i\)可以到达\(j\), \(j\)可以到达\(k\), 在转移的时候我们会将 \[ f[i] * Paths(i, k) \& \& f[j] * Paths(j, k) \] 都减掉, 这样会不会有问题呢?
实际上是不会的, 我们注意到\(f[i]\)的定义是指从\(A\)到\(i\)号障碍点不经过任何其他障碍的路径方案数, 所以\(f[j]\)中的方案数是不包括\(f[i] * Paths(i, j)\)的, 所以这样\(dp\)的正确性是有保障的, 最终复杂度为\(O(p ^ 2 \cdot d \cdot logP)\)这样的复杂度是正确的
代码 :
1 |
|
Summary
- 推容斥式子时不要想当然, 想清楚再打
水水水
咕咕咕