walkalone

分类

题解(77)

/ 注册

全部文章（共77篇）

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

G Good red-string 题意：给定一个长度为 nnn 的串，仅由 r，e，d，?构成。问能够找到一种将全部的 ?转化为 r，e，d中的一种字符，使得最后的串由 n3\dfrac{n}{3}3n 个不相交的 red子序列构成。例如 reredd符合条件而 rederd不符合条件。保证 n...

贪心

2022-08-26

0 276

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

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

图论数据结构

2022-08-26

0 304

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

L Lndjy and the mex 题意：给定长度为 nnn 的序列 {ai}\{a_i\}{ai}，满足 ∑ai=n\sum a_i=n∑ai=n。问由 a0a_0a0 个 000，a1a_1a1 个 111，……，ana_nan 个 nnn 构成的全部 n!∏i=0nai!\dis...

多项式计数

2022-08-26

0 376

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

K Killer Sajin's Matrix 题意：给定 n×mn\times mn×m 的矩阵，要求在其中填入 kkk 个 111 使得每行每列 111 的个数均为奇数。输出一个合法方案或者报告无解。n,m,k≤1×105n,m,k \leq 1\times 10^5n,m,k≤1×105。解...

构造

2022-08-26

1 442

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

K NIO's OAuth2 Server 题意：有 kkk 个元素和 nnn 个由这 kkk 个元素构成的集合 {Sn}\{S_n\}{Sn}，问由这 kkk 个元素生成的全部 2k−12^k-12k−1 个非空集合中有多少个 TTT 集合满足 T⊆⋃k=1iSk\displaystyle T ...

FWT

2022-08-16

0 272

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 388

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

G Magic Spells 题意：给定 kkk 个串 {Si}\{S_i\}{Si}，问在每个串中都出现的本质不同回文子串个数。∑∣Si∣≤3×105\sum|S_i| \leq 3\times 10^5∑∣Si∣≤3×105，k≤5k \leq 5k≤5。解法：kkk 较小，因而可以考虑对...

字符串回文自动机

2022-08-16

1 357

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 330

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

E Longest Increasing Subsequence 题意：构造一个长度不超过 100100100 的排列，使得其最长上升子序列个数恰好为 mmm 个。m≤1×109m \leq 1\times 10^9m≤1×109。解法：为了保证 LIS 的个数，一个基础的构造是 2,1,4,3,...

构造

2022-08-16

4 356

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

C Global Positioning System 题意：给定 nnn 个点 mmm 条边的图，图上每条边有一向量。现在这些边上的向量恰好有一个错误的，原始的图上任意环上向量和为 0⃗\vec 00，找出有多少个可能错误的边。n,m≤1×105n,m \leq 1\times 10^5n,m≤1...

图论树

2022-08-16

0 302