ddhw111

分类

题解(16)

/ 注册

全部文章（共16篇）

题解 | #分层图最短路#

分层图最短路链接：https://ac.nowcoder.com/acm/problem/236176 来源：牛客网做法：直接去连边的话因为数据范围过大，所以会出现tle的现象，也有段错误的现象不知道是为什么，所以对于层与层之间的边，我们建立一个平台，同层的点到这个平台的距离为0，层与层之间的距...

C++

2024-08-23

1 149

题解 | #宝藏猎人#

链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿： ...

C++

2024-06-13

2 184

题解 | #货船#

货船链接：https://ac.nowcoder.com/acm/problem/236172 来源：牛客网有 n个货物，需要装入货船，第 i 个货物的重量是 wi 。货船的最大载重量是 A ，请问在不超过货船最大载重量的前提下，一次最多能运送多少重量的货物。做法：一眼是01背包，但是无论是物...

C++

2024-06-12

1 169

题解 | #最大m个子段和#

链接：https://ac.nowcoder.com/acm/problem/235953 来源：牛客网给你一个数组 a ，包含 n 个整数，你需要在数组 a 中选出不相交的 m 个连续子段，每个子段的长度至少为 1 。定义每一个子段的贡献为子段内数字的和，你需要求出这 mmm 个子段的贡献之和...

C++

2024-06-11

1 207

题解 | #雾粉与最小值(简单版)#

链接：https://ac.nowcoder.com/acm/contest/84527/C 来源：牛客网做法暴力解法就是对于x的每一个位置去遍历最小和最大长度，那么复杂度肯定爆炸，我们先考虑一下最小长度和最大长度的关系，对于一个数来说，如果拓展的最小长度的最小值都小于x，那么最大也只能更小，所...

C++

2024-06-08

1 196

题解 | #合并回文子串#

链接：https://ac.nowcoder.com/acm/problem/13230 来源：牛客网输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回...

C++

2024-06-07

1 170

题解 | #孙悟空救师傅#

孙悟空救师傅链接：https://ac.nowcoder.com/acm/problem/235903 来源：牛客网师傅又被妖怪抓走了。师傅被困的宫殿可以看作一个 n×nn\times nn×n 的由字符构成的矩阵，每一个字符表示一个房间。字符'K'表示孙悟空的起始位置，'T'表示师傅被困的位置...

C++

2024-06-03

3 206

题解 | #草药大师#

草药大师链接：https://ac.nowcoder.com/acm/problem/235951 来源：牛客网做法1 因为最大容量有1e9，我们需要剪掉一些情况，对于每次物品我们只能拿一次，那么，其实也是从尾开始跑，只不过我们把从最大容量改成最大能放进的容量，如果总容量减去这一个物品的容量比原...

C++

2024-05-10

2 142

题解 | #多重背包#

多重背包链接：https://ac.nowcoder.com/acm/problem/235950 来源：牛客网做法：适用于物品数量不是无限但又不止一个的背包问题，一开始想到的是将n个相同重量的物品当作n个不同的物品，但完全背包的复杂度已经汗流浃背，所以我们需要把这个重复的n进行优化，我们尽量去...

C++

2024-05-03

2 226

题解 | #[NOIP2004]合唱队形#

合唱队形链接：https://ac.nowcoder.com/acm/problem/16664 来源：牛客网 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T...

C++

2024-05-03

2 269