UOJ Logo zhoukangyang的博客

博客

UOJ Round #29 题解

2025-02-17 11:51:29 By zhoukangyang

随机浏览

idea by GeZhiyuan, solution by GeZhiyuan, shr, std by shr, data by GeZhiyuan

算法 I

考虑必定是存在一些页面,如果到达了这些页面,就回到页面 $1$。可以直接枚举会回到 $1$ 的页面集合 $S$,然后暴力进行高斯消元,复杂度 $O(2^n \times n^3)$,预计通过 $12$ 分。

算法 II

考虑假设 $m$ 轮后,即使没有到达 $n$ 也不会继续操作,只要 $m$ 取到足够大误差就可以接受,复杂度 $O(m \times n^2)$。预计通过 $48$ 分。

通过精细卡常可能能通过 $72$ 分。

算法 III

考虑先强制让所有页面都不会按红色按钮,然后记 $f_i$ 表示目前在页面 $i$,要到页面 $n$ 期望要随机选择几次。每次找出最大的 $f_i$,如果最大的 $f_i$ 不为 $f_1$,则令到达这个页面后会点击红色按钮回到 $f_1$,每次消元复杂度 $O(n^3)$,又至多只会 $n$ 次让页面点击红色按钮,因此复杂度 $O(n^4)$。预计通过 $72$ 分。

算法 IV

考虑利用动态高斯消元优化 算法 III,复杂度 $O(n^3)$。预计通过 $100$ 分。

动态高斯消元的方法可以参考 [集训队互测2015] 最大异或和 的题解。

数字生命

idea by dead_X, solution, std by zhoukangyang, data by zhoukangyang, Rainbow_sjy

小故事

这题是三年前 dead_X 看错一道题后给我报的题意。听完题后我很快就想出了做法!而且感觉这个做法很趣味!之前没怎么见到过这种思路!

后来又在其他题/博客里面发现了这类做法,感觉有点错!但查询了一些选手的看法,他们认为即使见过这些也不简单!

WC2025 中我自己又讲了相关的内容,就当是抹平技术差距了(雾)

算法一

首先,我们差分 $a$ 序列,设差分结果为 $c$。

一次操作就是将 $c$ 的第 $p$ 个位置 $-1$(需要保证 $c_p\ge 1$),将 $c$ 的第 $p+len$ 个位置 $+1$。

此时我们可以将问题看成是,第 $i$ 个位置有 $c_i$($c_i$ 可以为负) 个石子。每次我们可以将一个石子向前移动 $len$ 步,最终我们要让每个位置的石子数清零。我们可以把这里的 "正 $c_i$" 看成一个石子移动的起点,一个 "负 $c_i$" 看成一个石子移动的终点。

容易发现,起点个数等于终点个数,且如果想要有解,则最多只会有 $m$ 个起点。

根据这个转化,我们可以写出 DP:从往后加入起点,记录此时已经匹配的终点和使用的操作。维护这个 DP 大约要 $\mathcal O(4^m)$ 的复杂度。

根据算法的复杂度和减枝程度,可以获得 $30\sim 75$ 分。

算法二

设 $G_{i,j}$ 表示从第 $i$ 个起点走到第 $j$ 个终点,可以使用哪些操作集合来进行操作。我们给每个 "操作集合" 随机赋值,并将其看成一个集合幂级数。

而我们想要求的是 $\sum_{p} \prod_{i} G_{i,p_i}$,其中集合幂级数的乘法是子集卷积。

注意到我们其实并不关心每个排列带的系数是什么,所以我们要求的也可以是 $\sum_{p} sgn(p) \prod_{i} G_{i,p_i}$。

这就是一个对集合幂级数求 det 的问题了。但是如果使用子集卷积,复杂度带的 $m$ 因子会过多。

我们发现我们可以直接使用或卷积。因为如果或卷积中有重的元素了,那么我们使用的操作的子集和一定和原序列的总和对不上,因此只需再对总和做限制即可。

算答案的每个点值需要 $\mathcal O(m^3)$ 的复杂度,总复杂度 $\mathcal O(2^mm^3)$。

人机验证

