前言

真就越靠近省选越颓...

ZJOI 2016

*小星星

编号两两不重维护的复杂度很大,而编号两两不重等价于所有编号都被用到,于是考虑子集反演,设 $f(S)$ 表示编号集合为 $S$,且每个编号都被用到的答案,再设:

$$ g(S) = \sum_{T\subseteq S} f(T) $$

即编号集合 $\subseteq S$ 的答案,子集反演得:

$$ f(S) = \sum_{T\subseteq S} (-1)^{|T|-|S|} g(S) $$

而 $g(S)$ 容易用一个 $\mathcal O(n^3)$ 的树形 dp 求得。

时间复杂度 $\mathcal O(2^nn^3)$.

旅行者

考虑分治,使用类似线段树的结构,维护出每一层一个区间内所有点到中线上所有点的最短路,那么查询就是递归直到 $s,t$ 被分到两个不同的区间(到此时 $s\to t$ 的所有路径必然穿过中线),每次枚举所有中线上的点作中转点,路径长度取 $\min$ 就好了。

不妨设 $n\le m$,时间复杂度是 $\mathcal O(n^2m\log^2 m+qn\log m)$,需要卡常,似乎采用更优越的分治方法能够少掉一个 $\log$?

大森林

考虑全局换生长节点,区间加叶子怎么做。把操作离线,按树的下标扫一遍,一开始把所有点都加上,但带 $0$ 的权值,每次若进入某个点生效区间就给它权值加上 $1$,若离开则减去 $1$,那我们可以容易树剖统计路径上有效点数,进而可以统计路径长度。

那么区间换生长节点也就可以使用类似的做法,每次换生长节点我们直接新建一个虚点,权值为 $0$,初始连向它前面一个生长节点新建的虚点,若进入它的生效区间,我们把它改接到操作应该换的节点下面,若离开再把它接回去,可以用 LCT 维护。

需要注意一些细节,例如查询的点 LCA 是生长节点的情况和生长节点换不过去的情况。

时间复杂度 $\mathcal O((n+m)\log n)$.

*线段树

设 $f(x,k,l,r)$ 表示进行了 $k$ 轮,$\forall i\in[l,r],a_i\le x$ 且 $a_{l-1},a_{r+1}>x$ 的方案数。

注意到 $[a_i>x]=1$ 总是在向中间合并的,所以这样设不会出现重复转移。

那么转移就可以分两类,第一类是改变了 $1$ 的位置。

$$ f(x,k+1,i,r) \gets (l-1)\cdot f(x,k+1,l,r) \\ f(x,k+1,l,j) \gets (n-r)\cdot f(x,k+1,l,r) \\ $$

而不变的有:

$$ f(x,k+1,l,r) \gets \frac {(l-1)^{\overline 2}+(n-r)^{\overline 2}+(r-l+1)^{\overline 2}}2\cdot f(x,k+1,l, r) $$

设排完序后的 $a_1,a_2,\cdots,a_n$ 为 $b_1,b_2,\cdots,b_n(b_{n+1}=0)$,于是我们可以统计出位置 $i$ 的答案:

$$ \sum_{j=1}^n\sum_{l\le i\le r} f(b_j,q,l,r)(b_{j+1}-b_j) $$

注意到 $f$ 的转移并没有用到 $x$,于是可以分开来处理,即设:

$$ h(k,l,r) = \sum_{x\in b_i} f(x,k,l,r) $$

容易发现转移是类似的,于是我们就做到了 $\mathcal O(n^2q)$.

ZJOI 2017

树状数组

不难发现实际上是在求后缀和,故询问 $[l,r]$ 正确的概率可以转化成求 $a_{l-1}=a_r$ 的概率(在 $l=0$ 时略有不同,但处理方法类似,不再赘述)。

记 $f_{i,j}$ 表示 $a_i=a_j$ 的概率,则容易发现区间 $[l,r]$ 随机选一个数加一的影响是一个矩形加 / 乘,直接大力上 KD-Tree 维护即可,时间复杂度 $\mathcal O(n\sqrt n)$.

然而可以上二维线段树,被吊打。

仙人掌

由于原图是连通图,所以必须得是仙人掌才能加成仙人掌。

然后注意到我们加的边不可能跨越圆方树的方点(也就是不会跨越在环上的边),所以可以把所有环内的边全部删掉,然后答案就为每个联通块答案之积。

对于每个连通块,注意到选一些点对连成环相当于把整棵树划分成若干条不相交的路径,每条路径对应着一个环(若路径只有一条边,则其在最后的仙人掌上是一个树边)。

于是直接设 $f_u$ 表示以 $u$ 为根的子树的答案,那么有 $f_u = c_u\prod_{v\in\operatorname{son}(u)} f_v$,其中 $c_u$ 为将子树中的路径合并或新建一条路径的方案数,可以用一个 $\mathcal O(n)$ 的 dp 求出,注意根的情况有所不同。

SHOI 2017

期末考试

不放令 $A\gets\min(A,B)$。

考虑枚举最后所有的课程发布时间 $\le t$,那么统计 $s=\sum \max(t-b_i,0)$ 和 $r = \sum \max(b_i-t,0)$,我们尽量多的使用第一个操作,直到没有课程可以用来延迟,那么只能使用第二个操作,这样一定是最优的。

$s$ 和 $r$ 可以用前缀和维护,时间复杂度 $\mathcal O(n)$.

