NOI2018 场外同步口胡题解

# Day1

## T1

这道题目离线相信大家都比较熟悉了。
首先使用最短路算法得到每个点回家的最短距离dis。

然后坐车可以通过一个没水的边组成的连通块，所以我们把所有边按照海拔高度排序，逐个加入图中，每一个连通块的代价就是该连通块内最小的dis值。这个可以使用并查集。

那么对于在线的情况呢？我们把操作可持久化，先排序做一遍，然后每次查询就好了。这样使用可持久化并查集可以得到一个可观的部分分。

但是依旧看上去不太能够通过，我们把连通块合并的过程建立成一棵树，也就是并查集合并两个集合的时候，我们选择新建一个父节点，然后两个集合的根节点连向这个父节点。于是我们就得到了一颗连通块合并顺序树。在每个父节点记录这次合并的海拔高度。然后对于一个点的查询，我们就可以遍历这个点到根节点的路径上的每个点，然后就可以判断答案，这部分采用树上倍增优化一下，就可以做到$NlogN$了。

所以本题最终复杂度$O(NlogN)$。

## T2

首先冒泡排序的交换次数是等于逆序对个数的。
我们分析题目所写的下界$\frac{1}{2} \sum_{i=1}^{N} |i-p_i|$的具体含义。比如排列231就是好的，而排列321就是不好的。

分析其中原因发现，每次交换必须使得两个数字离自己正确的位置都更近一步才行。
形象一点就是说，如果我们把$p_i$和$i$看成一个由$i$向$p_i$的箭头，那么所有同向的箭头必须互不完全包含才行。
自然而然又是很多个有向环压在一个序列上的问题了。

如果没有字典序的限制，DP[i][j][k]表示确定了前i个位置，j个向右的箭头，k个向左的箭头。每次转移有以下几种：
    当前点接受一个箭头，又发出一个箭头。DP[i+1][j][k] += DP[i][j][k]*2 （j,k>0）
    当前点接受发出一个向右和一个向左的箭头。DP[i+1][j+1][k+1] += DP[i][j][k]
    当前点接受两个箭头。 DP[i+1][j-1][k-1] += DP[i][j][k]
    当前点一个自环，DP[i+1][j][k] += DP[i][j][k] (j=k=0)
    
发现$k, j$的值永远是一样的，所以可以省去一个维度。
DP[i+1][j] += DP[i][j] (j=0)
DP[i+1][j] += DP[i][j]*2 (j>0)
DP[i+1][j+1] += DP[i][j] 
DP[i+1][j-1] += DP[i][j]

打表得出前几个数字会发现这是一个卡特兰数。
实际上这个竖着走有2的权值，放在网格里看确实是等于斯特兰数的。

$$C_n = {2n \choose n} - {2n \choose n+1}$$

![](https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike80%2C5%2C5%2C80%2C26/sign=1cfe77909d0a304e462fa8a8b0a1cce3/4d086e061d950a7be3e94d5000d162d9f3d3c942.jpg)

对于字典序限制，我们直接枚举在哪里出现区别就好了。这个相当于在我们这个网格中某不到3N个点上（因为有一些前缀可能本身不合法）添加一些值。
那么这样写一个$O(N^2)$的简单DP就可以得到80分！

那么一百分怎么办呢？
无非就是要解决一些不再原点出发也是不超过斜线的问题。
容斥扣掉y=x+1这条线对称的另外一个点的方案数即可。

## T3

题意为：给出字符串S，每次给出字符串str，数字l,r。求问str有多少个不同的子串不是S[l,r]的子串？

对于每次询问$l=1,r=|S|$的部分，我们建立S的后缀自动机，再建立str的后缀自动机。得到Str每个位置作为结尾时新出现的字符串是那一部分，假设为[1,R]->X。然后使用str在S的自动机上跑一遍就可以得到Str每个位置作为结尾时能和S匹配的最长的长度是多少。这样区间取差之后就可以以每个字符串第一次出现的位置完成统计。

这样就可以获得$68$分部分分！
然后对于100分部分，考虑套上一颗线段树，分界处怎么处理呢？我们把分界处$2|str|$长度的串拿出来，在str的自动机里面跑一次，标记这个后缀树相同的部分的大小。然后再使用str在$O(logn)$自动机里面挨个跑一遍，再次标记一遍str的后缀树上重叠的部分的长度。
最后拓扑排序在str 的后缀树上递推一遍即可。
复杂度$O(\sum|str| \log (N + |α|) +  |α| \times |S|\log N)$

这时候目测能有$80$分，瓶颈在线段树套后缀自动机这一部分的建立上。使用hash代替原有|α|大小的数组可以去掉这个|α|的理论复杂度，但预测实际速度可能没有太大的变化。。。

我们先建立字符串S的SAM，然后使用可持久化线段树合并得到每个节点的right集合。
对于每次询问我们把str丢入SAM中跑，如果当前节点管理的字符串并没有出现在[l,r]范围内就接着跳fail。复杂度证明类似与AC自动机跳fail一样，跳的次数是不会超过|str|的。单次对于是否出现的查询是log的。
故总复杂度$O(\sum|str| \log N + |S| \times (|α| + \log N))$

---

看来老年退役选手真的只有280分的水平了。估计场上T3也就一个暴力了，应该不超过248分了。。。

---

# Day2

## T1

根据题意可以直接列出同余方程组

$$ATK_i \times x - a_i = 0 \pmod {p_i}  $$
$$x \geq \lceil \frac{a_i}{ATK_i} \rceil $$

使用exCRT将上方同余方程组合并得到 $ATK \times x + (-1)\times a = 0 \pmod p $
尝试使用exgcd求解x的任意一个解，注意无解的情况。
然后将x调整到最小合法解即可。

这道简单数论题，场上通过人数应该不少。

## T2

题意：在给定的树上M条路径中，选择两条边交集非空的路径，获得的收益为两条链的边的并集的价值（每条边有价值，重复的只获得一次）减去两个方案的代价（每条路径有一个代价）。求最大收益。

考试时只会45分，没想出来。。。(我好菜啊)
最后膜了官方题解才会。[官方题解下载链接](http://on9i1rseh.bkt.clouddn.com/blog/%E6%83%85%E6%8A%A5%E4%B8%AD%E5%BF%83.pdf)

## T3

树上状压DP+大力讨论

$DP[i][0/1/2][3^{2k}]$ 表示当前子树以i为根，并且哈密尔顿回路从父亲到当前的儿子/从儿子到当前点的父亲/从儿子到儿子，当前子树中最左k个和最右k个叶子节点的进出状态（从其他子树到单前子树/从当前子树出发到其他子树/从当前子树到当前子树）。最后这一个维度的状态只有部分状态有效，可以剪枝一下。

那么DP转移的时候，枚举[0/1/2]的三种情况，分别进行三种DP。
每种DP也就是固定根节点和已经DP了的子树，然后枚举新的子树的状态$3^{2k}$以及进出的$3$的状态，拼接在当前已有的最右侧的子树旁边。讨论目前边界上3个点与这个子树左侧三个点的进出状态的匹配方案数，来更新当前部分子DP。得到答案后就可以更新这个子树的DP了。

wuvin

导航

最近发表

友情链接