Day1

争夺圣杯

By YJMWOI，题解 By C_SUNSHINE

算法一

$n \leq 100$的部分，当然可以写一个simple的暴力啦，我们枚举所有区间，然后对每个区间求出最大值，再计算答案。

这个复杂度是$O(n^3)$的，期望得分$10$分。

算法二

上一个做法太暴力了，可以发现$\max \{a_l,a_{l+1},\cdots,a_r\} = \max \{\max \{a_l,a_{l+1},\cdots,a_{r-1}\},a_r\}$，于是我们先枚举$l$，然后升序枚举$r$每次更新最大值就好了。

复杂度$O(n^2)$，期望得分$30$分。

算法三

暴力做法已经没有什么可以优化的地方了，我们把它扔进垃圾桶。

考虑一个元素$a_x$，在哪些区间中它会成为最大值。

找到$a_x$之前第一个比$a_x$大的元素$a_L$，若没有则$L=0$，再找到$a_x$之后第一个比$a_x$大的元素$a_R$，若没有则$R=n+1$。

设$p=x-L,q=R-x$，则以$a_x$为最大值的区间一共有$pq$个（左端点在$[L+1,x]$，右端点在$[x,R-1]$）。

接着观察这些区间的长度分布，不妨设$p \leq q$，考虑长度$len$

当$1 \leq len \leq p$时，长度为$len$的区间共有$len$个（$[x-len+1,x],[x-len+2,x+1],\cdots,[x,x+len-1]$）

当$p < len \leq q$时，长度为$len$的区间共有$p$个（$[x-p+1,x-p+len],[x-p+2,x-p+len+1],\cdots,[x,x+len-1]$）

当$q < x \leq p+q-1$时，长度为$len$的区间共有$p+q-len$个（$[x-p+1,x-p+len],[x-p+2,x-p+len+1],\cdots,[x+q-len,x+q-1]$）

注意到这三段都是关于$len$的等差数列。

所以相当于给一个数组加上若干等差数列，只要求最后每个位置的答案。对于这个问题，我们直接在这个数组的一阶和二阶差分上进行修改，最后从前往后扫一遍求出原数组即可。

使用倍增RMQ建出笛卡尔树来计算$L,R$的复杂度是$O(n \log n)$的，统计答案是$O(n)$的，期望得分$90 \sim 100$分。

算法四

注意到我们并不需要建出笛卡尔树，只要使用两个单调队列从前往后和从后往前分别扫一遍，就能对每个位置求出对应的$L,R$了。

时间复杂度$O(n)$，期望得分$100$分。

合唱队形

By jiry_2

嗯..slyvia 是一个萌萌哒的妹子。

算法一

$n=m$ 的时候终止状态只有一个，其中每一个人都必须学会一个特定的音。

所以就相当于有 $n$ 个数，每一次等概率看一个数再放回去，问期望多少步看到特定的 $k$ 个数。

考虑从看过 $i$ 个经过若干次观看到达看过 $i+1$ 个，那么每一次看一个数都有 $\frac{k-i}{n}$ 的概率完成转移，因此这一步的期望步数就是 $\frac{n}{k-i}$。

那么答案就是 $\sum_{i=1}^k \frac{n}{k-i+1}$。

期望得分 $30$ 分。

算法二

这种情况下总的状态数不超过 $2^{15}$ 种，然而直接列方程高斯消元求答案的时间复杂度还是是无法接受。

考虑每一个点出发的转移，可以发现每一个点能转移到自己或者多一个已完成课程的状态，因此转移是一个套上自环的 DAG，于是就可以按照拓扑序进行 DP，对每一个点解一个一元一次方程就能得到答案了。

期望得分 $30$ 分。

算法三

令 $f_i$ 为第 $i$ 时刻还没有停止的概率，那么答案就是 $\sum_{t=0}^\infty f_i$。

考虑算 $f_t$，这时我们可以进行容斥，枚举哪些位置已经完成了对给定串的匹配，来容斥出每一个位置都不匹配的概率。

所以可以先 $2^n$ 枚举每一个位置往后是否可以匹配给定串，那么就得到了一些小学生必须要会哪些音，这就相当于有 $n$ 个数，每次等概率模出来一个数看一下再放回去，有 $k$ 个特殊数，问 $t$ 时刻后所有特殊数都被看过的方案数。

