贺题记录

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

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

ARC114B Special Subsets

给你 $n$ 和序列 $f_{1\cdots n}$,对满足下面条件的子集 $S$ 计数,对 $998244353$ 取模。

  • $\forall i\in S,f_i\in S$
  • $\forall i,j\in S,i\not= j,f_i\not =f_j$

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

常规套路:$i\to f_i$ 连边,考虑会出现若干个环。

在题目限制下只能选若干个完整环,所以记录环个数是 $cnt$,答案就是 $2^{cnt}-1$。


ARC114C Sequence Scores

定义一个序列 $A$ 的权值 $f(A)$ 为,从一个全 $0$ 的相同长度序列 $B$ 开始,至少要多少次区间取 $\max$ 以得到序列 $A$。

求所有长度为 $n$,值域为 $[1,m]$ 的序列的权值和,对 $998244353$ 取模。

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

考虑转化一下计算权值的方式。

对于一个序列,我们找到 $i\not =j,a_i=a_j,\forall k\in(i,j),a_k>a_i$,把 $(i,j)$ 连边,最后的答案就是图的连通块个数。

然后考虑一条边的出现就必定意味着连通块数量减少一,于是对于每条边考虑它出现的次数就好了。

对于边 $(i,j)$,它会在 $\sum_{x=1}^m (m-x)^{j-i-1}m^{n-(j-i+1)}$ 个序列里面出现,也就是中间的都大于 $a_i,a_j$,两边的随便选。

于是就用总数来减就好了。


CF1508B Almost Sorted

定义一个排列 $a$ 是「几乎有序」的,当且仅当 $\forall i\in[1,n),a_i-1\leq a_{i+1}$。

求所有长度为 $n$ 的「几乎有序」的排列中,字典序第 $k$ 小的排列。

$1\leq n\leq10^5$,$1\leq k\leq 10^{18}$。

考虑几乎有序的序列的形态,发现它一定是若干个互不相交的区间翻转之后的样子。每个 $[2,n]$ 中的点都可以选择是否作为翻转的右端点,所以一共有 $2^{n-1}$ 个几乎有序的序列,并且每种切割方案对应不同的序列,这让我们想到了给每种切割方式一个特殊的编号。

于是在这些翻转区间的右端点设置为 $0$,否则设置为 $1$,于是就可以得到一个二进制数 $l$,有个结论就是这个序列的排名就是 $l+1$。

考虑第一个二进制下不同的位 $i$。即序列 $A$ 在这个位置没有切割,$B$ 在这个位置切割了,就有 $A>B$。因为前面都有 $a_j=b_j$,而在第 $i$ 位有 $a_i=i,b_i<i$。

然后就可以快乐地大力暴力了。


CF1508C Complete the MST

一张 $n$ 个点的完全图,其中 $m$ 条边指定了一个大于零的边权,现在让你指定剩下的边权,满足所有边权的异或和是 $0$,求出最小的最小生成树。

$1\leq n\leq 2\times 10^5$,$1\leq m\leq \min\{2\times 10^5,\frac{n(n-1)}{2}-1\}$。

由于 $\sum a_i \geq\oplus a_i$,所以肯定是只有一条需要指定的边权是其他边权的异或和,剩下的都是 $0$。

考虑这样一个事情,当 $\frac{n(n-1)}{2}-m\geq n$ 的时候,零边肯定会成环,所以异或和为 $0$ 的限制就消除掉了。否则肯定是点数在 $\sqrt{2e5}$ 级别的东西,直接 $O(n^3)$ 大暴力就好了。

于是问题就转化为了,有一些「禁边」,要尽可能的把剩下的边连上,于是就有一个很经典的 Trick。

考虑禁边的条数为 $m$,根据鸽巢原理,连出去最少禁边的点,连出去的级别也就是 $\frac{m}{n}$,于是就对应的连上没有禁边相连的点,就只剩下 $\frac{m}{n}$ 个点了,这个暴力尝试 merge 就好了,这里复杂度是 $O(m)$ 的。

于是时间复杂度瓶颈就是在边的排序上,总时间复杂度 $O(m\log m)$ 就过了。


