【2018~2019 Multi-University Training Contest 9】题解

补补吉老师的题,倒序补题。

Rikka with Segment Tree

题意:设$f(i,n)$为$n$个点的线段树代表$[i,i]$区间的这个点的深度(根节点深度为$1$),求$\sum_{i=L}^R \sum_{i=1}^n f(i,n)\ast i$。

数据范围:$1\leq L\leq R\leq 10^{18}$。

特殊说明:线段树的建树方式规定为$[l,r]$的儿子为$[l,\lfloor \frac{l+r}{2}\rfloor],[\lfloor \frac{l+r}{2}\rfloor+1,r]$。

做法:一道推式子题。。。

首先$L,R$独立,所以只用考虑$\sum_{i=1}^N \sum_{i=1}^n f(i,n)\ast i$。

令$g(1,n)=\sum_{i=1}^n f(i,n)\ast i$。

考虑$g(1,n)$怎么算。

方便地,设$mid=\lfloor \frac{l+r}{2}\rfloor$,$A(n)=\frac {n(n+1)}{2}$,$fl(n)=\lfloor \frac{n}{2} \rfloor$。

假设当前在$[l,r]$区间里,

$g(l,r)=g(l,mid)+g(mid+1,r)+mid\ast \sum_{i=mid+1}^r dep[i]+A(r-l+1)$。

边界是$g(l,l)=l$。

发现这个东西实际与$l,r$无关,只跟长度有关。所以可以重新令$g(n)=\sum_{i=1}^n f(i,n)\ast i$,$f(n)=\sum_{i=1}^n dep[i]$。

那么$g(n)=g(fl(n+1))+g(fl(n))+fl(n+1)\ast f(fl(n))+A(n)$。

两边同时$\sum$,得

$\sum_{i=1}^n g(i)=\sum_{i=1}^n g(fl(i))+\sum_{i=1}^n g(fl(i+1))+\sum_{i=1}^n fl(i+1)\ast f(fl(i))+\sum_{i=1}^n A(i)$。

左边即为我们要求的,看看右边咋办。

设$G(n)=\sum_{i=1}^n g(i)$,$B(n)=\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$。

讨论$n$为奇偶,先假设$n$为奇。

有$G(n)=g(0)+2G(fl(n))+2G(fl(n))+g(fl(n+1))+\sum_{i=1}^{fl(n)}(2i+1)f(i)+\frac{1}{2}\sum_{i=1}^n i\ast (i+1)$

$=4G(fl(n))+G(fl(n+1))-G(fl(n))+2\sum_{i=1}^{fl(n)} if(i)+\sum_{i=1}^{fl(n)}f(i)+\frac{1}{2}(A(n)+B(n))$

$=3G(fl(n))+G(fl(n+1))+2\sum_{i=1}^{fl(n)} if(i)+\sum_{i=1}^{fl(n)}f(i)+\frac{1}{2}(A(n)+B(n))$

设$F(i)=\sum_{i=1}^n f(i),H(i)=\sum_{i=1}^n if(i)$。

$G(n)=3G(fl(n))+G(fl(n+1))+2H(fl(n))+F(fl(n))+\frac{1}{2}(A(n)+B(n))$

$H$和$F$同理推一下,偶数就利用$G(n)=G(n-1)+g(n)$推一下,还是差不多。

于是就做好了。至于复杂度的话,你会发现每一层都比上一层多$1$,总共$log$层,所以总复杂度是$O(log^2N)$。当然,你用个$map$记忆化一下就是$O(log^3N)$了。

$std$的做法似乎是推的式子比较优秀,每次只用递归一个,用个$map$也只用$O(log^2N)$。

Rikka with Defensive Line

我九条可怜最喜欢做的一件事,就是出几何题,对自以为多开就能$AK$的人说“不”。

Rikka with Traffic Light

Rikka with Stable Marriage

题意:给你两个长度为$n$个数组$a_i,b_i$,重新排列后,希望$\sum_{i=1}^n a_i\bigoplus b_i$最大。

