MENU

做题笔记 since 2022.4.4

LG4314 CPU监控

线段树维护历史最值的模版题,要求支持区间加和区间推平,查询区间最大值以及区间历史最大值。

首先容易想到维护区间最大值 max,区间历史最大值 hmax,区间加的 tag add 以及区间推平的 tag cov

这里存在的细节就是,在一次推平操作后,之前的 add 一律失效,并且在有推平操作的情况下,接下来的 add 就都可以被转换为推平操作了,只需要对应的修改 cov 即可,这样在实现时会方便许多。

然后你会发现这还不够。

比如说区间加 $10$,然后区间加 $-5$,这个时候下传标记,我们就会用 $5$ 来更新儿子的 hmax,而这显然是错误的,所以我们另外需要维护一个历史最大的 add,以及对应的历史最大的 cov,这也是另一个我们把 add 转换为 cov 的原因,就是为了避免两个历史最大标记的冲突。

标记下传的过程一定要仔细实现,要不然很容易漏掉某个标记的更新。

LG3736 字符合并

区间 dp(注意到 $n\le300$),状压 dp(注意到 $k\le 8$)。

长度为 $len$ 的串经过若干次变换后,长度最终会变为 $(len-1)\bmod(k-1)+1$。

那么转移方程显然:
$$
f_{l,r,S\times2+0/1}=\max\{f_{l,p,S}+f_{p+1,r,0/1}\}
$$

这里我们要求 $r-p-1\equiv 0\pmod{k-1}$,也就是要求 $[p+1,r]$ 变换之后长度应为 $1$。

另外在 $r-l\equiv0\pmod{k-1}$ 时要特殊处理,先让 $[l,p]$ 和 $[p+1,r]$ 合并出长度为 $k$ 的串 ,然后再整体合并一次,加上贡献即可。

总复杂度 $O\left(\dfrac{n^32^k}{k}\right)$,但是上界很松,可以通过。

CF452F Permutation / LG2757 等差子序列

询问给定 $1\sim n$ 的排列中是否存在一个长度为 $3$ 的等差子序列。

从左到右扫一遍,记录每个数是否出现过,考虑某个时刻,现在我们拿到的数是 $a_i$,假如存在以 $a_i$ 为中项的等差子序列,则意味着存在 $a_i-k$ 和 $a_i+k$,一个在之前出现过,一个没出现过。

换言之,假设不存在以 $a_i$ 为中项的等差子序列,任取 $a_i-k$ 和 $a_i+k$,它们的出现状态应该相同,也就是说整个状态串构成了以 $a_i$ 为中心的回文串,用线段树维护 hash 即可快速判断。

LG2757 航线规划

无向图上动态删边,询问两点间割边数量,保证图中无自环、重边,保证图始终连通。

删边不好维护,考虑将操作离线下来逆序处理,删边变为加边。

tarjan 求割边肯定不现实,考虑另外一种做法,先把 dfs 树求出来,对于任意一条非树边 $u\to v$,在 dfs 树上将 $u\rightsquigarrow v$ 路径上所有边打上标记,那么这些边不可能是割边,反之所有没有被标记的边一定是割边。

于是我们现在只需要支持树上的路径覆盖和路径求和两种操作,树剖维护即可。

LG5310 Ynoi2011 遥远的过去

为什么会无聊到来做 Ynoi 呢

其实是从 等差子序列 那题过来的,一个是线段树维护 hash,一个是平衡树,感觉很 nb。

感觉我学编程的经历和题目背景有异曲同工之妙。

区别大概在于,我参加了一次科创大赛,然后做了个感觉很 nb 的游戏,代码也非常炫酷,这玩意现在在旧电脑的硬盘里还找得到,结果没拿奖,从此对这种科创大赛彻底丧失了兴趣,觉得这种东西水太深。

机缘巧合跑去 hsy 学信竞,当时在教 C++,但是我已经学过 Python 了,就觉得 C++ 跟 Python 比起来实在是显得十分丑陋,然后参加选拔考试(笔试)的时候,因为代码写的比较不合常规,被扣了好多分,那个时候觉得 OI 说是竞赛还是脱不开应试教育的恶劣风气,但还是学下来了,就成了现在这个样子,越来越菜了 /fad。

但是这里是做题笔记,而不是给我写奇怪文字的地方,所以我们回到题目上来。

类似于字符串匹配,只不过我们只需要两个串的 rank 数组相同即可。

kmp 看着不太合理,所以考虑 hash。

文本串始终不变,那我们大可直接把文本串所有长度为 $m$ 的子串的 hash 值算出来,丢到一个 map 里去。然后用平衡树动态维护模式串的 hash 值,直接在 map 里查询即可。

