水题大坝的水题大赛[第一弹]题解
CYJian
2018-10-28 18:35:57
# 水题大坝的水题大赛[第一弹]题解
标算都放在页面的最下方..
## $T1$ 毒瘤之神妙的圆
首先我们发现这些点都是可以八等分对称的..(对称轴分别$x$轴/$y$轴/直线$y=x$/直线$y=-x$)
然后我们处理好一个部分就行了..
比如处理好右上角靠$y$轴的一侧,那么我们只需要枚举每一个$x \in [0, \frac{r}{\sqrt{2}}]$,然后用圆的方程$x^2+y^2=r^2$计算$y$的值就好了..
什么??$x$的范围是怎么算出来的??
也是用圆的方程$x^2+y^2=r^2$然后用$y=x$带入就可以解出来了..
## $T2$ 毒瘤之神奇进制
这道题..首先发现所有的东西都是乘起来的..然后答案要求的是十进制下的位数..
然后高一以上的$OIer$们想必第一反应都是: $log_{10}$
然后..如果不明白对数的请自行百度..顺便了解一下对数的运算性质..
然后..不用多说什么了吧..
好吧还是啰嗦一会:$C++$中有算$lg$的函数: $log10(x)$,返回值为$double$...
## $T3$ 毒瘤之神秘通道
首先这道题目给出的图是一棵树,然后走的方向是固定的..而且其他人全都走光了..
所以可以先利用拓扑序推出每一个房间有多少人走过,然后再利用拓扑序倒推算出每一个房间为起点到达出口的时间..
然后就没有了..
如果先拓扑排序然后再暴力跑一遍图的话...有可能会被卡常数..
## $T4$ 毒瘤之神$TM$菱树①
(不是前面的题目没有写部分分做法,而是本身正解就非常简单易懂..)
#### $Subtask 1$
感觉不必多说..暴力建图$+Floyd$拿走你的$10$分..
#### $Subtask 2$
也不必多说..把上述算法的$Floyd$换成$Dijkstra$即可..
#### $Subtask 3$
首先我们需要一个显而易见的结论: 一个最短路一定是倒'V'形的..当然有可能左右两边的'那一条腿'退化没了..
然后我们可以用计算器得到第$10^5$号点的层数为$448$..
只需要把所有的点的层数和每一层的位置预处理一下,然后暴力往上跳就好了..
#### $Subtask 4$
首先利用$Subtask 3$的结论，我们考虑如何快速求出一个点的层数。
首先对于一层最右边的一个点，它的编号一定是$\frac{i \times (i + 1)}{2}$。那么扩展到其他点的话，如果用二次方程求根公式算的话$i$就会是一个小数。然后我们把它向上取整就是它的层数了。
然后已知层数和位置，那么我们可以分情况讨论一下就好了。。一共三种大家可以自行画图推一下式子。
如果令两个点的层数和在该层从左往右的位置分别为$c_u,c_v,p_u,p_v$的时候(令$c_u \ge c_v$)，就有以下几种情况：
$1:$ $c_u \ge c_v \qquad p_u \ge p_v \qquad p_u - p_v < c_u - c_v$
$2:$ $c_u \ge c_v \qquad p_u \ge p_v \qquad p_u - p_v \ge c_u - c_v$
$3:$ $c_u \ge c_v \qquad p_u \le p_v$
就是这三种了。至于为什么，留给大家思考。
## T5 毒瘤之神异之旅
#### $Subtask 1$
感觉不必多说..暴力$dfs$有请。。
#### $Subtask 2$
这个的话。。我们可以考虑一个神奇的做法:首先$N^2$计算$N$个数里面划分$K$个数的方案这个会吧。。
如果不会请出门[P1025数的划分](https://www.luogu.org/problemnew/show/P1025)。。
然后现在我们考虑如何用这个东西算。。
我们考虑连续取$k$个相同的数字$x$的该数字的答案。这样不会算重。
那么答案就是$\sum f[n-k*x][m-k]*x^p*k$
#### $Subtask 3$
这个是基于$Subtask 2$的。
只需要在计算$f[i][j]$的时候把$n$和$m$的顺序反过来就可以滚动数组了。可以参见标程。
## T6 毒瘤之神$TM$菱树②
#### $Subtask 1$
感觉不必多说..暴力建图$+Floyd(O(N^6)) / Dijkstra(O(N^4 \times log_2N^2))$拿走你的$10$分..
#### $Subtask 2$
也不必多说..把$T4$的正解偷过来暴力算每一个点的距离即可。。
复杂度$O(N^4)$。兴许$Dijkstra$也能跑过。。
#### $Subtask 3$
到这里就需要一些推理了。。
首先我们发现菱树一个性质：每一层的边权相等。
所以我们可以考虑直接计算每一层的贡献。
这样的话我们就分为两种情况：
第一种是在图中选择的两个点一个在这一层的下方，一个在这一层的上方。
根据$T4$的最短路的结论，我们可以推断出这种情况只可能通过这一层一次。
第二种是两个点都在这一层的下方。
这样一上一下，肯定要经过两次。
那么考虑直接计算贡献。
首先第一种的方案非常好求。就是这一层上面的节点个数$\times$下面的节点个数。转化为式子就是:
$$ \frac{i \times (i+1)}{2} \times (\frac{n \times (n + 1)}{2} - \frac{i \times (i+1)}{2}) $$
然后计算答案就乘上一个$i$就好了。
第二种的话。。
首先可以多画几个草图，发现需要满足右边的点到这一层的距离需要大于或等于左边的点与右边的点在该层从左往右数的相对位置的差。
事实上如果推出了$T4$的三种情况，那这个还是挺好想到的。
那么这样的话我们就考虑枚举左边的点。然后右边可以选择的点就是一个公差为$(n-i)$的等差数列。然后左边每一列的点一共有$(n-i)$个，则可以得到方案数为：
$$(n-i)^2 \times \frac{i \times (i+1)}{2}$$
然后由于需要一上一下，所以答案需要乘上一个$2 i$。
综上所述，最后的答案就是
$$\sum_{i=1}^{n-1}( \frac{i \times (i+1)}{2} \times (\frac{n \times (n + 1)}{2} - \frac{i \times (i+1)}{2}) \times i + (n-i)^2 \times i ^ 2 \times (i+1))$$
复杂度$O(N^2)$
#### $Subtask 4$
还是用上面的式子。~~也许~~可以化简一下变成$O(N)$
我们把它拆分一下:
$$\frac{n \times (n + 1)}{2} \times \sum_{i=1}^{n-1}(\frac{i \times (i+1)}{2} \times i) - \sum_{i=1}^{n-1} ((\frac{i \times (i+1)}{2})^2 \times i) + \sum_{i=1}^{n-1} (n^2-2\times i \times n +i^2) \times i ^ 2 \times (i+1))$$
$$= \frac{n \times (n + 1)}{2} \times \sum_{i=1}^{n-1}(\frac{i \times (i+1)}{2} \times i) - \sum_{i=1}^{n-1} ((\frac{i \times (i+1)}{2})^2 \times i) + n ^ 2 \times \sum_{i=1}^{n-1} (i ^ 2 \times (i + 1)) - 2\times n \times \sum_{i=1}^{n-1} (i ^ 3 \times (i+1)) + \sum_{i=1}^{n-1}(i ^ 4 \times (i+1))$$
然后发现所有$\sum$里面的东西都可以$O(N)$递推，所以答案也可以$O(N)$递推了。
标算全部都写成了变量的形式，所以时空复杂度都很小。
------
总之这套题目代码都不长，只要有思路就非常好写了。适合备战NOIP的选手们做一做。
标程由于用的是两格缩进，所以放在云剪贴版上缩进比较丑。。好在标程真的都不长。。
[T1](https://www.luogu.org/paste/89igy4fm)
[T2](https://www.luogu.org/paste/y408thxh)
[T3](https://www.luogu.org/paste/doq8kuam)
[T4](https://www.luogu.org/paste/xezvmefh)
[T5](https://www.luogu.org/paste/cuza2r0y)
[T6](https://www.luogu.org/paste/i3kph865)