数据范围:$1\leq T\leq 50,1\leq n\leq 10^5,1\leq a_i,b_i\leq 10^9$。

做法:这题我们联考考了一道差不多的。

你对$a$和$b$都建出$Trie$树,然后在上面贪心地$dfs$出最大数,$dfs\ n$遍后就做完了。复杂度$O(nloga_i)$。

Rikka with Travels

题意:给你一棵$n$个节点的树,要求你选出两条路径且这两条没有交。两组路径定义为相同当且仅当这两组的路径长度一样。问你一共有多少组不同的路径组?

数据范围:$1\leq T\leq 300,1\leq n\leq 10^5$。

做法:我的做法跟官方题解有点略微区别。

首先有个显然的性质,如果$(x,y)$这个二元组存在,则对于$1\leq i\leq x,1\leq j\leq y$,$(i,j)$也都存在。

于是我考虑直径那一套理论。你先将直径的一端作为树的根。显然地,直径和次长不相交的链肯定是非常好用的。然后你想着把次长不相交的链拉长,即不断截去直径的一段这样子,这样截取有两种选择,分别和直径的两端都来一次。然后你对于每种长度维护出$(x,y)$的$y$的最大值,看成二维平面上的面积并,扫描线$+$线段树即可。复杂度是$O(nlogn)$。

Rikka with Coin

题意:$n$件商品,都有个价格。你手上有面值为$10,20,50,100$的硬币,问你最少需要多少枚硬币,才能表示出所有商品的价格。

数据范围:$1\leq T\leq 500,1\leq n\leq 100,1\leq w_i\leq 10^9$。

做法:你感觉一下,就知道大部分的钱还是要用$100$表示。然而到底要剩下多少用$10,20,50$表示你并不知道。于是随便猜个$300$,以$10,20,50$做一个$300$容量的背包。最后暴力枚举一下就不管了,猜一猜就是对的。复杂度是$O(300\ast n\ast p)$,这里的$p$是有几种$10,20,50$的选法。

Rikka with Game

题意:给你一个长度为$n$的串,两人博弈,操作有两个,一是选择一个字符,将它$+1$,即$a$变$b$,$b$变$c$,…,$z$变$a$。二是结束博弈。先动手的那个人希望字符串最小,后动手的希望最大。问最终的串。

数据范围:$1\leq T\leq 100,1\leq |s|\leq 100$。

做法:签到题吧。

你随便感觉一下,假如第一位是$z$,那肯定会把这位变成$a$,然后后手的再变成$b$,先手的就会结束游戏了。如果不是$y$,显然怎么动手都不优,所以先手的会直接结束。否则递归照样贪心即可。复杂度$O(n)$。

Rikka with Geometric Sequence

题意:给你一个$n$,问$1$~$n$的排列中有多少个子序列能组成等比数列。

数据范围:$1\leq T\leq 1000,1\leq n\leq 5\ast 10^{17}$。

做法:大暴力题。

考虑枚举公比$a$,发现这时的贡献就是$\sum_k \phi(k)\lfloor\frac{n}{a^{k-1}}\rfloor$。所以总的式子就是$\sum_{a=2}^n \sum_k \phi(k)\lfloor\frac{n}{a^{k-1}}\rfloor=\sum_{k=1}^n \phi(k)\sum_{a=2}^{n^{\frac{1}{k-1}}} \lfloor\frac{n}{a^{k-1}}\rfloor$。

$k=1$和$k=2$都可以直接$O(1)$算,$k=2$可以整除分块+杜教筛,其余的暴力算。这样的复杂度瓶颈就在杜教筛了,你大概分析一下是$O(n^{\frac{5}{18}})$?可能我分析有点问题,反正能过就是了。

Rikka with Mista

题意:一个数的权值定义为这个数出现的$4$的个数。现给你$n$个数,问你所有子集和的权值之和。

数据范围:$1\leq T\leq 4,1\leq n\leq 40,1\leq w_i\leq 44444444$。

