SCOI 2016 完整题解

背单词

给你$n$个字符串$s_i$，你需要将他们按照某种方式排序。排序后，第$i$个字符串$s_i$的权值定义为：

1. 如果存在$j>i$使得$s_j$是$s_i$的后缀，则权值为$n^2$。
2. 否则，如果$n$个字符串中不存在$s_j$（$j\ne i$）使得$s_j$是$s_i$的后缀，那么权值为$i$。
3. 否则，求出最大的$j$使得$s_j$是$s_i$的后缀。那么权值为$i-j$。

一种排序方案的权值是所有字符串的权值之和。

要求你最小化排序方案的权值并输出。

$1\le n\le 10^5,\sum |s_i|\le 5.1\times 10^5$。

Trie DFS 贪心 交换法

首先把所有字符串倒过来，后缀变前缀。

容易使用交换法证明，一定不存在第一种情况的权值。即，我们会把一个串的前缀排在它前面。

对$n$个串建 Trie，然后把关键点拿出来再建一棵有根树。那么排序方案就是这棵树的拓扑序。而且容易发现，一个串的权值就是它和它的父节点在拓扑序上的距离。现在我们要最小化这个距离。

考虑子树拓扑序合并。仍然使用交换法可以证明，我们把子树按大小排序，按从大到小的顺序把拓扑序拼起来即可。时间复杂度$O(n\log_2n)$。

代码

幸运数字

给出一棵$n$个点带点权$c_i$的树，$q$次询问$(x,y)$，求$x,y$路径上点权集合中的子集异或和的最大值（即任意选元素异或起来的最大值）。

$n\le 2\times 10^4,q\le 2\times 10^5,c_i\le 2^{60}$。

线性基 倍增

容易想到线性基。线性基的合并是$O(\log_2^2W)$的。考虑倍增（因为树剖 + 线段树更慢），则一次询问的复杂度$O(\log_2^2W\log_2n)$。总复杂度$O((n+q)\log_2^2W\log_2n)$。

代码

萌萌哒

给出一个长度为$n$的大数$s$，$s_1$表示数的最高位。有$m$个限制条件$(l_1,r_1,l_2,r_2)$（$r_1-l_1=r_2-l_2$），表示$s[l_1,r_1]=s[l_2,r_2]$。问满足条件的数有多少个。

倍增 并查集

这是一道倍增思想的好题。

定义$(i,j)$表示$s[i,i+2^j-1]$。那么对于一个限制条件，我们可以将其拆分成$O(\log_2n)$对形如$(a,j)=(b,j)$的条件。那么我们直接用并查集把$(a,j)$和$(b,j)$并起来。

另一方面，如果$(a,j)=(b,j)$，则$(a,j-1)=(b,j-1)$，$(a+2^{j-1},j-1)=(b+2^{j-1},j-1)$。因此我们可以枚举$(a,j)$，如果它不是代表元，那么我们找到它的代表元$(b,j)$，然后把两者的两个儿子对应着合并。我们$j$从大到小枚举，最后就可以得到单个元素之间的相等关系，那么就很容易计算答案了。

并查集有$O(\log_2n)$个，总大小是$O(n\log_2n)$的，因此复杂度$O(n\log_2n\alpha(n))$。

代码

美味

给出一个长度为$n$的整数序列$a_1,\cdots,a_n$，有$m$次询问形如$(b,x,l,r)$，求

$$\max_{l\le i\le r}\{b\oplus(a_i+x)\}$$

$1\le n\le 2\times 10^5,0\le a_i,b,x\le 10^5,1\le m\le 10^5$。

权值线段树 扫描线

考虑$x=0,l=1,r=n$怎么做。我们可以将权值排序。每次查询，我们从高到底枚举每一位，看答案的这一位能不能是$1$。那么我们可选的数的区间就会不断缩小，到最后只剩下单独的数，就是答案。

考虑$l=1,r=n$怎么做。相当于，我们的区间往左平移了$x$个单位。和上一个问题没啥区别。

考虑原问题。把询问离线，按照右端点分类。每次我们加入一个数$a_i$，处理$r=i$的询问。这时我们就需要判断，$a_l,\cdots,a_r$中是否存在某个数，位于值域区间$[L,R]$中。考虑建立权值线段树。那么我们的问题就转化为，是否在值域区间$[L,R]$中是否存在某个下标在$[l,r]$中。由于当前加入的下标是$\le r$的，那么我们直接求出下标最大值即可。

时间复杂度$O(n\log_2n+m\log_2^2n)$。

代码

妖怪

给出$n$个函数$f_i(x)=(1+x)(A_i+\frac{B_i}{x})$。设$F(x)=\max_{1\le i\le n}f_i(x)$。求$F(x)$最小值。

$n\le 10^6,A_i,B_i\le 10^8$。

三分 调参 凸包

$F$是一个凸的函数。三分即可。时间复杂度$O(n\log_2W)$。然而要调参，显然不是正解。

$f_i(k)=A_i+kA_i+B_i+\frac{1}{k}B_i$。考虑一条斜率为$-k$且过$(A_i,B_i)$的直线$y=-kx+kA_i+B_i$，容易发现这条直线的纵截距是$kA_i+B_i$，横截距是$A_i+\frac{1}{k}B_i$。换言之$f_i(k)$表示的就是$y$的横纵截距之和。

那么我们枚举斜率。则使得$f_i(k)$最大的$(A_i,B_i)$一定是上凸壳上的点。因此我们求出$n$个点的凸壳。考虑凸壳上编号为$i$的点，那么$f_i(k)$为最大值的$k$就是一段区间。这时我们要求的就是这个区间里$f_i(k)$的最小值。可以简单地使用均值不等式求解。

时间复杂度$O(n\log_2n)$。

三分代码

围棋

给出一个$n\times m$的网格，每个格子可以填WBX三种字符。给定$q,c$。$q$次询问。

每次询问给出一个$2\times c$的网格，每个格子是WBX三种字符。问在所有$3^{nm}$种方案里，有多少种方案包含了这个$2\times c$的网格（出现过）。

$n\le 100,m\le 12,c\le 5,q\le 5$。

轮廓线 DP

我们可以把$2\times c$的网格当成两个字符串。不妨考虑计算不合法的方案数。

考虑轮廓线 DP。设$f(i,j,S,x,y)$表示当前的格子是$(i,j)$，且$(i,j)$匹配到第一个串的位置是$x$（即$(i,j-x+1),(i,j-x+2),\cdots,(i,j)$上的字符匹配第一个串长度为$x$的前缀），$(i,j)$匹配到第二个串的位置是$y$。$S$是轮廓线的二进制状态，表示轮廓线上的这个格子是否能匹配第一个串。

当我们从$(i,j)$转移到$(i,j+1)$的时候，我们枚举$(i,j+1)$上面填的字符。然后$x,y$就可以使用 KMP 求出新的$x',y'$。如果$(i-1,j+1)$能匹配第一个串，而$y'=c$，相当于出现了一个$2\times c$的网格，这种转移就不能进行。其他情况都可以转移。在求出了新的$S'$后，从$f(i,j,S,x,y)$转移到$f(i,j+1,S',x',y')$即可。

从$(i,m)$转移到$(i+1,0)$比较简单。

代码