idea by xyf007, data, std by zhoukangyang, solution by zhoukangyang, EntropyIncreaser

小故事

这是 NOI2023 后的暑假时给出的做法。

当时 xyf007 找我问这个题。我看了一下发现就是求带深度限制的有根树计数,然后思考了一下,发现有些困难。感觉这是典题,所以咨询了 EI,EI 告诉我他也很好奇这题能不能做。

xyf007 告诉我这题能做,而且我之前说出过正确做法。我隐约感觉有些印象,就又开始思考这个问题。断断续续想了几天,我终于想出了一个低于平方的做法!而这题之前的做法并不正确。我把这个做法告诉了 EI,EI 提出用特征多项式优化的做法,能做到 $\mathcal O(n\sqrt n\log n)$。

近几天准备这道题的时候,我重新思考了一下这个问题,发现有了快速的多项式复合后又有另一种 $\mathcal O(n\sqrt n\log n)$ 做法,以及【数据删除】。

题解

显然,问题的难点在于求 $n$ 个点深度不超过 $k$ 的有标号有根树个数。

首先容斥,钦定一些元素的深度恰好为 $k+1$,然后把这些点和他们的祖先都标记了(即保留”虚树“上的点)。

真实的树就是在每个”虚树“上的点上长出一颗新的树,所以答案只和虚树上的点数有关。

可以据此写出一个看起来没啥变化的 DP 来统计虚树上的点数:

$$F_0=-x$$

$$F_i=x(\exp(F_{i-1})-1)$$

求出 $F_k$ 即可得到答案。

接下来我们考虑另一种 DP:

设 $dp_{d,r}(x)$,其中 $[x^c]$ 表示离叶子高度为 $d$ 的恰好有 $r$ 个点,且总点数恰好为 $c$ 的方案数。其中,有 $r \le \lfloor \frac{n}{d} \rfloor$。

从 $dp_{i-1}$ 到 $dp_i$ 的转移系数是个第二类斯特林数。我们要求的是 $dp_{k+1}$。

注意到 $dp_{d,r} = \frac{F_d^r}{r!}$。所以我们可以定一个阈值 $B$,用第一种 DP 算出 $dp_{B}$。

此时考虑如何用 $dp_{B}$ 获得 $dp_{2B}$。这里设 $m = \lfloor \frac{n}{B} \rfloor$

注意到第二维大小不大,因此可以考虑矩阵快速幂。如果直接使用矩阵快速幂,需要对一个 $len$ 维护 $m \times m$ 的矩阵 $G$,其中 $[x^c] G_{i,j}$ 表示第 $0$ 层有 $i$ 个点,第 $len$ 层有 $j$ 个点,总共有 $c$ 个点的有标号有根树个数。

接下来有两种做法。

做法1

把整个矩阵记下来很浪费。考虑设 $H_i(x) = \sum_j G_{i,j}y^j$,可以发现 $H_{i} = H_1^i$。因此只需记录 $H_1$。

接下来考虑如何"翻倍",即 $len\to len\times 2$。这无非计算 $\sum_i [y^i]H_i H^i$,对 $x$ 这一维插值,对 $y$ 这一维就是多项式复合。

使用 $\texttt {2log}$ 的多项式复合,我们可以做到 $\mathcal O(m^2len\log^2 n)$ 计算长度为 $len$ 的转移矩阵。而对于一个多项式 $F_x$,我们通过其计算 $F_{x+len}$ 可以做到 $\mathcal O(nm)$。

因此复杂度是 $\mathcal O(\frac{B}{len}\times nm+m^2len\log^2 n) = \mathcal O(\frac{n^2}{len}+m^2len\log^2 n)$。取 $len=\frac{n}{m\log n}$ 即可得到 $\mathcal O(nm\log n)$ 的复杂度。

$B$ 最初取 $\sqrt n$,总复杂度 $\mathcal O(n\sqrt n\log n)$。

做法2

这个转移矩阵是对角矩阵,有特征多项式 $f(y) = \prod_{i=1}^{m}(y-x^i)$。

