Virtual NOIP 2018 Day1 总结

## 上午 ### T1 回文切割 $10$分：最朴素的暴力。其实这题写暴力也是有一定难度的，要枚举分点。 $30$分：好一点的暴力，或者$\text{O}(n^3)$。 $60$分：$\text{O}(n^3)$。 先计算$f[i][j]$表示以$i$为中心、长度为$2j$（即从$i-j$到$i+j-1$）的回文串的代价。其中若$a[i-j]=a[i+j-1]$，则$f[i][j]=f[i][j-1]$；否则从$a[i-j]$和$a[i+j-1]$两者中选择一个权值较小的来修改，即$f[i][j]=f[i][j-1]+\min(w[i-j],w[i+j-1])$。 再计算$g[i][j]$表示把区间$[i,j]$变为合法（即若干个回文串的拼接）的代价，$g[i][j]=\min(f[\frac{i+j+1}{2}][\frac{j-i+1}{2}],g[i][k]+g[k+1][j])$，即枚举是把整段直接变为回文还是分割变成回文。最后取$g[1][n]$作为答案即可。 $100$分：$\text{O}(n^2)$。上面的$g$数组状态冗余，实际上由于计算$g$数组时，发生决策仅仅是在使用$f$数组的值时，因此这样计算浪费大量时间和空间。 我们考虑简化枚举方式。我们重新定义状态$g[i]$表示把区间$[1,i]$变为合法字符串的最小代价，我们在状态转移时只需枚举最后一次（即最右边的）分割点的位置，即枚举$k$，对$[k+1,i]$直接转为整个回文串，则$g[i]=\max\left( g[k],f[\frac{i+k}{2}+1][\frac{i-k}{2}] \right)$。 这题也是类似于$f[i][j]=\max(f[i][k]+f[k+1][j])+w$的四边形不等式$\text{dp}$，为什么可以压为一维呢？因为这题中转移没有代价，即$w=0$，因此不需要考虑转移的次数，如一段字符串分成三段并不会比分成两段更劣。这样我们就可以用更低维的状态完成$\text{dp}$。 ### T2 ~~膜~~ 模 $50$分：$\text{O}(2^n)$直接枚举所有子集，计算所有元素乘积即可。 $70$分：下述做法中，如果先求所有数的逆元，并且开$\text{cnt}$数组记录下每一个乘积的子集个数，即得$70$分。 然而，昨天我交程序的时候忘记按数据分治了，对所有的数据点都应用了这种方法，导致$n\le 18$的所有点都$\text{RE}$（数组下标越界）。因此，**按数据分治一定要做好！** $100$分：$n\le 35$，恰好比$50$分的数据范围多了一倍。考虑$\text{Meet in the middle}$。 把每一个子集拆分成左右两部分。考虑左半中的子集和右半中的子集何时相乘能够得到$r$，若设左半中的子集的元素之积为$x$，右半中的子集的元素之积为$y$，则两边相乘得到$r$，即$xy\equiv r \pmod{p}$，可知$y\equiv x^{-1}r\pmod{p}$。因此我们先在左半进行上述枚举，得到所有的乘积；再对右半进行枚举，对每一个$y$，给答案累加上左半中$x^{-1}r$的个数即可。 累加时有技巧。考虑到$p\le 10^9$，如果计算完所有数的逆元，显然会$\text{TLE+MLE}$。因此逆元应该即用即算。 而如果开一个$p$大小的数组统计每一个$x$出现的个数，显然会$\text{MLE}$。因此我们找出现次数应该现用现找，即把所有的$x$存到一个数组中，排序后每次用二分查找即可知道出现次数。 ### T3 摘苹果 天啊，我太naive了……没有考虑到正确的策略…… 运用贪心思想，我们可以把剪断操作发生的时间分别推迟到某个$b_i$。 对所有苹果按照$b$进行排序，然后从小到大枚举苹果。枚举到某一个苹果时，如果这个苹果当前还没有被摘掉，那么它必须在$b_i$时刻被摘掉。由于这一次剪断操作必须发生，因此我们想要摘掉尽量多的苹果。我们向上寻找它的祖先节点，找到最靠近根节点的、可以进行采摘操作的节点进行采摘。 如果直接模拟上述过程，可以实现$\text{O}(n^2)$的复杂度，从而得到$40$分。 上述过程为什么慢呢？因为在向上寻找祖先节点的过程中，要求出这棵子树没摘掉的苹果的$a$的最大值，并且摘除苹果时还要把所有叶子节点标记为已删除。 我们考虑加速这一过程。 1. 如何维护苹果能否被摘除？考虑将每个苹果处理为两个事件，即成熟事件和腐烂事件，把事件按时间顺序排列并处理。 由于我只学过区间操作的数据结构，而一棵子树的节点编号是不连续的，因此我们要进行一次$\text{dfs}$，用$\text{dfs}$序重新编号即变为连续区间内的操作，查询时直接查询区间最大值即可。由于已经摘下的苹果的成熟时间一定比当前早，因此不需要考虑他们对判断结果的影响。 2. 如何标记苹果已经被摘除？ 同样可以使用线段树的区间加操作。 这样，时间复杂度就可以降为$\text{O}(n\log n\log n)$。 ## 下午 ### T1 数列 根据输入数据的提示，进行~~疯狂的~~分类讨论。 首先判断$c\ge d$的情况，直接输出$0$。 $10$分：直接计算等差数列的情况即可。对$b$的取值进行讨论。如果$b\le 0$且$c<d$，则无解；否则计算$\lceil \frac{d-c}{b} \rceil$即为答案。 接着如果有解，由于是指数级增长，因此很快就会达到$d$，直接枚举即可。 ### T2 子集和 %%% [cultry](https://www.luogu.org/space/show?uid=76655) 37行AC 没想到这题码量其实不太大。 先证明数列好的充要条件是，将数列排序后，$\forall i\in [1,n],i\in \mathbb{N},a_{i}\le S_{i-1}+1 $。（证明过程略，用数学归纳法可证。） $70$分：先把数列排序。现在设$f[i][j]$表示前$i$个数中的、总和为$j$的好数列的个数。 若$j<a[i]-1$，则$f[i][j]=f[i-1][j]$； 若$j\ge a[i]+1$，则$f[i][j]=f[i-1][j]+f[i-1][j-a[i]]$。 于是，我们给所有$j\ge a[i]+1$加上$f[i-1][j-a[i]]$。 时空复杂度$\text{O}(n^3)$。 $100$分： 考虑优化时空复杂度。 首先空间当然可以用滚动数组优化。 接着考虑时间。 先复习一下[绝美的挣扎的题解](https://www.luogu.org/blog/Taki/solution-struggle)。在这道题中，我们是如何处理状态的第二维的呢？如果第二维超过$mk$，我们就强令它等于$mk$，因为所有大于等于$mk$的状态都是同等的，都可以转移到所有状态中。 这题的状态也是如此。如果一个$j$已经大于$\max\left\{a_{i}\right\}+1$，那么我们就可以令$j=\max\left\{a_{i}\right\}+1$,即用$\max\left\{a_{i}\right\}+1$代表所有更大的状态，因为他们对研究的问题都已经够大了。就好比周子凯、毕克、金策、吴凯路这几位大佬都太强了，对我这种蒟蒻来说，都是“极强”的概念，不必再区分。 有了这个优化，时间复杂度降到$\text{O}(n^2)$，空间复杂度降到$\text{O}(n)$，可以通过所有数据。 ### T3 棋盘 $10$分：直接$\text{dfs}$爆搜，不需要中途剪枝。 $30$分：对于$n\le 2$的情况，分别计算出一维情况的方案数再扩展到二维即可。 $100$分：撞鸭$\text{dp}$。每一行的状态只和前两行有关系，因此我们要保存前面两行的状态。$f[i][s_1][s_2]$表示第$i$行，上一行的状态是$s_1$，上二行的状态是$s_2$时的方案数。 每一行的状态无需枚举$2^m$个，可以先降维打击到一维，对行进行处理。处理后存储合法状态，转移时只从合法状态进行转移即可。