这个也是可以容斥的，我们枚举有多少个特殊数没有被看过，那么就变成了有 $k$ 个数不能被看的概率，这个是非常好算的，就是 $(\frac{n-k}{n})^t$。

容斥的过程中，我们把若干个 $1^t$ 和若干个小于 $1$ 的分数的 $t$ 次加加减减，但是可以发现所有 $1^t$ 是完全抵消的，因为 $\sum_{i=0}^n \binom{n}{i}(-1)^i=(1-1)^n=0$。所以我们可以不管所有 $1^t$ 项，只考虑哪些小于 $1$ 的分数的 $t$ 次项。

将里层的式子拆开，就相当于对很多个真分数 $k$，求 $\sum_{i=0}^\infty k^i=\frac{1}{1-k}$。

所以在容斥的过程中出现的每一个分数 $k$ 的 $t$ 次项对答案的贡献就是 $\frac{1}{1-k}$。

于是枚举位置容斥的时候把贡献累加起来就好了，时间复杂度 $O(2^nn)$，期望得分 $50$ 分。

算法四

不难发现算法三的复杂度其实是 $O(2^{n-m}n)$，因此当 $n$ 和 $m$ 非常接近时，是可以使用算法三的。

考虑当 $m$ 比较小的时候怎么进行容斥。因为两个方案，如果它们必须要选的教程数目是相同的，那么它们在容斥的时候对答案的贡献的绝对值也是相同。

所以可以令 $dp_{i,j,k}$ 表示当前考虑到了第 $i$ 个位置，$i$ 往前 $m$ 个位置匹配给定串的情况是 $j$，当前有 $k$ 个教程必须进行的方案数（实际上是偶数个位置匹配的方案数减去奇数个位置匹配的方案数）。因为只有往前 $m$ 个位置对 $i$ 有影响，所以再往前的就可以不记录了，每一次枚举当前位置选还是不选然后统计答案。

预处理一下后这一部分的时间复杂度是 $O(2^mn^2)$ 的。

均衡两部分的时间复杂度后可以得到一个 $O(2^{\frac{n}{2}}n^2)$ 复杂度的算法，期望得分 $100$ 分。

果冻运输

By xllend3

算法零

手玩了两个点心力憔悴，我还是让出题人感受我的哲♂学吧。

期望得分$0$分，成功成为全场唯一爆零选手。

提交记录：http://uoj.ac/submission/84215

算法一

辣鸡出题人居然搞了个这么长的题面我看都懒得看。直接点下提交爽一爽吧。

期望得分$1$分。

算法二

手玩！

根据手玩技巧和花的时间不等可以获得$6 \sim 50$分。

算法三

我发现这游戏我玩过http://qrostar.skr.jp/index.cgi?page=jelly&lang=en

看我轻松手玩每个点至少$2$分。

但是由于部分分给的特别少，而且大多数的点和原游戏有一些细微的差别并不能直接照抄，又因为一旦步数超的太多就$2$分了，这么做效率比较低。

验题组手玩取$\min$之后获得的分数是$84$分。

考场上单挑$5$小时大概能拿$50 \sim 70$分。

算法四

搜搜搜！根据搜的技巧不同能获得$0 \sim 100$分。

详细搜法见immortalCO的博客，我就不详细讲了。

为什么checker给源码呢

虽然checker半个多钟头肯定也能写出来了，但是这样的话我就会变成辣鸡模拟题出题人，所以就直接给源码了。我才不会告诉你其实是因为懒得check每个平台下的问题呢，哼

为什么数据和游戏有点不一样呢

其实原来是照抄游戏的，但是由于是NOI膜你赛，VFK要求最高分达到250，于是就把每个点压缩了几列让比较弱的搜索多拿点分，然后删了几个点，最后成功完成控分。 要是这题考场上有人A了就可以全真模拟题题有人A但是没人AK的情况了

Day2

Jakarta Skyscrapers

By qmqmqm

以下复杂度中的$n$为$\max(a,b)$。

算法一

每次暴力枚举得到消息的两个doge，看他们能不能使一个之前没有得到过消息的doge得到消息，直到不能操作为止。时间复杂度$O(n^3)$,操作次数$n$,可以通过第一个subtask，期望得分$10$分。

算法二

对于$b=1$的情况，明显如果$c>a$则无解。