CF149D Coloring Brackets

给定一个长度为 $n$ 的合法括号序列,求按照下面的要求对其染色的方案数,对 $10^9+7$ 取模。

  • 一个括号可以染红色、蓝色或不染色
  • 一对匹配的括号需要且只能将其中一个染色
  • 相邻两个括号颜色不能相同(但可以都不染色)

$2\leq n\leq 700$

考虑设 $f_{l,r,0/1/2,0/1/2}$ 表示区间 $[l,r]$ 内,左/右端点的颜色为 不染色/红色/蓝色 的方案数。

于是我们发现在后两维 都是0/只有一个0/有两个0 的情况下分别对应的答案都是相同的,这个也很容易理解,换一下颜色的编号答案是不会变的。于是考虑设 $f_{l,r,0/1/2}$ 表示区间 $[l,r]$ 内左右端点不染色点的个数是 $0/1/2$ 的方案数。

于是就传统地用区间 dp 转移就好了...时间复杂度 $O(n^3)$ 但完全跑不满。


CF794F Leha and security system

维护一个长度为 $n$ 的非负整数序列 $a$,每个数位数不超过 $9$ 位,需要支持 $q$ 次以下两个操作:

  • 1 l r a b,把区间 $[l,r]$ 里所有的 数字 $a$ 改为 $b$。例如 $114514$ 把 $1$ 修改为 $9$ 之后就是 $994594$。
  • 2 l r,求区间 $[l,r]$ 的和。

$1\leq n,q\leq 10^5$,$0\leq a\leq 9$,$1\leq b\leq 9$。

绝妙线段树题。

首先一眼想到对每一位开个线段树来维护,但是这样我只会写用 vector 存懒标记的,于是就喜 MLE #8

然后想想它能怎么卡,大概就是每次修改之后尽可能把我的懒标记下传到更深,这样我的空间就会裂开。

那必不能 vector,换成 $10\times 10$ 的 bool 又铁定会 T,于是考虑只开一棵线段树,每个结点开一个 s[10]v[10]s[i],v[i] 分别表示这个结点对应区间数字 $i$ 的加权和/数字 $i$ 会变为 $v_i$。

于是注意一下 down/up 的写法就好了。record


AGC010E Rearranging

给定一个长度为 $n$ 的序列 $a_{1...n}$,先手可以任意排列,后手可以任意次交换相邻两个互质的数,先手希望最终字典序最小,后手希望最终字典序最大,输出最后的序列。

$1\leq n\leq 2\times 10^3$,$1\leq a_i\leq 10^8$。

考虑把不互质的数连边,这样会形成若干个连通块。

我们发现不互质的数之间的相对位置关系不会改变,于是如果我们能够给这些边定向,就能通过拓扑排序找到一组合法的解。

由于先手希望字典序更小,所以他给边定向的时候一定是从连通块里最小的点开始往后连边,至此我们得到了先手的操作策略:从每个连通块里值最小的点出发 dfs,边被经过的方向就是他定下的方向。

那么考虑后手的操作。他可以在不改变拓扑序的条件下任意的选点,那么就把拓扑排序时的队列换成一个大根堆即可,代码及其好写。


USACO21FEB No Time to Dry P

给定一个长度为 $n$ 的颜色序列 $a_{1...n}$,颜色从 $1$ 到 $n$ 编号,值越大颜色越深,深色可以覆盖浅色。

$q$ 次询问,每次询问给定一个区间,问给这个区间涂色所需要的最小次数。

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

发现只需要维护每个位置的颜色到它下一个同色位置之间的最小值,如果这个值不小于自己,那就不需要额外涂色,依据这个写发莫队就可以过了。

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


LOJ #6077「2017 山东一轮集训 Day7」逆序对

对恰有 $k$ 对逆序对的 $n$ 阶排列计数,对 $10^9+7$ 取模。

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

考虑从小到大插入数,插入第 $i$ 个数的时候可以任意选择增加 $[0,i-1]$ 对逆序对,所以问题转化为了:

