贺题记录

长期记录一些破水题的做法,有的简单题可能只是因为我不擅长所以放进来了(

可能因为 $\LaTeX$ 的大量使用,加载比较卡,还请见谅。

P6071 『MdOI R1』Treequery

给定一棵 $n$ 个点带边权的树,$q$ 次在线询问 $p$ 到 $[l,r]$ 内的点路径的交的长度。

$1\leq n,q\leq 2\times 10^5$。

考虑用 ST 表求出 $[l,r]$ 内点的 LCA 为点 $u$。

  • $u,p$ 无祖先后代关系,答案为 $dis(u,p)$。
  • $u$ 在 $p$ 子树内,答案即为 $dis(u,p)$,因为所有点都在 $p$ 子树内,在 $u$ 处汇合。
  • $p$ 在 $u$ 子树内。

    • 若 $p$ 子树内有 $[l,r]$ 内的点,则答案是 $0$,因为 $p$ 子树内外都有点,路径会没有交。
    • 否则二分找到最高的点 $p'$ 满足 $p'$ 子树内无 $[l,r]$ 内的点,答案为 $dis(fa_{p'},p)$,因为此时所有点都会走到 $fa_{p'}$ 之后再走向 $p$,这一步可以用主席树来维护。

时间复杂度 $\mathcal O(n\log^2 n)$,空间复杂度 $\mathcal O(n\log n)$。


ARC084B Small Multiple

给定整数 $k$,求 $k$ 的倍数中最小的数位和。

$2\leq k\leq 10^5$。

对于所有 $i\in[0,k)$,向 $10i\bmod k$ 连边权为 $0$ 的边,向 $(i+1)\bmod k$ 连边权为 $1$ 的边。$1$ 到 $i$ 的最短路的意义就是从一个 $\bmod k=1$ 的数到一个 $\bmod k =i$ 的数额外所需的最小代价。

答案就是 $1$ 到 $0$ 的最短路,初始 $dis_1=1$,可以用 01BFS 解决。

时间复杂度 $\mathcal O(k)$。


P2824 HEOI2016/TJOI2016 排序

给出一个排列 $a_{1\cdots n}$,$m$ 次对区间 $[l,r]$ 升序或降序排序,询问所有排序进行完成之后的 $a_{pos}$。

$1\leq n,m\leq 10^5$。

考虑到区间排序不容易有简单做法,并且只询问一次一个单点的值,考虑什么样的区间排序有特殊性质使得能够快速完成。

发现如果是 01 序列,区间排序可以用线段树的区间求和与区间覆盖来完成,不妨往这个方向靠近。

考虑二分答案 $x$,把不小于 $x$ 的位置设为 1,否则设为 0,完成 $m$ 次 01 序列排序之后检查 $pos$ 位置上的值若是 $1$,则说明 $a_{pos}\ge x$,于是二分答案,用线段树维护 01 序列排序即可。

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


CF917D Stranger Trees

给定一棵 $n$ 个点的无根树,对于 $k\in[0,n)$ 计算,有多少棵 $n$ 个点的树与给定树恰有 $k$ 条相同的边。

$1\leq n\leq 100$。

扩展 Cayley 公式:被确定边分为大小为 $a_1,a_2,\cdots, a_k$ 的连通块,有 $n^{k-2}\prod {a_i}$ 种生成树。证明不会。

考虑利用这个性质进行 dp,设 $f_{u,j,k}$ 表示 $u$ 子树有 $j$ 条和原树相同的边,$u$ 所在的连通块大小为 $k$ 的方案数,统计到根之后可以 $O(n^2)$ 二项式反演。dp 的转移即考虑 $u$ 和 $v$ 之间的原树边是否保留即可转移,这样做是 $O(n^4)$ 的,可以通过本题。

Bonus:$1\leq n\leq 8\times 10^3$,8MB

给 $\prod a_i$ 一个简单的组合意义,即给每个连通块里放一个小球的方案数,不妨改状态为 $f_{u,j,k}$ 表示 $u$ 子树,$j$ 条原树边,$u$ 是否放小球,$k\in\{0,1\}$。

这个 dp 的转移就有 $f_{u,0,0/1}=1$,$k_1+k_2\leq 1$ 时可以保留这条原树边:$f_{u,j_1,k_1}\times f_{v,j_2,k_2}\to f_{u,j_1+j_2+1,k_1+k_2}$,任意时候可以不保留原树边:$f_{u,j_1,k_1}\times f_{v,j_2,1}\to f_{u,j_1+j_2,k_1}$。转移时注意开个临时数组承接转移值,一个儿子转移完毕后再放回,否则会重复转移。

不难发现这样利用树上背包复杂度的分析,每对点在它们的 lca 处贡献一次计算,时间复杂度是 $O(n^2)$ 的。

至于空间的限制就把 $f$ 数组的第二维换为 vector,一个儿子转移完毕后就把它内存清空,总空间复杂度是 $O(n)$ 的。


AT2689 ARC080D Prime Flip

给定无限长的 01 序列,其中只有 $x_{1\cdots n}$ 位置上的元素是 $1$,每次操作可以翻转($01$ 互换)一个长度为奇质数的区间,求最少多少次操作可以让序列变为全 $0$。

$1\leq n\leq 100$,$1\leq x_i\leq 10^7$。

考虑异或上左边的数,$b_i$ 表示第 $i$ 个为 $1$ 的位置,则翻转 $[l,r]$ 等价于将 $b_{l-1},b_{r}$ 翻转,此时 $r-(l-1)=r-l+1=len$,也即只需要 $b_j-b_i$ 是奇质数就能一次操作翻转 $b_i,b_j$。由于 $b$ 序列也只有 $O(n)$ 个元素,并且一定有偶数个元素,所以我们要将其两两配对算贡献,记 $h=b_j-b_i$,有比较明显的分类讨论:

  • $h$ 是奇质数,这样的 $i,j$ 可以花费一次操作消除;
  • $h$ 是偶数,$h=2$ 时用 $5-3$,$h=4$ 时用 $7-3$,否则利用 $[5,10^7]$ 内的偶数都可以拆分成两个奇质数之和的性质,且一次操作不能完成同时消除 $i,j$,于是需要两次操作消除;
  • $h$ 是奇数但非质数,$h=1$ 时用 $3+5-7$,$h\ge 5$ 时先拆一个 $3$,再用偶数的方法来做可以做到三次操作消除,并且一次操作不能消除非奇数质数 $h$,两次操作不能消除奇数 $h$,所以三次就是最少的。

那么我们就需要更多地执行第一种,然后贪心执行第二种,最后才考虑第三种。

实现时先把奇质数筛出来,为了更多执行第一种,我们把 $b_j-b_i$ 为奇质数的 $i,j$ 连边,显然有 $b_i,b_j$ 奇偶性不同,于是连出来的图一定是个二分图,于是二分图最大匹配就是最多能执行的第一种操作。

剩余一堆奇数和偶数共偶数个,那么两两奇偶性相同的匹配完之后要么一个不剩,要么恰好剩一对奇偶性不同的,于是直接贪心。


CF1588F Jumping Through the Array

给定序列 $a_{1\cdots n}$ 与排列 $p_{1\cdots n}$,进行 $q$ 次操作如下:

  • 1 l r,询问 $\sum_{i=l}^r a_i$ 的值;
  • 2 v x,临时连边 $i\to p_i$,将 $v$ 能到达的所有点 $u$ 的 $a_u\gets a_u+x$;
  • 3 x y,交换 $p_x,p_y$。

$1\leq n,q\leq 2\times 10^5$,$-10^8\leq a_i\leq 10^8$。

图由若干个环构成,交换 $p_x,p_y$ 性质很不优美,并且显然修改的方式不便于上线段树,所以考虑上根号复杂度的处理。为了更符合思维习惯,我们先考虑没有 $3$ 操作的简化版本。

先考虑序列分块,但因为修改对于查询来说的无序而没啥用,所以考虑操作分块,每 $S$ 个操作统一处理一次,总共处理 $O(\frac qS)$ 次。那么我们计算答案的方式就是先有一个前缀和数组,对于这 $S$ 个操作中的询问,它的答案是前缀和相减再加上这个询问之前块内操作对它的贡献,很容易想到把有修改操作的环提出来,修改操作就在环上打标记,询问操作就暴力遍历所有在块内被修改了的环来计算贡献,这个贡献就是点数乘上标记,标记直接用,点数可以考虑在每个环的点的集合(STL::set)里二分得到。然后处理完操作之后再对于每个环把 add 标记打在点上,更新前缀和数组。至此我们得到了一个带根号还带 $\log$ 的算法,它还不能处理 $3$ 操作,但是没有关系。

有了 $3$ 操作之后仍然保留整体处理的思想,把所有 $2,3$ 操作中的 $v,x,y$ 设置为关键点,一条链定义为从一个关键点的后继出发,直到遇到第一个关键点为止,那么这条链始终处于同一个环中,且只有 $O(S)$ 个,我们将其缩起来以链为基础单位来处理,每次统一处理操作时标记每个点所处的链,复杂度 $O(n)$。为什么要这么做呢?因为 $3$ 操作最大的影响是破坏了环的完整结构,而我们如果还要继续利用整体处理的思想,就需要另外找到一个不变的东西,不难发现这一条链中只有链尾是可能改变 $p$ 的,即它的结构在有了 $3$ 操作后依然保持相对不变。

于是维护一个到这次处理之前的前缀和,顺序遍历操作,$2$ 操作遍历目前环上的每条链,在链上打 add 的标记,复杂度 $O(S)$,$3$ 操作只需要直接交换 $p$ 即可,复杂度 $O(1)$。

接下来考虑 $1$ 操作的答案就是前缀和算出来的答案再加上块内之前修改的贡献,那么需要枚举每一条链对这次询问的贡献,其等于这条链当前的 add 标记乘上其中有多少个点在 $[l,r]$ 内,add 标记可以直接查,求链中有多少点编号在区间内这一步如果按照之前直接二分来搞的话可以做到 $O(S\log n)$,那么总复杂度就是 $O(\frac qS \cdot n+qS\log n)$,将 $n,q$ 视为同阶,则在 $S=\sqrt \frac {n}{\log n}$ 时取得理论最优复杂度 $O(n\sqrt{n\log n})$,貌似可以通过。

但是我们有简单的办法可以去掉这只 $\log$,具体可以考虑先将其预处理出来:得到每个点所在的链之后按编号从小到大遍历每一个点,并给其所在的链的权值 +1,则遍历到 $i$ 时链的权值的意义就是链中编号属于 $[1,i]$ 的点的个数,于是把询问拆成前缀相减来做就可以做到总复杂度 $O(n\sqrt n)$。

我写的代码跑的不是很快,但是应该比较简洁。


CF1202C You Are Given a WASD-string...

给定一个长度为 $n$ 的 WASD 组成的移动序列,四个字母分别对应在方格纸上向上左下右走一格,定义权值为最小的能包含所有被经过的格子的矩形的面积,求至多在序列任意位置插入任意一个上述移动后能达到的最小权值。

$1\leq n\leq 2\times 10^5$。

首先发现横纵坐标是独立的,假设原本移动序列的权值为 $a\times b$,则猜想答案会是 $\min\{(a-1)\times b,a\times (b-1)\}$,即插入的操作使得长的那边退回来一步,但是考虑这样一个操作序列 ADAD 原本是 $1\times 2$,但任意添加操作之后并不能让权值变为 $0\times 2$,甚至不能变为 $1\times 1$,这启发我们更深入地思考。

我们把问题转化为分别检查 $a,b$ 是否能减一,因为减一就是最大可能的贡献,即得到了一个 +1/-1 序列,将其做前缀和,贡献就是前缀和的 $\max-\min+1$,问是否能在其中插入一个 +1/-1 使得这个贡献减一,也就是将其前缀和数组的一个后缀 +1/-1

不难发现,若这个后缀中同时存在最大值和最小值,那么显然是不行的,因为它们同时改变是不会贡献的;若这个后缀以外的前缀中同时存在最大值和最小值,那么也是不行的,因为它们根本就没有受到影响。所以我们需要找到这样一个位置,使得它能够把最大值出现的位置和最小值出现的位置分开,即最大值只出现在这个位置之前,最小值只出现在这个位置之后或者反过来,那么我们就可以在这里插入一个操作使得贡献减一。

特殊的是,若出现了分割点是最值,分割点的前一个位置是另一种最值,即序列的前缀和在 0,-1 或是 0,1 之间横跳,也是不行的,所以实现上我们只需要检查最后一个最大值的位置加一是否小于第一个最小值的位置,或者反过来。

于是就 $a,b$ 分开检查再最和计算答案,时间复杂度 $O(n)$,一份参考代码实现


P5892 IOI2014 holiday 假期

有一行 $n$ 个城市依次编号 $1\cdots n$,从 $s$ 出发的 $d$ 天内每天可以选择以下两种操作之一:

  • 假设当前在 $x$ 城市,可以选择走向 $x-1$ 或 $x+1$ 城市(如果存在);
  • 假设当前在 $x$ 城市,如果没有参观过 $x$ 城市的景点,那么参观它的 $a_x$ 个景点。

求 $d$ 天过去后至多能参观多少个景点。

$1\leq n\leq 10^5$,$0\leq d\leq 3\times 10^5$,$0\leq a_i\leq 10^9$,1s,64MB。

显然的最优策略是如果走过了一些城市,剩下 $k$ 天一定会去参观走过城市的 $a_x$ 前 $k$ 大的景点。

所以策略要么是一直往一边走,要不是走一边回来之后再往另一边走,而且对于分配到移动上的天数是显然存在单调性的,于是就用主席树求区间前 $k$ 大的和,决策单调性分治 dp 几次就好了。

时间复杂度 $O(n\log ^2n)$,主席树需要离散化。

最后修改:2022 年 09 月 03 日
如果觉得我的文章对你有用,请随意赞赏