否则，我们可以采用类似这种方式：

$a~~~~~~~~~~~~ \ 1$

$a-1~~~~~~1$

$a~~~~~~~~~~ \ a-2$

$a-2~~~~~~2$

$a~~~~~~~~~~ \ a-4$

$a-4~~~~~~4$

…………

在$2 \log(a)$次操作内得到所有不超过$a$的$2$的幂，进而可以通过二进制分解在$3 \log(a)$次操作内得到所有不超过$a$的数。

可以通过第二个subtask，期望得分$20$分。

算法三

对于$c=1$的情况，明显如果$gcd(a,b)>1$则无解。

否则，我们可以采用辗转相除的方法得到1。每次计算$x \bmod y=x-(x/y)*y$时,采用类似算法二的做法得到$(x/y)*y$。

这样看起来是$3 \log^2(n)$次的，但其实每次的$x/y$的乘积不会超过$n$，所以这些$3 \log(x/y)$之和也不会超过$3 \log(n)$。

可以通过第三个subtask，期望得分$20$分。

算法四

特判$c> \max(a,b)$和$c \bmod gcd(a,b) \neq 0$的两种无解情况。

将算法二和算法三结合，先通过算法二得到$gcd(a,b)$，再通过算法三得到$c$。

操作次数不超过$6 \log(n)$。

可以通过所有数据，期望得分$100$分。

如果你的做法常数过大，可以通过前四个subtask得到70分。

奇怪的线段树

By jiry_2

算法一

一共有 $2n-1$ 个节点，可以直接状压这些节点的颜色，每一次枚举一个区间放上去进行转移。

时间复杂度为 $O(2^{2n-1}n^2)$。

算法二

不难发现无解当且仅当存在一个节点它的孩子中有黑色节点但它自己却是白色的。这样显然是无解的，而只要不存在这样的情况，我们可以直接找出所有是黑色但是孩子都不是黑色的节点，仅对这些节点的区间单独操作，这样就得到了一个可行解，因此这个条件是充分必要的。

于是我们就不用状压全部节点了，只需要考虑所有是黑色但是孩子不是黑色的节点的染色情况就行了，这样状态数就减少到了 $O(2^n)$，实际上算法一种的有用状态也就只有这么多。

时间复杂度为 $O(2^nn^2)$。

算法三

命题一：一次覆盖时最终定位的点的区间一定是连续的，而且一定是连续的一段右儿子加上连续的一段左儿子（从左到右）。

证明：考虑反证法，如果存在从左到右连续的左儿子和右儿子，那么它们一定是同一个节点的两个孩子，这时在定位的时候我们取得一定是它们的父亲而不是它们本身，矛盾。

命题二：每一段连续的右儿子加连续的左儿子这样的序列一定可以通过一次定位得到。

证明：首先，我们证明一个引理，就是线段树上的所有右儿子对应的区间的右端点是互不相同的，所有左儿子对应的区间的左端点是互不相同的。

考虑反证法，假设存在，那么这两个右儿子一定是祖先关系，因为他们的区间相交了，令深度较浅的是 $a$，深度较深的是 $b$，那么考虑 $b$ 的父亲 $c$，$c$ 一定是 $a$ 或者 $a$ 的后代，因此 $c$ 的区间一定被 $a$ 包含。然而 $c$ 还存在一个非空的左儿子，因此 $c$ 的右端点要大于 $a$ 的右端点，矛盾。

通过这个命题，我们得到的信息是，对于一个右儿子，往右和它相邻的右儿子恰好只有一个，因此确定了出发点后不停的走连续的右儿子的路径只有一条，左儿子同理。

因此一个左侧的右儿子和一个右侧的左儿子之间至多只存在一条满足条件的路径。

我们来考虑路径最多有多少条，假设每一个左侧的右儿子都可以和一个右侧的左儿子组成路径，每一个左儿子一定可以和它每一个祖先的左儿子组成路径，每一个右儿子一定可以和它的每一个祖先的右儿子组成路径，这样计算出来的路径条数一定不小于真实的路径条数。

令 $w[i]$ 为长度为 $i$ 的线段树中用这种方式计算出来的路径条数，只要证明 $w[i]=\frac{i(i+1)}{2}$，那么路径和区间就是一一对应的。

考虑归纳法：等于 $1$ 的时候显然。