由于 $F_i = dp_{i,1}$,序列 $F_i$ 有线性递推 $f$。我们计算出 $F_B,F_{B+1},F_{B+2},...,F_{B+m}$,然后只要计算出 $y^{B}\bmod f(y)$ 即可知道如何用 $F_{B},F_{B+1},...,F_{B+m}$ 线性表示出 $F_{2B}$。

考虑倍增计算 $y^{B}\bmod f(y)$。注意到 $y^k \bmod f(y)$ 在 $x$ 上的多项式次数是 $\mathcal O(km)$ 的,总大小是 $\mathcal O(km^2)$,因此需要的复杂度是 $\sum_{i} \frac{B}{2^i}m^2\log n = \mathcal O(\frac{n^2}{B}\log n)$。你也可以通过对对 $x$ 这一维插值、对 $y$ 这一维取模来计算这个式子。

$B$ 最初取 $\mathcal O(\sqrt n)$,总复杂度 $\mathcal O(n\sqrt n\log n)$。

暂别

2024-08-30 18:16:29 By zhoukangyang

一年接一年,又到了 UOJ 管理员的换届时刻!

我们这一届管理员(1kri, huahua, JohnVictor, zhoukangyang)在过去的一年中举办了一场 UR,一场UR,以及年度活动 Goodbye Round 与 UNR。多亏了为我们提供指导与帮助的 vfk vfleaking 与前管理 qingyuskip2004,帮我们上传了大量题目的 Rainbow_sjy, 以及这一年来为 UOJ 分享自己有趣的题目的 command_block, cmll02, Kubic, tzc_wk, Ecrade_, zjy0001myee。在无数的命题、造题、传题与修锅的过程中,是这个大家庭对 UOJ 共同的热爱,指引着我们又走过了一年。

当我是刚学 OI 的小朋友时,我便与 UOJ 第一次邂逅。当时我参加了 UOJ Long Round #1,鏖战四个小时终于通过了 T1,而在这题之后还有五道更难的题目,我感受到了这个 OJ 的深不可测。后来我在做 UOJ 比赛题的时候,我发现这些题目的质量普遍较高。这些题目常常蕴含着一些独特而惊艳的思想,这些思想让我受益匪浅。一代一代的管理员用自己纯粹的热情传递着 UOJ 的精神,打造着属于一代一代选手的思维乐园。

在 NOI 2023 结束前,青鱼与 127 找到了我,问我有没有兴趣来当 UOJ 管理员。出于对这个伟大 OJ 的热爱,我毅然决定接下了这个大锅。回顾当管理的一年,许多事情让我记忆犹新。UR26 比赛时我发现 T2 的一个子任务数据范围配错了,好在样例没问题,没对比赛造成影响;在 UR27 前,为了让这场比赛的 T3 不被浪费(我计划在 APIO 讲这道题)且让尽可能多的选手能参赛,我们反复地商讨比赛时间;还记得 UNR Day2 的前一天我还在参加 AWTF 的现场活动,而我还没完全造完我的题目,因此我没去最后的 KTV 活动,而是回到酒店造题造到凌晨;今天我试着将自己的账号封禁再用其他超管的账号把自己解封,却发现自己已经不再是超管了,这给我的我的 UOJ 管理任期画上了一个滑稽的句号。

我们相信下一届管理员能够比我们做的更好,将 UOJ 的这份精神继续发扬光大,建设这一算法竞赛的圣地。在接下来的一年中担任 UOJ 的管理员的四位分别是:

Rainbow_sjy, shr, yaoxi_std, Melania

祝你们四位一切顺利,祝 UOJ 有更光明的未来!

UOJ NOI Round #8 Day2 题解

2024-07-14 14:27:00 By zhoukangyang

D2T1

idea,solution,data,std by zhoukangyang

这题有很多做法,欢迎大家在评论区交流。

考虑设 $t_i$ 表示 $i$ 被删除的时间。

考虑从前往后依次确定 $t_i$。如果 $i$ 时刻在 $t_i$ 时刻被删掉,那么 $i$ 前面的第一个 $\ge t_i$ 的 $t$ 上的字符一定和 $i$ 不同。而 $t_i$ 是满足条件的值中最小的一个。

