walkalone

分类

题解(77)

/ 注册

全部文章（共13篇）

题解 | 2023 年牛客多校第三场 I 题

题意：有一个 nnn 个点的树，第 iii 个点拥有的颜色种类由二进制数 cic_ici 定义。qqq 次询问，每次从 uuu 出发到 vvv，初始自选颜色，一秒的时间里可以移动到相邻同色节点（即该节点有自身的一种颜色），或者在一个点变换自身颜色（必须是这个点已经有的颜色）。问花费的最少时间。1≤...

数据结构倍增

2023-07-25

3 495

题解 | 2023 年牛客多校第三场 E 题

题意：给定一张 G(n,m)G(n,m)G(n,m) 的有向图，使用 dfs 算法求解从 111 开始的单源最短路，问给定的图能否在任何边遍历顺序下都正确输出。1≤n,m≤1051 \le n,m\le 10^51≤n,m≤105。解法：为什么我们要找支配树？可以考虑以下三个例子：基本错误型：...

支配树数据结构

2023-07-25

0 416

2022 年牛客多校第一场补题记录

A Villages: Landlines 题意：有一个电站位于 xsx_sxs，需要在 [xs−rs,xs+rs][x_s-r_s,x_s+r_s][xs−rs,xs+rs] 的范围内设置至少一个电塔将电引出。n−1n-1n−1 个用电处位于 xix_ixi，需要在其范围 [xi−ri...

动态规划贪心数据结构字符串

2022-09-08

0 414

2022 年牛客多校第十场 D 题题解

D Mi Re Do Si La? So Fa! 题意：给定串 SSS，询问其每个子串的完整循环节长度和。例如串 aaaa的完整循环节长度有 1,2,41,2,41,2,4 三种。∣S∣≤1×106|S| \leq 1\times 10^6∣S∣≤1×106。解法：显然每个子串 S[l,r]S[l...

字符串 RMQ 数据结构

2022-08-27

1 353

2022 年牛客多校加赛场 C 题题解

C Cmostp 题意：给定字符串 SSS，qqq 次询问 SSS 的全部本质不同子串中有多少个子串的右端点落入 [l,r][l,r][l,r] 中的。 ∣S∣,q≤5×105|S|,q \leq 5\times 10^5∣S∣,q≤5×105。解法：显然在 SAM 上可以将前缀 [1,i][1,...

数据结构字符串

2022-08-26

0 299

2022 年牛客多校加赛场 B 题题解

B Bustling City 题意：给定一个 nnn 个点 nnn 条边的有向图，第 iii 个点恰有一条出边指向 aia_iai。在每个点上恰有一个商人，一个时刻位于点 iii 处的商人会走到 aia_iai 号节点，问每个节点第一次有 kkk 个商人同时在该点的时间。n,k≤1×106n,...

图论数据结构

2022-08-26

0 300

2022 年牛客多校第九场 I 题题解

I The Great Wall II 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai}，将其划分为连续的 kkk 段，每一段的花费为这一段的最大值，问 k∈[1,n]k \in [1,n]k∈[1,n] 的最小花费。n≤8×103n \leq 8\times 10^3n≤8×10...

动态规划数据结构

2022-08-16

3 384

2022 年牛客多校第九场 F 题题解

F Matrix and GCD 题意：给定 n×mn \times mn×m 的矩阵，其中 [1,nm][1,nm][1,nm] 的数字均只出现一次，问所有的连续子矩阵的 gcd⁡\gcd gcd 之和。n,m≤1×103n,m \leq 1\times 10^3n,m≤1×103。解法：考虑 ...

数据结构数论

2022-08-16

2 328

2022 年牛客多校第八场 I 题题解

I Equivalence in Connectivity 题意：给定 kkk 个 nnn 的点的图。对于第 iii 个图，其由 pip_ipi 图删除或者新增一条边构成（保证 pi<ip_i<ipi<i），问这 kkk 张图依据连通性可以分成多少组。n,k≤1×105n,k ...

数据结构分治

2022-08-14

0 687

2022 年牛客多校第八场 G 题题解

G Lexicographic Comparison 题意：给定两个长度均为 nnn 的排列 A,PA,PA,P。有以下 qqq 次三类操作：交换 AxA_xAx 与 AyA_yAy；交换 PxP_xPx 与 PyP_yPy；查询 APxAP^xAPx 与 APyAP^yAPy 的大...

数据结构平衡树

2022-08-14

0 306