$\sum_{i=1}^n a_i=k,0\leq a_i<i$,对满足条件的序列 $a$ 计数。

如果没有后面的限制很好做,就是一个插板,答案是 $\binom{n+k-1}{n-1}$,那么考虑容斥掉不满足限制的情况。

假设至少有 $i$ 个位置不满足限制的方案数是 $g_i$,那么就要额外加上 $\sum_{i=1}^n(-1)^i\times g_i$,考虑如何计算这个东西。

我们发现 $g_i$ 的限制即有至少 $i$ 个 $a_i\ge i$,其余数不小于 $0$,和为 $k$。即 $g_i=\sum \binom{n+k-1-\sum_{p_{1\cdots i}}p_i}{n-1}$,其中 $p_i$ 位置上的数满足 $a_{p_i}\ge p_i$,这里的隔板法和初始答案的计算是一样的,于是只需要求有多少个 $\sum p_{1\cdots i}=j$。

问题就转化为了在 $0,1,\cdots,k$ 里面任选若干个数求和,$f_{i,j}$ 表示选 $i$ 个互不相同的自然数,和为 $j$ 的方案数,这个东西的第一维大小是 $O(\sqrt k)$ 的,那么直接 dp 的复杂度就是 $O(k\sqrt k)$。

那么就有一个比较妙的转移就是 $f_{i,j}=f_{i-1,j-i}+f_{i,j-i}$,意义是要么把 $i-1$ 个数都加一再插入一个 $1$,要么把 $i$ 个数都加一,这样可以满足限制。

问题是可能插入 $n+1$,那么当 $j>n$ 的时候 $f_{i,j}$ 减去 $f_{i-1,j-n-1}$ 就好了。

那么 $g_i=\sum_{j=1}^k f_{i,j}\times \binom{n+k-1-j}{n-1}$,直接容斥就好了,时间复杂度 $O(k\sqrt k)$。


CF522D Closest Equals

给定一个长度为 $n$ 的序列 $a_{1\cdots n}$,$m$ 次询问区间 $[l,r]$ 内最近相同元素之间的距离,即 $\min_{i,j\in[l,r],a_i=a_j}|i-j|$。

$1\leq n,m\leq 5\times 10^5$,$-10^9\leq a_i\leq 10^9$。

考虑对于每个位置 $i$ 求出一个 $b_i$ 表示和下一个相同元素之间的距离。不难发现答案就是 $\min_{i=l}^r b_i,i+b_i\leq r$。

于是询问离线按 $r$ 从大到小排序,数据按 $i+b_i$ 排序,就是一个单点修改区间求 $\min$ 的题,上线段树就好了。

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


CF232E Quick Tortoise

给定一张 $n\times m$ 的网格,有一些格子是障碍,$q$ 次询问从 $(x_1,y_1)$ 出发不经过障碍是否能到达 $(x_2,y_2)$。

$1\leq n,m\leq 500$,$1\leq q\leq 6\times 10^5$。

下面的可达都指双向关系。

考虑直接暴力,可以 $O(n^4)$ 处理出任意两个点是否可达,但是发现这个可达性是可以传递的,即对于可达的两点 $A(x_1,y_1),B(x_2,y_2)$,任意满足 $x_1\leq i\leq x_2$ 的第 $i$ 列都至少存在一个点 $C$ 满足 $A,B$ 都可达 $C$。

于是转化一下暴力方式,考虑找到这样合适的第 $i$ 列方便查询,于是对这玩意分治,对于一个区间$[l,r]$,记录 $f_{i,j,k}$ 表示点 $(i,j)$ 是否能到达点 $(mid,k)$,这样是 $O(n^3\log n)$ 的。$\log n$ 是因为其实还有一维深度没有表示进来。

由于可达性可传递,于是本质是一个或的过程,只需要把第三维改为 bitset 就可以做到预处理 $O(\frac{n^3\log n}{\omega})$ 了。

对于每组询问,我们找到最大的那个 $mid$ 分割开 $x_1,x_2$ 的区间直接查询就好了。