所以可以考虑对于每个 $j$ 记录 $i$ 前面第一个(下标最大的一个)满足 $t_{pos}\ge j$ 的 $s_{pos}$。

考虑记录该字符串。初始状态就是整个字符串均为 $s_1$。

加入位置 $i$ 的时候,修改即为在字符串中找到第一个 $\neq s_i$ 的字符 $p$,将其修改为 $s_p$。如果找不到则说明该位置不会被删除。

直接用动态规划维护是 $\mathcal O(n2^k)$ 的。

注意到我们其实只关心字符串中 $1$ 的个数!这样就能做到 $\mathcal O(nk)$ 了。

思考题:如果 $s_1$ 也会被删除该怎么做?(这题也能做到 $\mathcal O(nk)$。)

D2T2

idea,solution,data,std by zhoukangyang

致歉

本来这题是 $n\times n$ 矩阵找第 $n$ 小,只允许比较,要求次数 $\mathcal O(\sqrt n)$,放 Day2T3 的。

但是后来因为常数太大,卡不掉暴力,就改成了现在这个版本。

结果这题之前在一些地方的模拟赛里面出现过了,赛前没有查到一样的题,向大家道歉!!

题解

考虑提取所有偶数列,然后求出其中第 $(k-n)/2$ 小值。我们发现最后的答案一定大于等于这个值,所以前 $k$ 小的元素中我们已经确定出了 $(k-n)/2\times 2$ 个了,还差 $n$ 个。

现在我们只需要接下来再取出 $n$ 个元素即可。这个可以把每行第一个没被选的元素丢到 priority_queue 实现。

行列交替地做,操作次数是 $T(n,m) = T(m,n/2) + 2n$,有 $T(n,n)=6n$,还不能通过(然而数据较弱,部分选手直接实现了这个算法也通过了)。

我们发现如果 $(x-1,y)$ 和 $(x,y-1)$ 还没被选进前 $k$ 小,$(x,y)$ 就暂时不会被选。事实上,加上这个优化操作次数就是 $5n$ 的了。

我们证明从 $T(n/2,n/2)$ 的答案推到 $T(n,n)$ 的过程中我们最多只会问 $2.5n$ 次。

证明:考虑 $T(n/2,n)$ 到 $T(n,n)$ 的过程。设第 $i$ 行刚开始去了 $a_i$ 个元素($a_i$ 是偶数),最终取了 $b_i$ 个元素,那么最终我们会问 $n+|\{b_i\}|$ 次。在 $T(n/2,n/2)$ 中,我们询问了 $n/2 + |\{a_i\}|$ 次。;

我们先假装总询问次数是 $3n/2 + n + |\{a_i\}|$ 次,接下来观察我们会在什么情况下少问一些。

在做 $T(n/2,n)$ 时,如果 $a_i\neq a_{i-1}$,那么 $(i,a_{i}+2)$ 一定被问过了。

此时,如果 $a_i\neq b_i$,那么我们就利用上了 $(i,a_i+2)$ 的信息,询问次数 $-1$;而如果 $a_i = b_i$,那么 $b_i$ 中一定不会出现 $a_i+1$ 这个数,询问次数 $-1$。

综上,我们一定少询问了 $|\{a_i\}|$ 次,也就是说我们只会询问 $5n/2$ 次。所以总询问次数不会超过 $T(n,n) = T(n/2,n/2) + 5n/2$,即 $T(n,n) = 5n$。

D2T3

idea,solution,data,std by Kubic

$O(n\log^2 n)$

分治。处理所有跨过分治点的贡献。只需 $O(\log n)$ 代价即可转化到原问题。

离线,扫描值域。令当前扫描到 $x$。对于每个 $i$,维护 $p_i$ 表示第 $i$ 时刻分治中心左边距离中心最近的 $\le x$ 的数的距离,$q_i$ 表示右边的距离。

$x$ 增大时对 $p,q$ 的修改均为区间取 $\min$,用 $\text{segbeats}$ 维护即可。

还需要维护每个时刻的答案 $w_i$。第 $i$ 时刻 $\min\ge x$ 的区间数量即为 $p_i\times q_i$。因此 $x$ 增大时,需要令 $w_i\leftarrow w_i+p_i\times q_i$。

