walkalone

分类

题解(77)

/ 注册

全部文章（共8篇）

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

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

动态规划

2023-07-25

2 655

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 493

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 年牛客多校第十场 K 题题解

K You are given a tree... 题意：给定一个 nnn 个节点的树，树上每个点有颜色 aia_iai，边有边权。问从中选择 kkk 个颜色不同的点，他们构成的生成子图的边权值和最大值。n≤1×103n \leq 1\times 10^3n≤1×103，k∈[2,5]k \in ...

动态规划状态压缩随机化

2022-08-27

0 314

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

牛客多校第七场 J 题解

J 题题意：求长度为 nnn，且每个数字都在 [0,k−1][0,k-1][0,k−1]，使得区间连续和为 kkk 倍数的子区间有 ttt 个的序列个数。n,k≤64n,k \leq 64n,k≤64，t≤n(n−1)2t \leq \dfrac{n(n-1)}{2}t≤2n(n−1)。解法：区...

动态规划前缀和

2022-08-11

1 337

牛客多校第六场 C 题题解

C Forest 题意：给定 nnn 个点 mmm 条带权边的无向图，问从中选出若干条边和全部的点构成的 2m2^m2m 张子图中，最小生成森林的边权值和。n≤16n \leq 16n≤16，m≤100m \leq 100m≤100。解法：首先从小到大的对边进行排序，等边权的按照边编号排序，保证生...

状态压缩动态规划

2022-08-08

2 442

牛客多校第三场 D 题题解

D Directed 题意：给定一个 nnn 个点以 111 为根的树，现在要从 sss 出发到 111 号节点。现在随机选择 kkk 条树边变成单向边，方向由儿子指向父亲。同时人在某一个节点以等概率选择出边，问期望多少步走到 111 号节点。解法：对于一个有根树，从儿子节点 vvv 走到父节点 ...

动态规划期望

2022-07-28

8 316