假设把 $n$ 拆成长度为 $m$ 和 $n-m$ 的区间，那么就有式子：

$w[n]=w[m]+w[n-m]+(m-1)(n-m-1)+(m-1)+(n-m-1)+1=\frac{n(n+1)}{2}$

因此每一个区间和每一条这样的线段树上的路径都是一一对应的。

于是我们可以把每一次覆盖拆成两部分，分别为连续的一段右儿子和连续的一段左儿子，并在两条链的 LCA 处统计它们。

令 $f[i][j][k]$ 表示 $i$ 为根的子树，子树中延伸出去要在外面合并的右儿子链有 $j$ 条，左儿子链有 $k$ 条时已合并链数的最小值，暴力转移合并即可。

这个算法的时间复杂度非常高，不过 $n \leq 50$ 的部分分应该还是可以过的。

算法四

在算法三中，我们已经发现连续的一段右儿子加连续的一段左儿子的路径与序列中的区间是一一对应的。

考虑把每一个点的后继都连出来，对于每一个右儿子 $i$，它能走到所有 $l_j=r_i+1$ 的节点；而对于每一个左儿子 $i$，它能走到所有的 $l_j=r_i+1$ 的左儿子。

我们把这张图建出来，不难发现我们得到了一个 DAG，因为我们每走一步所在节点的左端点都是增加的。

同时不难发现这个 DAG 上的每一条路径都是合法的，即都是满足由连续的一段右儿子和连续的一段左儿子组成的。因此这个 DAG 上的每一条路径，我们都可以通过一次操作进行覆盖。

于是就变成了给出一个 DAG，其中有一些点至少经过一次，有一些点不能经过，问最少多少条路径能满足条件。

这是一个裸的下界最小流问题。

点数 $O(n)$，边数 $O(n^2)$，因为流量是 $O(n)$ 的，所以时间复杂度是 $O(n^3)$。

算法五

考虑优化连边，连边的瓶颈在于对每一个右儿子都连一条边指向与它相邻的节点，这部分是可以优化的。

我们新建 $n$ 个辅助节点，对于每一个右儿子 $[l_i,r_i]$，都连一条边指向第 $r_i+1$ 个辅助节点。

同时对每一个线段树节点 $[l_i,r_i]$，都从第 $l_i$ 个辅助节点连一条边回来。

这样边数就优化到了 $O(n)$，时间复杂度为 $O(n^2)$。

在出题的时候我一直觉得这道题是可以线性贪心的，但是因为 ddl 实在太多一时间又有点想不清楚（实际上是不会证明），所以还是放 $4000$ 的良心范围娱乐大众吧。

如果大家想出了贪心的算法欢迎和我讨论。

火车管理

By SkyDec

这是一道十分清真的小清新数据结构题

首先题目可以转化为，有$n$个栈，区间压数，单点弹栈，求区间栈顶和。

算法一

我们可以直接用$\texttt{vector}$模拟栈。

时间复杂度 $O(n^2)$

空间复杂度 $O(n^2)$

期望得分:$30$分

算法二

考虑一种比较简单粗暴的做法

我们以铁路的编号为下标建立一颗线段树。

则对应的操作就是区间压一个数，单点弹一个数，区间求栈顶之和。

我们可以在线段树上用可持久化treap作为标记，压数和弹数就便成了treap的合并与分裂。标记的下传合并也可以在$O( \log n)$的时间内完成

由于可持久了treap，所以时间复杂度和空间复杂度也相当正确。

时间复杂度 $O(n \log^2 n)$

空间复杂度 $O(n \log^2 n)$

期望得分:$30$分$\sim 100$分

算法三

我们可以建立一颗可持久化线段树，维护每个铁路每个时间的栈顶的吨位和栈顶火车的入栈时间。

我们再维护一颗线段树用来统计答案。

于是操作就显得很简单了：

区间询问：直接在答案线段树里询问即可。

区间压数：在可持久化线段树上进行区间覆盖，这个是十分基础的数据结构技巧，然后在答案线段树上修改一下。

区间弹数：由于我们记录了入栈时间，所以我们删完后用可持久化线段树查出当前入栈之前的栈顶的信息即可，然后在答案线段树上和可持久化线段树上修改一下。

时间复杂度 $O(n \log n)$

空间复杂度 $O(n \log n)$

期望得分:$100$分