每个 $i$ 处维护四维向量 $(p_i,q_i,p_i\times q_i,w_i)$,用矩阵表示修改即可。时间复杂度为 $O(n\log n)$。

加上外层分治,总时间复杂度为 $O(n\log^2 n)$。

$O(n\sqrt n)$

可以把要求的东西转化为 $\sum\limits_{i=1}^n(suf_i-i)(i-pre_i)a_i$。

其中 $pre_i$ 表示 $i$ 前面第一个 $< a_i$ 的位置,$suf_i$ 表示 $i$ 后面第一个 $\le a_i$ 的位置。

考虑询问分块,将 $B$ 个询问分入同一个块中。

在进入每个块之前先将这个块中所涉及到的 $B$ 个位置设为 $+\infty$,然后计算 $pre$ 和 $suf$。

此时序列被这 $B$ 个位置分为了 $O(B)$ 段。

对于一个询问,我们分析填上这 $B$ 个位置的数对 $pre$ 和 $suf$ 的影响。只考虑 $pre$,$suf$ 的分析是类似的。

可能有一些 $pre$ 会变为这 $B$ 个位置之一。每个段内只有所有非严格前缀最小值的 $pre$ 可能改变。

我们用类似于求 $pre$ 的过程,对这 $B$ 个位置以及每个段内的最小值做单调栈。

到达一个段时,我们可以用当前的单调栈刻画出这个段中所有数的 $pre$ 的变化情况:对于一个当前段中的前缀最小值 $a_i$,我们找到单调栈中第一个 $< a_i$ 的数 $a_t$。如果 $t$ 是 $B$ 个位置之一,那么 $pre_i$ 会变为 $t$,否则 $pre_i$ 不变。

于是我们可以把一次询问转化为在序列上的 $O(B^2)$ 次询问,每次询问一个段中有多少个 $\le w$ 的数。

这样做的时间复杂度为 $O(\dfrac{n^2}{B}+nB^2)$,取 $B=n^{\frac{1}{3}}$ 可以得到 $O(n^{\frac{5}{3}})$ 的时间复杂度。

但我们可以进一步优化,可以发现,单调栈中有很多不变的数,我们可以在单调栈改变的时候将后面的数因为这次改变所产生的贡献全部计算出来。每次询问形如在第 $x$ 个段及之后的所有数中有多少个 $\le w$ 的数。

因为段只有 $O(B)$ 个,并且询问的 $w$ 也只有 $O(B)$ 种,所以我们可以用在每个段内双指针,并用二维前缀和预处理出每一种可能的询问的答案。

这 $O(B)$ 个点的贡献容易在过程中同时进行计算,这里不再赘述。

这样做的时间复杂度为 $O(\dfrac{n^2}{B}+nB)$,取 $B=n^{\frac{1}{2}}$ 可以得到 $O(n\sqrt n)$ 的时间复杂度。

UOJ NOI Round #8 Day1 题解

2024-07-13 20:36:57 By zhoukangyang

D1T1

idea,sol,data,std from Kubic

别急。

D1T2

idea from cmk666,solution from cmk666

记区间 $[l,r]$ 中颜色 $i$ 出现 $c_i(c_i>0)$ 次,如果 $i$ 只出现在 $S$ 中,那么有 $1$ 种选择方法,如果只出现在 $U/S$ 中,那么有 $1$ 种选择方法,否则有 $2^{c_i}-2$ 种选择方法。

考虑构造形式幂级数 $F_i(x)=(x-1)^2+2^{c_i}x,F(x)=\prod_i F_i(x)$ ,如果有 $K$ 种不同的颜色在区间 $[l,r]$ 中出现,那么答案就是 $[x^K]F(x)$。

考虑记 $y=(x-1)^2$ 那么 $F(x)$ 每一项的指数和是固定的 $K$,于是我们可以设 $G_i(x)=1+2^{c_i}x$,求出 $G(x)=\prod_i G_i(x)$,那么答案就是 $[x^K]\sum_i(x-1)^{2(K-i)}x^i[x^i]G(x)=\sum_i(-1)^{K-i}\binom{2(K-i)}{K-i}[x^i]G(x)$。