关于 hash 函数的选取上,大体上有两种思路,$\sum rank_i\times base^{i}$ 以及 $\sum i\times base^{rank_i}$,为了方便快速求出文本串所有长度为 $m$ 子串的 hash 值,这里采用前者(现在想想用后面一个实现起来也不困难)。

平衡树动态维护 hash 值的时候,我们考虑如何将两个串 $L,R$ 合并在一起,由于是在平衡树上,$L$ 的 rank 肯定整体比 $R$ 小。

在合并的时候,我们相当于将 $R$ 的 rank 整体提高了 $len(L)$,反映在 hash 值上,就是加上了 $\sum len(L)\times base^{rank_i}$,所以,我们再额外维护一个 $\sum base^{rank_i}$ 即可。

单模数试了半天过不去,实在没办法就魔改了一个双模数。

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

PJ21618 ExPR#1 乘积 / ABC239Ex Dice Product 2

感觉 public judge 的题解一直都写的非常简洁,尤其是对于 A 题,大概是搬题人水平普遍太高,认为这种题完全是签到题不需要多讲,但是对于我这种人确实是不太友好。

讲一讲我的一些想法。请注意如无特殊说明,变量的取值均为整数。

首先我们希望设 $f_i$ 表示当 $M=i$ 时,或 $M>i$ 时的期望步数,后者似乎并不方便转移,而前者的问题也很明显,我们不知道 $f_i$ 会由哪些状态转移而来,概率的计算上也就变得更加复杂了,同时还存在的问题是终止状态并不唯一,不方便统计答案。

所以我们考虑这样的一步转化,将 dp 的过程倒过来,也就是乘法变为除法,初始时我们让 $f_i(i>m)=0$,也就对应了初始状态,由于对于任一状态而言,能够转移到的状态都恰好有 $n$ 个,我们容易得到转移方程:
$$
f_i=1+\frac{1}{n}\sum_{j=1}^n f_{ij}
$$
方程右边出现了 $f_i$,我们将其挪到左边来,容易得到:
$$
f_i=\frac{n}{n-1}+\frac{1}{n-1}\sum_{j=2}^nf_{ij}
$$
暴力转移即可,最终答案即为 $f_1$(对应正序转移时的起始状态),至此我们得到了一个 $O(nm)$ 的算法。

pjudge 的题解中没有提到上述对于问题的转化 /yun。

接下来,我们观察可以发现,对于 $\left\lfloor \dfrac{m}{i} \right\rfloor$ 相同的 $i$,$f$ 值一样。

这一点可以用归纳法证明,对 $i$ 进行归纳,$f_i$ 会从 $f_{ij},j\in[2,n]$ 转移而来,考虑若 $\left\lfloor\dfrac mi\right\rfloor$ 相同,则 $\left\lfloor\dfrac m{ij}\right\rfloor=\left\lfloor\dfrac{\left\lfloor m/i\right\rfloor}{j}\right\rfloor$ 相同,于是易证。

但是,如果我们要深究存在这一现象的原因,考虑这样一件事情。

对于 $f_i$ 和 $f_j$,我们设 $x$ 表示使 $ix>m$ 最小的 $x$,类似的,对于 $j$ 设 $y$,假如 $f_i$ 和 $f_j$ 相等,则 $x$ 和 $y$ 应该是相等的,这一点从感性上来说应该容易理解。于是我们可以得到 $\left\lceil\dfrac{m+1}{i}\right\rceil=\left\lceil\dfrac{m+1}{j}\right\rceil$,我们知道 $\left\lceil\dfrac{m+1}{i}\right\rceil=\left\lfloor\dfrac{m}{i}\right\rfloor+1$,所以原命题同样得证。

所以,我们设 $g_i$ 表示 $f_k,\left\lfloor\dfrac{m}{k}\right\rfloor=i$ 的值,有:
$$
g_i=1+\frac1n\sum_{j=1}^ng_{\lfloor\frac{i}{j}\rfloor}
$$
化为:
$$
g_i=\frac{n}{n-1}+\frac{1}{n-1}\sum_{j=2}^ng_{\lfloor\frac{i}{j}\rfloor}
$$
记搜即可。

根据整除分块的分析方法,我们知道总状态数为 $|\{\lfloor m/k\rfloor\}|=\sqrt m$,总复杂度为 $O\left(\sum\limits_{i=1}^\sqrt{m}\sqrt{m/i}\right)$。