把这玩意在线段树上实现就是猫树吧(

时间复杂度 $O(\frac{n^3\log n}{\omega}+q(\frac{n}{\omega}+\log n))$。


P4949 最短距离

给定一棵 $n$ 个点的基环树,要求支持 $m$ 次以下操作之一:

  • 1 x y,把第 $x$ 条边的边权修改为 $y$。
  • 2 x y,查询 $x$ 到 $y$ 的最短路。

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

先把图变成一棵树加上额外的一条边。

考虑这个最短路要么直接走树上路径,要不走那条额外的边,问题转化为了动态求树上两点之间的距离,这个把边权下沉为点权直接裸树剖就好了..主要是好久没写题了练练手。

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


ARC101F Robots and Exits

给定一条数轴上的 $n$ 个小球和 $m$ 个洞的位置,可以把所有球整体向左/右移动任意距离,当一个球与一个洞位置重合,球就会掉入洞。求有多少种本质不同的最终状态,称两种最终状态不同当且仅当存在一颗球落入的洞不同。

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

去掉最左边和最右边的球,剩下的球都可以用它距离左边和右边最近洞的距离作为一个二元组 $(x,y)$ 来表示,因为一个球显然只会掉进相邻的两个洞之中。

于是考虑整体移动的过程,就相当于把这些二元组当做坐标放到平面里,然后可以任意向上移动 $x$ 轴或向右移动 $y$ 轴,当一个球先与 $x$ 轴触碰,则落入左边的洞,否则落入右边的洞。

考虑过程中原点是在不断向右/向上移动的,会画出一条折线,把折线向下平移直到上面触碰到若干个点,此时就可以用这些点来唯一地描述这条折线,也就是若干个横纵坐标都单调上升的点可以唯一对应一种最终状态,那么问题就转化为了对严格上升子序列计数,即设 $f_i$ 是以点 $i$ 作为折线的最后一个点的方案数,那么有 $f_i=1+\sum_{x_j<x_i,y_j<y_i}f_j$,这个第一维排序掉,第二位用树状数组就好了。

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


CF1539F Strange Array

给定一个序列 $a_{1\cdots n}$,$\forall i\in[1,n]$,求出包含 $a_i$ 的一个区间 $[l,r]$,满足区间 $[l,r]$ 排序后 $a_i$ 与区间内中位数的下标之差最大,偶数长度序列的中位数视作中间靠右的那个。

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

不难发现对于一个 $i$,把大于 $a_i$ 的视作 $1$,小于 $a_i$ 的视作 $-1$,等于 $a_i$ 的视作 $0$,问题就转化为了要求包含 $i$ 的最大的一段区间和,但要根据题目要求除以二上取整/下取整,做前后缀和之后也就是要求某个位置开始的最大值/最小值,这个显然可以用线段树来完成,每个结点维护区间最大/最小值,支持区间加减即可。

那么从小到大枚举 $a_i$,计算答案之后把对应的更改也放到线段树上,时间复杂度 $O(n\log n)$。

参考代码


ABC206E Divide Both

$$ \sum_{i=l}^r\sum_{j=l}^r [(i,j)\not=1][i\nmid j][j\nmid i] $$

$1\leq l\leq r\leq 10^6$。

考虑容斥:

$$ \begin{aligned} f(n,m)=&\sum_{i=1}^n\sum_{j=1}^m [(i,j)\not =1][i\nmid j][j\nmid i]\\ =&nm-\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]-\sum_{i=2}^n \lfloor\frac mi\rfloor-\sum_{j=2}^n \lfloor\frac ni\rfloor +n\\ \end{aligned} $$

这个都是经典问题,有了 $\mu$ 的前缀和之后可以 $O(\sqrt n+\sqrt m)$ 计算,处理 $\mu$ 的前缀和可以 $O(n^{\frac 23})$ 的杜教筛或者 $O(n)$ 的线性筛,都能通过本题。

最终的答案就是 $f(r,r)-2f(l-1,r)+f(l-1,l-1)$。


ABC205E White and Black Balls

