CYJian的水题大赛[第四弹]题解

# CYJian的水题大赛[第四弹]题解 还是老规矩，先讲思路后放标程。 ## T1 水の造题 将会附上$20$分，$40$分和$100$分的代码。 #### ${\rm Subtask\ 1}$ 暴力枚举每一个位置做哪一个动作就好了。 #### ${\rm Subtask\ 2}$ 可以考虑dp。 我们令$f[i][j]$表示第$i$个动作做第$j$种动作的时候期望的威力。 可以得到转移为: $$f[i][j]=\sum \frac{(f[i-1][k]+a[j]+(j=next_k?a[j]+a[k]:0))}{K}$$ 其中$K$为动作种数，$k$为枚举的上一个动作。 然后就可以得到$40$分了。 #### ${\rm Subtask\ 3}$ 事实上，只需要把上述的状态转移式子用矩阵快速幂优化就好了。 可能这一部分很难写，有点超纲${\rm NOIP}$。 #### ${\rm Subtask\ 4}$ 听说。。费马小定理同样适用于矩阵快速幂。。所以造了这样一档部分分。。 #### ${\rm Subtask\ 5}$ 这里就是满分算法了。。 我们可以考虑期望值的一个简单算法: $$E(X) = \frac{\text{所有方案的贡献和}}{\text{方案数}}$$ 然后这道题的话。。方案数就是$K^N$。 然后考虑所有方案的贡献和。 这个东西的话。首先不考虑额外威力，那么每一个位置上都可以做一个动作，其他位置上随意，那么这个位置做这个动作的方案数为$K^{N-1}$，但是每一个位置都可以这么做一次，那么单个动作的威力就可以这么算: $$\sum_{i=1}^{k} a_i \times K^{N-1} \times N$$ 然后考虑额外的威力。 用差不多的方法，我们就相当于是把每两个动作捆在一起做，然后其他位置上的方案数为$K^{N-2}$，然后由于两个动作需要连续打两次，那么就只有$N-1$种占用位置的方法。那么威力就是这么算的: $$\sum_{i=1}^{k-1} (a_i+a_{i+1}) \times K^{N-2} \times (N-1)$$ 然后把上面的两个东西加起来，乘上$K^N$的逆元就好了。 以上所有的某次方均可以套用费马小定理进行简化。 ## T2 水の数列 将会附上$60$分和$100$分的代码。 #### ${\rm Subtask\ 1}$ 发现最优的方案肯定是选择数列里面的一个数字。所以可以枚举数列中每一个数字，然后暴力计算答案，然后检查选出的区间个数有没有在$l$~$r$中间就好了。 #### ${\rm Subtask\ 2}$ 这个也很简单。只需要提前$N^2$预处理出选择每一个数的答案，然后枚举选择哪一个数就可以很快得到答案了。 #### ${\rm Subtask\ 3}$ 发现这个询问每一次都是询问区间最大值，那么可以考虑使用线段树支持区间查询。 那么怎么$O(N)$计算每一个数的贡献呢？？ 我们注意到选择一个大的数得到的这些区间一定包括选择所有比它小的数的得到的区间。那么可以考虑从小到大直接递推。使用并查集记录每一个区间的大小，然后每一次选择一个比它大的数的时候把两边的数的并查集合并，然后重新计算答案贡献就好了。 具体方式可以参见标程的$Link$函数。其中$si$数组表示这段区间的大小。 然后每一次计算完每一个数字的贡献的时候只需要把它的值用线段树维护好就好了。 至于线段树，表示的就是选择一个数的时候分成的区间个数得到的得分就好了。 ## T3 水の三角 其实这道题是蒟蒻在造完菱树后魔改了一波菱树得到的产物。(首先变成有向边，然后加上横向边。) 将会附上$60$分和$100$分的代码。 #### ${\rm Subtask\ 1}$ 可以考虑先写一个枚举路线的${\rm dfs}$，然后打表/${\rm OEIS}$就好了。 #### ${\rm Subtask\ 2}$ 可以考虑设$f[i][j]$表示从顶点到第$i$层的第$j$个的方案数。 由题目给出的图可以很方便的发现转移方程为: $$f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i][j-1]$$ 然后输出$f[N][N]$就好了。 #### ${\rm Subtask\ 3}$ 可能是蒟蒻英语不好，上${\rm OEIS}$的时候都没有找到$O(N)$的递推式。 然后如果想知道有证明的做法，请看下面： ------- 如果我们把这个图顺时针旋转一下，然后把所有横向边去掉，这个图就长这个样子了：  然后可以自己查一下卡特兰数的图，有没有发现莫名很像呢？？ 然后事实上就可以使用卡特兰数去计算。 我们发现走每走一条横边就会使得卡特兰数减少一层，同时需要走的步数也会减少一步。 然后可以枚举走几条横边，然后一共需要走的步数也可以得到，这样的话从这些步数中选出横边的步数，其他的步数用来走斜边，方案数为卡特兰数。运用加法原理和乘法原理可以得到答案为: $$\sum_{i=0}^{n-1} Catalan(n-i) \times C_{2n-i-1}^{i}$$ 然后只需要预处理出卡特兰数和阶乘，然后直接用上面的式子计算就可以了。 ## T4 水の斗牛 ~~这道题就是用来给大家练习代码能力和读题能力的。~~ 此题仅需模拟就好。 下面将会附上出题人3KB的代码和验题人8KB的代码。 然而特殊性质事实上并没有什么用。 只不过一个是炸弹娱乐赛，两个没有铁板和炸弹，一个不需要考虑花色影响的特殊情况而已。 ## 代码区 这几份代码都是出题人自己写的，除了最后一题的验题人代码=-=。但是由于出题人自己用的是两格缩进，而洛谷默认四格缩进，所以代码的缩进可能不同，请见谅。简单地说，就是你谷把一些两格缩进吞成两个空格，而另一些弄成了四格缩进。。 #### T1 [${\rm 20\ pts}$](https://paste.ubuntu.com/p/966qSN8CP2/) [${\rm 40\ pts}$](https://paste.ubuntu.com/p/9ZQ785Dd7c/) [${\rm 100\ pts}$](https://paste.ubuntu.com/p/4Qqq5gCrZn/) #### T2 [${\rm 60\ pts}$](https://paste.ubuntu.com/p/tPTBHBR76C/) [${\rm 100\ pts}$](https://paste.ubuntu.com/p/CGg6F6fCQG/) #### T3 [${\rm 60\ pts}$](https://paste.ubuntu.com/p/XxhM29D97t/) [${\rm 100\ pts}$](https://paste.ubuntu.com/p/QGFYxcxxcQ/) #### T4 中间有一些英文注释，是因为怕写中文的时候到Linux上就挂了。 [出题人3KB代码](https://paste.ubuntu.com/p/3T2RwZngW4/) [验题人9KB代码](https://paste.ubuntu.com/p/jDBpCqSM4R/)