walkalone

题解

/ 注册

全部文章 / 题解（共76篇）

题解 | 2023 年牛客多校第九场 B 题题解

题意：给定 a,ma,ma,m，构造一个非负整数 uuu，使得 au≡u(modm)a^u \equiv u \pmod mau≡u(modm)。1≤a<m≤1091 \le a<m \le 10^91≤a<m≤109，0≤u≤10180 \le u \le 10^{18}0≤u≤...

数论

2023-08-15

9 500

题解 | 2023 年牛客多校第三场 J 题 Fine Logic

题意：给定 nnn 个点和 mmm 对偏序关系 ⟨u,v⟩\langle u,v\rangle⟨u,v⟩，构造最少的排列数目 kkk，使得在这 kkk 个排列中至少有一个排列满足 u<vu <vu<v。1≤n,m≤1061\le n,m \le 10^61≤n,m≤106。解法：...

拓扑排序

2023-07-25

2 232

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

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

数据结构倍增

2023-07-25

3 281

题解 | 2023 年牛客多校第三场 H 题 Until the Blue Moon Rises

题意：给定一个长度为 nnn 的序列 {a}i=1n\{a\}_{i=1}^n{a}i=1n，一次操作可以选择两个不同的数字 aia_iai 和 aja_jaj 执行 ai←ai+1,aj←aj−1a_i \leftarrow a_i+1,a_j \leftarrow a_j-1ai←ai...

构造

2023-07-25

0 215

题解 | 2023 年牛客多校第三场 G 题 Beautiful Matrix

题意：给定一个 n×mn\times mn×m 的字符矩阵 {S}(i,j)=(1,1)(n,m)\{S\}_{(i,j)=(1,1)}^{(n,m)}{S}(i,j)=(1,1)(n,m)，定义一个 n×nn\times nn×n 的子矩阵是优美的当且仅当 ∀i,j∈[1,n]\forall i...

字符串 Manacher

2023-07-25

2 376

题解 | 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 245

题解 | 2023 年牛客多校第三场 D 题 Ama no Jaku

题意：给定一 n×nn\times nn×n 的 01 矩阵，每次可以翻转一行或一列，执行若干次操作。若将操作完成后的矩阵的每一行从做到右视为一个二进制数 {r}i=1n\{r\}_{i=1}^n{r}i=1n，每一列从上到下视为 {c}i=1n\{c\}_{i=1}^n{c}i=1n，要求 m...

并查集

2023-07-25

0 328

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

题意：给定 nnn 表示有一个由 {1,2,3,⋯ ,2n}\{1,2,3,\cdots,2n\}{1,2,3,⋯,2n} 构成的 2n2n2n 张牌的初始牌堆，同时自己这里有一个空的牌堆。执行以下的操作：翻开牌堆顶的一张牌，并放在自己牌堆的堆顶。记自己牌堆堆顶的一张牌大小为 xxx。如果初始...

动态规划

2023-07-25

2 468

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

G Steins’ Game 2 题意：有 nnn 堆石子 {an}\{a_n\}{an}，满足 0≤a1≤a2⋯≤an≤m0 \leq a_1 \leq a_2\cdots \leq a_n \leq m0≤a1≤a2⋯≤an≤m。Alice 与 Bob 依次从非空的一堆拿走正数个石子使得...

多项式动态规划

2022-09-10

1 293

2022 年牛客多校第三场签到题题解

A Ancestor 题意：给出两棵 nnn 个节点的树 A,BA,BA,B，A,BA,BA,B 树上每个节点均有一个权值，给出 kkk 个关键点的编号 x1,x2,⋯ ,xkx_1, x_2, \cdots, x_kx1,x2,⋯,xk，问有多少种方案，使得去掉恰好一个关键点使得剩余关键点在...

图论贪心

2022-09-08

0 204