接下来观察模数的性质,因为$G_i(x)=1+2^{c_i}x,c_i>0$,所以有 $\forall i\ge 64,[x^i]G(x)\equiv 0\pmod{2^{64}}$,于是我们只需要求出 $G$ 的前 $64$ 项即可。

对于 $c_i\ge 64$,我们不用关心,因为 $G_i(x)\equiv 1\pmod{2^{64}}$,对 $G$ 的求解没有影响。

否则,对于 $1\le k\le 63$,依次统计出 $d_k=\sum_i[c_i=k]$,于是 $G(x)=\prod_{k=1}^{63} (1+2^kx)^{d_k}$,容易用组合数预处理出 $(1+2^kx)^{d_k}$ 的每一项系数,并且对于每一个 $k$,其只有前 $\lfloor \dfrac{63}{k}\rfloor$ 的值在模意义下不为 $0$,如果我们从大到小依次枚举 $k$ 乘起来,它依然保持这个性质,于是单次计算 $G(x)$ 的复杂度就是 $\Theta(\log^2 P)$ 的了。

如果用扫描线配合树状数组求出 $d_k$,那么总时间复杂度就是 $\Theta((n+q)\log n\log P+q\log^2 P)$ 的。

D1T3

idea,data,std from unputdownable, solution from unputdownable,zhoukangyang

$n \le 2$

一个点只有两个出边。

如果两者字符不一样,那么直接走对应字符的出边就行。

难处理的是两条出边字符相等的情况。

但是 $n \leq 2$,注意到向右走一定不劣,所以贪心先匹配第一行,然后再往第二行匹配即可。

总复杂度 $O(L+nm+q\log m)$,也可以做到单组查询 $O(1)$。

$n \leq 3$

贪心失效了!真的失效了吗?

考虑我们的贪心什么时候会挂。 $$ S=\text{xxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxx}\color{black}\texttt{aaaaa}\\ &\color{blue}\texttt{aaaax}\color{black}\texttt{aaaaaaaaaaaa}\\ &\texttt{aaaa}\color{blue}\texttt{xxxxxxxxxxx}\color{black}\texttt{aa}\\ \end{aligned} $$ 考虑选择一个位置提前往下拐。

注意到如果在蓝色分支之前就往下拐,一定不比蓝色优,否则蓝色一定能接到那个路径上去。

所以应该选择最后一个能往下拐的位置往下拐,然后就是 $n=2$ 的部分了。

注意到能往下拐的位置一定满足 $T_{2,x}=T_{1,x+1}$,或者在末尾,而这个是好维护的

记得在两种贪心中取较大的一个。

总复杂度仍是 $O(L+nm+q\log m)$,也可以做到单组查询 $O(1)$。

$n \leq 4$

贪心还有救吗? $$ S=\text{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}\\ \\ \begin{aligned} T=\ &\color{red}\texttt{xxxxxxxxxxxxxxxxxx}\color{}\texttt{aaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aa}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{}\texttt{a}\color{blue}\texttt{x}\color{black}\texttt{aaaaaaa}\\ &\texttt{a}\color{green}\texttt{x}\color{}\texttt{aaaaaaaaaaaaaaaaaaaaaa}\\ &\texttt{a}\color{green}\texttt{xxxxxxxxxxxxxxxxxxxxxxx}\\ \end{aligned} $$

这样子可以把上述贪心卡死。

但是如果能找到一个直达第三排的位置,从那个位置往下拐贪一下,就还有救。

因为考虑所有从第二行转移到第三行的列,如果这一列的第一行无法到达,那么可以被走完第一行再接 $n=3$ 的贪心;

而当我们找到一个能直达第三行的位置,和 $n=3$ 的情况就差不多了,可以证明这是最优的决策之一。

观察到能到第三排的位置应该满足 $T_{2,x}=T_{1,x+1},T_{3,x}=T_{1,x+2}$;或者 $x$ 在第一行贪心匹配部分(上图红色)末尾两个字符(需要特判)。