不会算,所以积一下:
$$
\begin{aligned}
&\int_{1}^{\sqrt m}\sqrt{\frac{m}{x}}\mathrm{d} x\\
=&\int_{1}^{\sqrt m}\sqrt m\cdot x^{-\frac12}\mathrm dx\\
=&O(m^{\frac34})
\end{aligned}
$$
实际上和杜教筛是一样的。

LG5514 柠檬

考虑每一段的端点颜色一定相同,要不然多余的部分也无法对当前段作贡献。

然后分颜色进行斜率优化即可。

值得注意的是在本题中,我们希望最大化 dp 的值,所以要维护的是上凸包,同时 $x$ 单调增,$k$ 单调增,那么就应当使用单调栈。

是道斜率优化好题。

LG6400 UMNOZAK / BZ1183 Umnozak

首先是显然的数位 dp,但是题目所定义的「自积」并不方便直接维护。

对于 $x=\overline{a_1a_2\dots a_k}$,定义 $p(x)=\prod_i a_i$,因为 $a_i\in[0,9]\cap \mathbb{Z}$,所以 $p(x)$ 的质因子仅有 $2,3,5,7$。

我们有 $p(x)\le 9^k$,$x=\sum_i a_i10^i>10^k$,于是 $x>p(x)$。

又因为 $A,B\le10^{18}$,于是 $p(x)<10^9$。

我们知道,$10^9$ 以内质因子仅有 $2,3,5,7$ 的数极少,事实上,如果你枚举一下容易发现这样的数仅有 $5194$ 个。

那么考虑枚举满足条件的 $p(x)$,然后进行数位 dp,记录当前各位数字之积中 $2,3,5,7$ 质因子的个数,这里略去实现细节。

总复杂度为 $O(k\log^5B)$,其中 $k=5194$,这个 5log 实际上是 $2,3,5,7,10$ 为底数各一个,我也不知道这个复杂度分析是不是对的,从实际效率来说应该没什么问题。

BZ3329 Xorequ

给出的方程是:
$$
x\oplus3x=2x
$$
两边同时异或 $x$:
$$
\begin{aligned}
3x&=x\oplus 2x\\
x+2x&=x\oplus 2x
\end{aligned}
$$
我们知道 $x+2x=x\operatorname{|}2x+x\operatorname{\&}2x$,$x\oplus 2x=x\operatorname{|}2x-x\operatorname{\&}2x$,由于这两者相等,于是:
$$
x\operatorname{\&}2x=0
$$
也就是说,$x$ 中不存在相邻的两个 $0$。

对于第一问直接数位 dp 即可,第二问考虑设 $f_{i,0/1}$ 表示考虑前 $i$ 位,以 $0/1$ 结尾的方案数,有转移:
$$
\begin{cases}
f_{i,0}=f_{i-1,0}+f_{i-1,1}\\
f_{i,1}=f_{i-1,0}
\end{cases}
$$
实际上和 fibonacci 数列一致,本来想用通项公式直接水,但是似乎 $\sqrt5$ 在 $\bmod 10^9+7$ 下不存在二次剩余,所以老老实实矩阵加速即可。

LG6669 清华集训2016 组合数问题

考虑 lucas 定理:
$$
\binom nm \equiv \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p
$$
实际上就是对 $n$ 和 $m$ 进行了 $p$ 进制拆分,然后每一位取组合数再全部乘起来。

在本题中也一样,如果将 $i,j$ 进行 $k$ 进制拆分后分别为 $\overline{a_1a_2\dots a_l}$ 和 $\overline{b_1b_2\dots b_l}$,那么有:
$$
\binom{i}{j}\equiv\prod_{t=1}^l\binom{a_t}{b_t}\pmod k
$$
由于保证了 $k$ 为质数,$\dbinom{a_t}{b_t}=0$ 当且仅当 $a_t<b_t$,所以题目要求等价于 $i$ 的 $k$ 进制表示中至少有一位比 $j$ 的小。

容斥一下变为每一位都不小于 $j$ 后数位 dp 即可。

PJ21613 PR#1 删数

其实很简单,但是之前看题解就是没有 get 到点。

首先题意的转化是容易理解的,求出差分数组,然后操作变为合并两个相同的数变为原来的两倍。

从二进制来看,变为原来的两倍意味着左移,而左移显然不会对 $d_i/\mathrm{lowbit}(d_i)$ 进行改变,换言之也就意味着 $d_i/\mathrm{lowbit}(d_i)$ 不同的两个数永远不可能被合并。

这意味着我们可以按照 $d_i/\mathrm{lowbit}(i)$ 对原序列进行分段,在每一段中我们可以将每个数都只保留 $\mathrm{lowbit}(d_i)$,这也就完成了「不妨设 $d_i$ 均为 $2$ 的幂次」这一步。