有 $n$ 个白球以及 $m$ 个黑球,将它们排成一列,要求对于每个前缀,白球的个数都不超过黑球的个数 $+k$,对满足要求的排列方式计数,对 $10^9+7$ 取模。

$0\leq k\leq n,m\leq 10^6$。

考虑把问题放到二维平面上,如果不考虑限制条件,就等价于从 $(0,0)$ 出发,每次放白球就向上走一步,放黑球就向右走一步,最终走到 $(m,n)$ 的方案数,这个显然是 $\binom {n+m}{n}$。

考虑加上限制条件,也就是要求这个路径不穿过直线 $y=x+k$。

考虑每个不合法的路径第一次穿过这条限制直线时,坐标 $(x,y)$ 满足 $y=x+k+1$,我们把这个位置之前的部分全部沿着直线 $y=x+k+1$ 翻折,得到的起点是 $(-k+1,k+1)$,那么每一个不合法路径都对应一种从 $(-k-1,k+1)$ 走到 $(m,n)$ 的方案,也就是 $\binom {n+m}{n-k-1}$。

那么答案就是 $\binom{n+m}n - \binom{n+m}{n-k-1}$,注意特判 $n>m+k$ 的情况。

时间复杂度 $O(n+m)$。


计蒜客T3342 幸运路径

给定一棵 $n$ 个点的树以及 $m$ 条幸运路径,每条路径带一个权值。$q$ 次询问,每次询问给定一条路径,求所有与这条路径有至少一个公共点的幸运路径的权值和。

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

越来越丢人了,学数据结构学傻了。

考虑树上差分,依据是若两条路径相交,那么相交部分的点数-1=边数。于是对点和边分别差分就做完了。

时间复杂度 $O(n+m\log n+q\log n)$,$\log n$ 是求 $LCA$ 的复杂度。


CF1555F Good Graph

初始有一张 $n$ 个点,没有边的无向图。$m$ 次询问加入一条 $u_i,v_i$ 之间权值为 $w_i\in\{0,1\}$ 的边,若加入之后图上不存在路径权值异或和是 $0$ 的简单环,则成功加入,否则不加入。求每次是否成功加入了给定的边。

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

离线,顺次遍历每条边,若它连接了两个连通块,则这条边 必定 会加入,于是把这些边拉出来加入,得到一个森林。

考虑剩余的边能够成功加入的条件。

  • 加入后直接构成的简单环异或和为 $1$;
  • 加入后直接构成的简单环不与已经存在的简单环有共边,即不能形成"环套环"。

所以现在需要判断的东西变为了,求树上一条路径是否完全没有被覆盖,以及覆盖一条树上路径。

树剖一下,线段树维护区间加,区间求和就好了,时间复杂度 $O(m\log ^2n)$。


CF1557D Ezzat and Grid

有一张 $n$ 行,无限长的网格,上面覆盖了 $m$ 条线段,每条线段用 $(i,l,r)$ 表示覆盖了第 $i$ 行的区间 $[l,r]$,问最少删除多少行,使得剩余的相邻两行都有至少一个相同位置都被线段覆盖,并输出方案。

$1\leq n,m\leq 3\times 10^5$,$1\leq l\leq r\leq 10^9$。

因为输出方案的步骤只需要稍加修改,所以只考虑如何求最多保留多少行。

首先把 $l,r$ 离散化掉,注意数组大小。

设 $f_i$ 表示以第 $i$ 行结尾,能保留的最大行数,$f_i=\max\{f_j\}+1$,其中 $i$ 和 $j$ 存在一个相同位置都被覆盖。

更进一步地,设 $g_i$ 表示位置 $i$ 上被线段覆盖时的最大的 $f$ 值,那么 $f_i$ 就等于所有第 $i$ 行线段对应区间的 $g$ 值的 $\max$ 再加一,然后把 $f_i$ 贡献到它对应的区间上,这个贡献直观感受是让区间对 $f_i$ 取 $\max$。

但不难发现对于一个 $i$,每次更新时 $g_i$ 是单调递增的,即如果这个位置 $i$ 在 $f_j$ 更新时被涉及,那么有 $f_j>g_i$,所以实际上区间取 $\max$ 的操作改为区间赋值即可。