将走完第一行再接 $n=3$;第一行走到剩下一个再接 $n=3$;选择最后一个能往下拐的位置往下拐;找到最后一个能直达第三行的位置往下拐四种贪心拼起来即可通过 $n=4$。

总复杂度仍是 $O(L+nm+q\log m)$,也可以做到单组查询 $O(1)$。

$L,m,q \leq 1000$

对于询问暴力跑一个朴素的 DP,记 $f_{i,j}$ 表示能否走到 $(i,j)$ 这个点,单次询问复杂度 $O(nm)$,

总复杂度 $O(L+nm+qnm)$。

$L,m,q \leq 10^4$

注意到 DP 状态只有 $01$,直接压位用位运算做 DP,单组询问复杂度 $O(m)$;

总复杂度 $O(L+nm\sum+qm)$。

$n \leq 7$

贪心彻底没救了,因为此时路径的形态会变得相当复杂。

注意到 $n$ 很小,考虑想办法维护上述动态 DP。

首先将矩阵转换为斜矩阵以方便理解(第 $i$ 行向右平移 $i-1$ 个字符),这样每一步是向右或者向右下走,即第 $i$ 步一定走到第 $i$ 列。

维护 DP,第 $i$ 列的状态只和第 $i-1$ 列的状态以及需要匹配的字符有关。

难点在于转移矩阵会随着询问的字符串而改变。

想办法固定每个位置的转移矩阵。

注意到如果先贪心在第一行匹配,那么在和第一行匹配上的这个区间内,转移矩阵是固定的。

直接动态 DP 维护此时的 DP 状态;如果下面的行已经没有可达的位置了,那么贪心匹配第一行一定是最优的;否则跳到下方第一个可以到达的行,然后递归。

预处理动态 DP 矩阵,查询时只需要做至多 $n$ 遍向量乘区间的转移矩阵。

视实现的不同复杂度大约 $O(L \log L+n^3m\log m+qn^3)$。

$n \leq 10$

注意到矩阵很小,可以压位,单次矩乘 $O(n^2)$。

上猫树,注意到每次乘的是单个转移矩阵,而不是若干转移矩阵的积,其中非 $0$ 元素只有 $O(n)$ 个。

这样预处理时单次矩乘 $O(n)$。

复杂度 $O(L \log L+n^2m \log m+qn^2)$。

由于实测时间瓶颈在 $SA$ 预处理上,所以即使你的询问多一个 $n$ 或者多一只 $\log$,如果卡常较为精细也能通过。

谢罪

部分乱搞获得了 $84$,复杂度错误的 $O(m2^{\frac n 2})$ 以及 $O(m2^n)$ 也通过了。

UOJ NOI Round #8 公告

2024-07-02 22:50:14 By zhoukangyang

转眼间又是一年 NOI 了,为了帮大家备战 NOI,延续 UOJ 的传统保留项目,UOJ NOI Round #8 将在 7 月 12 号到 7 月 14 号隆重举行!

为了方便阅读,同时也因为管理员比较鸽,这次的 UNR 没有特别的主题。

比赛时间

笔试模拟将于 7 月 12 日晚 19 点开始,将进行半个小时。

Day 1 的比赛将于 7 月 13 日上午 8 点半开始,将进行五个小时,共三道题。

Day 2 的比赛将于 7 月 14 日上午 8 点半开始,将进行五个小时,共三道题。

比赛难度

比赛的难度将和 NOI2023 相近,相信对绝大部分选手来说题目是具有一定的挑战性的。

题目中可能拥有若干道非传统题(可能包括但不限于交互题、提交答案题、通信题),大家可以放心食用。

出题阵容

拯救这一年度的 UNR 的出题人将在稍后公布。各位可以先行无奖竞猜出题人的名单。

这场比赛除笔试外将计入 rating。

比赛奖项

这次比赛将会根据三次比赛的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字),其中比赛的前三十名将成为这次训练的金牌得主,第三十一名到第一百二十名将获得银牌,第一百二十一名到第二百名将获得铜牌。(得奖人数将根据参赛人数进行调整)

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

zhoukangyang Avatar