分手是祝愿

列式可以发现操作相当于一个 $n$ 个未知数,$n$ 个方程的异或方程组,所以必然存在唯一解,我们可以通过倒着操作构造解。

设 $f_i$ 表示未知数中还有 $i$ 个 $1$,消成全 $0$ 的期望步数,容易列出 $nf_i = if_{i-1}-(n-i)f_{i+1}+n$(在 $k< i$ 的情况下)于是有:

$$ f_{i+1} = \frac{nf_i-if_{i-1}-n}{n-i} $$

特别的我们有 $f_n = f_{n-1} + 1$,注意到我们没有 $f_{k+1}$ 的式子,所以可以把每个式子表示成 $af_{k+1}+b$ 的形式,然后用最后一个等式 $f_n=f_{n-1} + 1$ 解出 $f_{k+1}$ 即可。

寿司餐厅

选了区间 $[i,j]$ 就必须选区间 $[i',j']\subset [i,j]$,容易发现这是最大权闭合子图的模型。发现 $[i,j]$ 的子区间族为 $[i,j-1]$ 和 $[i+1,j]$ 的子区间族的并,所以我们只需要连 $\mathcal O(n)$ 条边就可以完成建图。

接下来考虑 $mx^2+cx$ 的贡献,注意到 $cx$ 相当于给 $d_{i,i}$ 加上 $a_i$,而 $mx^2$ 相当于选了某一类就附加贡献,所以再新建点表示这类选不选就好了。

九省联考 2018

*IIIDX

考虑对 $i=1,\cdots,n$,依次确定 $d_i$.

于是考虑贪心,假如我们要选取某个 $d_i$,那么就要求选完 $d_i$ 之后剩下的数存在一种选择的方案。对于每个已经确定了权值的点 $j<i$,我们需要在剩下的数中选取 ${\rm siz}_j - 1$ 个不小于 $d_j$ 的数,于是我们可以贪心确定这个方案:每次选最小的合法的数。这样最大的 $d_i$ 就是做完所有贪心之后剩下的最大的数了。

暴力做是 $\mathcal O(n^2\log n)$ 的,考虑如何优化这个过程,记 $f_u$ 表示考虑了 $d_j\ge u$ 的贪心选取后,还剩下多少个 $\ge u$ 的数,那么考虑所有的 $d_j$ 之后,剩下的 $\ge u$ 的数即为 $g_u=\min_{v\le u}f_v$,这样定义的好处在于,每次新选了的数对 $f_u$ 的影响是显而易见的(假如给某个子树大小为 $s$ 的节点选了 $v$,就是对所有 $u\le v$ 有 $f_u\gets f_v-s$),我们可以很容易的用线段树去维护。

然后我们就做到了 $\mathcal O(n\log n)$.

AHOI / HNOI 2018

游戏

可以把门当成房间,这样大概可以少考虑一些细节。

考虑对每个点求出 $l_i,r_i$ 表示能到的最远点。

然后考虑每个起点 $s$、钥匙 $k$,门 $t$ 的位置关系。若 $s<k<t$,那么直接忽略这对钥匙和门,若 $s<t<k$,那么必然开不了这个门,对 $r_s\gets \min(r_s,t-1)$,对 $t,k$ 均在 $s$ 的另一侧的情况同理。

所以只需要考虑跨过 $s$ 的,注意到若 $k_2<t_1<t_2<k_1$,那么相当于区间对 $l,r$ 进行取 $\min/\max$,拆贡献后发现可以对 $s\in(t_1,n]$ 的 $l_s$ 和 $t_1$ 取 $\max$,$s\in[1,t_2)$ 的 $r_s$ 可以和 $t_2$ 取 $\min$,于是我们只需要对每个 $k,t$ 跑一个二维偏序判一下有没有就可以计算贡献了。

然后还有一个限制是 $s\to t$ 的路径上不能有需要走到走不到的地方才能取的要是,这个可以用一个 RMQ 解决。

时间复杂度 $\mathcal O(n\log n+p)$.

正解据说是线性,但是我不会。

排列

原题。容易转化为树上的模型,考虑合并必须相邻的连通块,把每个连通块视作二元组 $(c_i,w_i)$ 分别表示大小和权值和,然后考虑交换 $(c_1,w_1)$(一开始在前面)和 $(c_2,w_2)$ 的代价是 $c_2w_1-c_1w_2$,直接拿这个去贪心地合并就好了,需要用优先队列维护。

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

寻宝游戏

先把输入翻转,方便倒推。

注意到倒推时若使用了或,则所有 $a_{i,j}=1$ 的位置后续就不用管了,反之所有 $a_{i,j}=0$ 的位置都不用管了,所以暴力枚举可以做到 $\mathcal O(nmq)$ 的复杂度。

再注意到交换两个位不影响答案,所以我们可以对所有排序,即使得第一个数为 $00\cdots011\cdots1$ 的形式,第二个数为 $00\cdots011\cdots100\cdots011\cdots1$ 的形式,以此类推。

那么我们每次考虑的就是一段连续的区间的内容了,于是可以预处理前缀和。

乍一看复杂度还是 $\mathcal O(nmq)$ 的,但容易注意到我们只会考察 $\mathcal O(1)$ 条链的状态,故复杂度变成了 $\mathcal O((n+q)m)$.

最后修改:2021 年 04 月 07 日 05 : 23 PM