需要用线段树实现区间赋值,区间查询 $\max$,方案的话把结点记录的信息改为 pair 即可。

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


[P7172 [COCI2020-2021#3] Specijacija](https://www.luogu.com.cn/problem/P7172)

大致题意:一棵 $n+1$ 层的树,第 $i$ 层有 $i$ 个结点,树从上往下,从左往右依次从 $1$ 开始编号,第 $i$ 层的结点 $a_i$ 会有两个儿子,同层其它点只有一个儿子,儿子从下一层的最左结点开始依次分配,$q$ 次询问两个点的最近公共祖先,强制在线

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

首先考虑这棵树里会有很多的直链,即这条链上的点除了链尾都只有一个儿子。如果我们用链尾结点代替这条直链,保留连通性建树,那么树的点数为最后一层的 $n+1$ 个点以及向上 $n$ 层每层新增的一个点,即 $2n+1=O(n)$。

思考这棵树的性质,我们发现询问的答案要么是其中一个点,要么是一个链尾,所以我们如果实际建出了这棵树,并能查询每个点对应的直链编号,那么就可以方便地回答询问。

考虑一个朴素的过程,对于每一层点分别维护它们对应的直链编号,观察自底向上维护的时候的更新可以发现,从第 $i+1$ 层到第 $i$ 层,只有第 $i$ 层的特殊结点和它后面的一个位置的编号合并成了一个新的编号,即只有 单点删除,查询第 $k$ 个没被删除的元素,单点修改 三种操作,这个过程可以用经典的主席树来解决。

于是这题就做完了,时间复杂度 $O(n\log n+q\log n)$。


bzoj 2889 Tree Conundrum

给定一棵 $n$ 个点的树,求有多少种方案可以把树分为若干联通子树,且每个联通子树的大小相等。

$1\leq n\leq 10^6$。

很神奇的一道题。

如果存在一个每棵子树大小为 $d$ 的合法分割方案,那么就需要有恰好 $\frac nd$ 个关键点来分割整棵树,即这 $\frac nd$ 个联通子树都以一个关键点为根,切去这些关键点连向父亲的边即得这些连通块。

不难发现这些关键点在原树上的子树大小都一定是 $d$ 的倍数,我们尝试考虑这样的点的个数不会超过 $\frac nd$,这一步是容易的,因为把这些点建出虚树,虚树上每个叶子节点都代表着互不重合的 $d$ 个点,而非叶子节点又必定比所有儿子节点的 size 和更大,这个大的幅度至少是 $d$,所以只有至多 $\frac nd$ 个关键点。

然后我们发现,如果 恰好可以找到 $\frac nd$ 个关键点,那么说明每个关键点都 恰好对应 着原树上的 $d$ 个点组成的联通子树,也就是 一种合法的划分方案。同时到这里也可以发现,同一个大小 $d$ 只有至多一个分割方案。

转化问题之后就是简单的 dfs 了。

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


CF1547E Coloring

有一个 $n\times m$ 的初始全为空的 01 矩阵,$q$ 次操作修改一个点 $(x,y)$ 为 $0,1$ 或清空。每次修改后询问有多少种把所有空位填上 $0,1$ 的办法可以让任意一个 $2\times 2$ 的子矩阵里都有恰好两个 $1$。

$1\leq n,m\leq 10^6$,$1\leq q\leq 3\times 10^5$。

考虑固定第一行或者第一列就可以确定整个矩阵,于是考虑对于每行每列分别统计答案,每一行的贡献可能是 $0,1,2$,列也同理,然后再减去可能出现的两种 $01$ 间隔的情况就是答案。

具体实现可以根据行的奇偶性记录到对应列上面,列也同理,如果出现一行既有 $0$ 又有 $1$ 贡献即为 $0$,如果一行都没有 $0,1$ 的贡献就是 $2$,行列分别乘起来再相加就可以了。注意还要减去可能满足的两种 $01$ 间隔的情况。

用一个 map 来记录每个点的值即可,时间复杂度 $O(n\log n)$。

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