做法:好毒啊,有点卡常的。

首先看到$40$这个数据范围,可以由此想到$meet\ in\ the\ middle$。我们求出两组分别的子集和后,按位考虑(最多$10$位),于是有数这一位有$4$当且仅当$4\ast 10^i\leq x< 5\ast 10^i$。于是直接利用单调性做是$O(2^{\frac{n}{2}}\ast \frac{n}{2}\ast 10)$,显然过不了。考虑优化排序的过程,显然可以看这一位是几然后分别放进对应的$vector$里,然后归并一下。于是复杂度就变成$O(2^{\frac{n}{2}}\ast 10\ast 10)$,最后再卡卡常就能过了,这里卡常可以每次按位考虑的时候先预处理它们这一位的数,然后将取模运算变成三目加法运算之类的。

Rikka with Cake

题意:给你$n$条射线,问你将平面分成了几个部分?

数据范围:$1\leq T\leq 100,1\leq r,c\leq 10^9,1\leq k\leq 10^5$。

做法:咋回事啊,我写得咋这么复杂啊。

很明显就是求交点数,简单地想到离散化维护$x$坐标扫描线。然后然后,我没想到把朝下的射线理解成$+1$的朝上射线和$-1$的朝上射线,于是我开始了分类讨论,如果朝上的和朝下的有交,就要减去交的贡献,于是代码就很长了。。。

Rikka with Quicksort

题意:
$$
g_m(n) =
\begin{cases}
0, & \text{if $n\leq m$ } \[2ex]
n-1+\frac{1}{n}\sum_{i=1}^n (g_m(i-1)+g_m(n-i)), & \text{if $n>m$}
\end{cases}
$$

求$g_m(n)$。

数据范围:$1\leq T\leq 10,1\leq m\leq n\leq 10^9$。

做法:完蛋了啊,这道题居然不会做。

显然是要推式子。观察一下后,发现
$$
g_m(n) =
\begin{cases}
0, & \text{if $n\leq m$ } \[2ex]
n-1+\frac{2}{n}\sum_{i=0}^{n-1} g_m(i), & \text{if $n>m$}
\end{cases}
$$

然后我希望通过设$S[n]=\sum_{i=0}^{n-1} (g_m(i))$的办法搞出一些东西,发现并不能很好地弄出来,于是看了下题解,发现还是要差分推导的。。。

以下推导均假设$n>m$。

整理式子,有$(g_m(n)-(n-1))\frac{n}{2}=\sum_{i=0}^{n-1} (g_m(i))$。

同时也有$(g_m(n+1)-n)\frac{n+1}{2}=\sum_{i=0}^{n} (g_m(i))$。

两式做差,得$g_m(n)=\frac{n+1}{2}g_m(n+1)-\frac{n}{2}g_m(n)-n$。

稍微整理一下,即$(n+2)g_m(n)+2n=(n+1)g_m(n+1)$。

下一步数学推导我就没想到了,可能数列白学了。

$(n+1)(n+2)$除一下,有$\frac{g_m(n)}{n+1}+\frac{2n}{(n+1)(n+2)}=\frac{g_m(n+1)}{n+2}$。

接下来就很显然了,转换成两个新数列,然后$\frac{2n}{(n+1)(n+2)}$这个东西随便裂项一下就完事了,最后会推出这样一个东西。

$g_m(n)=\frac{m(n+1)}{m+2}+2(n+1)\sum_{i=m+2}^n\frac{1}{i}-(2n-2)+(n+1)\frac{2m}{m+2}$.

仔细观察一下,发现只有个调和级数要算了。直接$ln_n+C$不知道能不能过,反正分段打表看起来就比较科学。

Rikka with Badminton

Rikka with Time Complexity

Rikka with Bubble Sort

Rikka with Line Graph

Rikka with Treasure

Rikka with Spanning Tree

Rikka with Rain

Rikka with Stone-Paper-Scissors

Rikka with APSP

Rikka with Seam

Rikka with Nash Equilibrium