设 $f_i$ 表示前 $i$ 个数至少能合并为多少段,$g_{i,j}$ 表示在每一段中,以 $i$ 为右端点合并出 $2^j$ 时的左端点,递推转移即可,复杂度为 $O(n\log V)$,其中 $V$ 为值域。

或者说我们也可以不分段,直接设 $g_{i,j}$ 表示以 $i$ 为右端点合并出 $j$ 时的左端点,当然要求 $j=d_i\times2^k$,用 map 维护状态即可,代码实现更为简单粗暴,复杂度由于 map 变为 $O(n\log^2 V)$,但也足以通过此题。

PJ21614 PR#1 守卫

每个连通块可以只保留最小生成树,因为每个守卫负责的连通块最终肯定是只会保留最小生成树的,我们任取原图的一个导出子图,导出子图也一定存在一个最小生成树是原图最小生成树的子图。

剩下的部分容易用网络流描述。

  • 守卫向可以前往的结点连费用为 0,流量为 1 的边。
  • 生成树上的边向两个端点连费用为边权,流量为 1 的边。
  • 源点向守卫和边连费用为 0,流量为 1 的边。
  • 原图中结点向汇点连费用为 0,流量为 1 的边。

然后判合法一方面需要所有守卫被匹配,一方面需要所有原图中结点被匹配。

你可以选择先只连守卫 $\to$ 结点的边,跑一次费用流判断前者,再把树边 $\to$ 端点的边连上,再跑一次费用流判断后者,第一次流的流量是不用撤回的。

PJ21625 PR#3 最小生成树

给一种与题解不同的,更容易理解的,但是很可能存在错误的证明。

我们的网格图从上到下行数递增,从左到右列数递增。

Lemma. 1 最上面一行的所有横向边和最左边一列的所有纵向边一定会被选取。

也就是像这样:

net05

Proof. 我们考虑任意的一个生成树:

net01

第二行缺纵向边,第一列缺横向边,我们希望通过从同一行或同一列调整一条边的位置,来使得生成树符合条件。

由于保证了 $A,B,C,D$ 单调不降,所以这样调整必然不劣,接下来只需要证明一定存在合法的调整方案。

在断开一条边之后,整棵树会被分为两个连通块,为了使修改后的图仍然是生成树,我们需要保证接下来所连边的两个端点分别属于这两个连通块。

那么我们不妨考虑这样一个过程:首先连上缺失的横向边/纵向边,此时图中必然会出现一个环,我们只要删去环上另外一条与缺失边处于同一列/行的边即可,这样的边一定存在,原理与勘根定理类似。$\blacksquare$

在这个例子中,修改后的图如下:

net02

删去的边用粉色虚线代替,下同。

Lemma. 2 在 Lemma. 1 的基础上,必然存在一个最优解,使得 $\forall (x,y),x\in[2,n],y\in[2,m]$,使得边 $(x,y)\to (x-1,y)$ 和 $(x,y)\to(x,y-1)$ 中「恰好」存在一条。

换言之,就是在固定最上面一行的横向边和最左边一列的纵向边后,余下未连边的结点都「恰好」向左或向上连了一条边。

Proof. 首先,显然任意这样连边都是合法的,可以归纳证明连通性,接下来由总边数可知图中不存在环,故必然是一棵生成树。

我们仍然考虑将任意生成树调整至符合条件,这里接着使用 Lemma. 1 中的例子。

net03

此时图中会存在若干个点既没有向左连边,也没有像上连边。在例子中,这样的点被标记为了绿色,我们称这种点为「空」的,而与之相反的,我们称既向左连边又向上连边的点为「满」的。

对于一个空点,在其右下方必然存在一个满电。

否则,考虑满点与其所有左上方点构成的导出子图,这个子图将包含 $|V|$ 条边,于是必然存在一个环,这与原图是生成树矛盾。

于是,我们可以任取满点对应的横向边或纵向边,移动到空点上即可,由于满点在空点的右下方,这样调整必然不劣。$\blacksquare$

在这个例子中,调整后的图如下:

net04

根据 Lemma. 1 和 Lemma. 2,我们容易得到一个构造答案的方式,首先固定最上面的横向边与最左边的纵向边,然后对于余下所有点,贪心的选择向左连边或向上连边即可。

注意到 $\min\{A+B,C+D\}=A+B+[A-C+B-D>0](A-C+B-D)$,于是容易通过二分+前缀和优化复杂度至 $O(n\log m)$。

Archives Tip
QR Code for this page
Tipping QR Code