每次更新5题，持续更新中…欢迎Ctrl+D收藏本页面！

代码部分请看视频，希望大家可以多看几遍视频照着敲一遍，收获更大。

luogu题单：洛谷带刷100题（1~50） – 题单 – 洛谷

1~5题视频讲解：希望下次秒懂的是算法_哔哩哔哩_bilibili

1.P1002 [NOIP2002 普及组] 过河卒

首先将整个地图进行一个偏移，即向右下方进行一格移动，令起点从(0, 0)变为(1, 1)，其他点类似。

设状态dp[i][j]为从(1, 1)到(i, j)的路径条数，容易得到状态转移方程：

dp[i][j] = dp[i – 1][j] + dp[i][j – 1]

特别地，若(i, j)为马的控制点时，dp[i][j] = 0，同时注意状态转移时跳过起点（起点单独进行初始化）。

答案为dp[n][m]（注意此时的n, m进行了偏移）。

2.P1003 [NOIP2011 提高组] 铺地毯

将地毯信息用结构体存下，由于询问只有一次，所以我们可以从后往前扫描所有地毯，检查点(x, y)是否在地毯中，如果在则得到了答案。

3.P1008 [NOIP1998 普及组] 三连击

假设我们的三元组为(i, j, k)，枚举i（注意i的范围），有j=2i，k=3i。

再将i,j,k分解后检查是否分别为9位独立的数字。

4.P1028 [NOIP2001 普及组] 数的计算

设状态dp[i][j]表示长度为i且最后一位数值为j的方法数量，容易得到状态转移方程：

dp[i][j] = sum_{k=2j}^{n}dp[i-1][k]

右边这个式子是可以通过后缀和处理出来的。

最后的答案就是将整个dp数组求和。

5.P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

我们知道：

atimes b=gcd(a,b) times lcm(a, b)

所以我们可以枚举a，b可以直接算出，然后再判断二元组(a, b)是否合法即可。

6~10题视频讲解：七夕可以不过，算法必须要学_哔哩哔哩_bilibili

6.P1031 [NOIP2002 提高组] 均分纸牌

先假想这么一种情况，若纸牌数量是可以为负数的，那么至多n-1次移动一定可以使得纸牌均分。

操作方法就是从左往右对于每一个位置，如果纸牌数量少于均值，就从右边拿（即便会拿成负数），如果多于均值，就放到右边去。

现在来解决“负数”的问题，假如上面一共操作了m次，那么一定存在一种方案，通过调整操作次序，使得整个操作序列是合法的，所以就不必担心出现“纸牌数量为负数”的问题。

7.P1036 [NOIP2002 普及组] 选数

看一眼数据范围，可以使用搜索，我们搜索出一个子集树（即枚举从n个中选出k个数字的所有情况），然后再用 O(sqrt{n}) 的方法判断素数即可。

dfs函数有三个参数，分别是dep（当前层数），cnt（已经选了多少个数字），sum（所选数字的和）。

8.P1060 [NOIP2006 普及组] 开心的金明

这道题可以转化为经典的01背包问题，即m个物品，n的容量，每个物品的体积为v[i]，价值为v[i] * w[i]。

关于几种经典的背包问题，我在ET-Campus算法基础班中有讲过，现在录播已经上线了，支持在线播放，大家可以去了解一下，也算是对作者一点点小小的支持，多谢各位老爷啦~购买方式请看视频讲解！

当然这道题的物品数量较少，应该也可以采用搜索+剪枝的方式求解。

9.P1100 高低位交换

本题较简单，考察对于基础数据类型和位运算的理解。使用unsigned int类型存储数字，然后将左移16位和右移16位的结果“或起来“即可实现高低位交换。

10.P1097 [NOIP2007 提高组] 统计数字

本题有两种解法。

解法一：

由于数字可能很大，所以用桶是不行的，我们可以使用STL中的map，统计完数字后直接遍历输出即可。

解法二：

将输入的数组进行排序，然后计算每一段相同数字的长度，输出即可。

11~15题视频讲解：希望下次秒懂的是算法题_哔哩哔哩_bilibili

11.P1094 [NOIP2007 普及组] 纪念品分组

算法标签：贪心、排序、双指针

每一组最多两个，为了使得组数尽可能少，就需要使得每一组的纪念品价格之和尽量接近w。

于是我们可以先将数组排序，然后利用双指针的思想，每次选价格最大和最小的两个进行配对，如果可以凑成一组，就凑成一组，如果不行，就将较大价格的单独作为一组。

12.P1102 A-B 数对

算法标签：map

要求A-B=C的数对个数，这里C是一个正数，说明A和B一定是不相等的，且这里的元素值较大。

先用map存下每个数字出现的次数。

再枚举A，然后对应的B=A-C，即算一下有多少个数字等于A-C即可，这个可以用map直接求出来。

13.P1105 平台

算法标签：结构体排序、暴力枚举

先将所有的平台存下来，再根据h为第一关键字升序，id为第二关键字降序（因为题目要求高度相等时选编号小的）进行排序。

枚举每一个平台，去找所有比他更低的平台，看下会落到哪个上面即可，注意擦边的不算落上去，同时答案是以id为下标的，最后输出即可。

14.P1111 修复公路

算法标签：图论、并查集、连通块、结构体排序

将所有边存到结构体里，按照t升序排列，从前往后顺序遍历（t从小到大），用并查集维护连通关系，维护连通块的个数，当个数为1的时候说明得到答案了，如果遍历完个数都没变为1说明没有答案。

并查集相关的知识在ET-Campus算法基础班中我也有详细地讲过，关于并查集的结构、原理、路径压缩、按秩合并等等，强烈推荐有语法基础但算法基础较薄弱的同学了解一下：

15.P1115 最大子段和

算法标签：前缀和、贪心

这题有两种解法，贪心法和前缀和法。

解法一（贪心法）：

从前往后枚举并求子段和，当子段和<0时，与其接到后面去，不如直接将这个字段舍弃掉。

根据这个贪心选择性质可以求出结果。

解法二（前缀和）：

计算出前缀和，我们知道子段[l, r]的和是prefix[r] – prefix[l – 1]，枚举r得到prefix[r]，记录左边最小的prefix[l – 1]，求prefix[r] – prefix[l – 1]即可。

其实还有一种分治法的方法，这种方法一般是学校会教给你的，但是复杂度相比于贪心法和前缀和会更高，这里就不讲咯~

第16~20题视频讲解：https://www.bilibili.com/video/BV1zF411r7xU

16.P1147 连续自然数和

标签：数学、因数分解

本题实际上是要我们求出所有满足以下条件的二元组(l, r)：

l le r space and space (l + r)(r – l + 1) =2M

直接枚举l, r相对困难，我们可以先对2M进行因数分解（假设分解为x1, x2, …, xn），然后(l+r)和(r-l+1)就只能在因数中进行取值。

对于某一对(xi, xj)，我们可以得到以下二元一次方程组：

left{begin{matrix} l+r=x_i / r-l+1=x_j end{matrix}right.

求解即可得到l, r的取值，再判断l, r是否合法即可。

17.P1125 [NOIP2008 提高组] 笨小猴

标签：字符串、素数判断、桶

遍历字符串，用桶记录下每个字符出现的次数，再遍历桶求出maxn和minn（注意跳过没出现过的字符），再判断(maxn – minn)是否为一个质数即可。

18.P1605 迷宫

标签：dfs

从起点开始dfs搜索，每当走到终点一次就将答案+1即可，由于地图很小所以不会超时。

注意dfs中的细节。

在ET-Campus算法基础课中，我讲解过dfs、bfs、dijkstra单源最短路、floyd多源最短路等经典图论算法，感兴趣的可以了解一下：

19.P1090 [NOIP2004 提高组] 合并果子

标签：优先队列、贪心

首先，我们知道一共需要进行n-1次合并操作，基于贪心的思想，使得每次合并的代价最小（收益都是一样的），我们选数目最少的堆进行合并，这样做还能使得产生出来的这个新的堆数目最小，让后面的合并操作的代价也尽可能小。

所以我们只需要将n堆果子的数目存到一个优先队列中，然后每次选出最小的两个合并，并把合并出来的新堆push进去，直到优先队列中仅剩一个数字。

过程中将消耗的体力求和即可。

20.P1037 [NOIP2002 普及组] 产生数

标签：图论、组合计数

根据规则构建一个图，求出对于每个数字(0~9)能够有多少种取值。

比如我要求数字x可以变为多少种数字，方法是在图上从x开始跑bfs或dfs看能够走到多少个点即可。

然后遍历每一位，通过初始的数字可以知道当前这一位上可以有多少种取值，根据分步乘法原理，计算出总方案数。

第21~25题视频讲解：

21.P1164 小A点菜

标签：动态规划、背包、计数dp

我们定义dp[j]表示到目前为止，使得总价格为j的方案个数，初始化dp[0] = 1。

可以得到状态转移方程（假设当前物品的价格为a[i]元）：

dp[j] = dp[j] + dp[j – a[i]]

意思是说当前总价格为j的方案，可以分成“不点当前这个菜”和“点当前这个菜”两部分，其方案数分别为dp[j]和dp[j – w]。

这里需要注意的是，因为我们状态是从小的转移到大的，所以我们需要从后往前进行遍历来转移，这个写法有点像01背包，具体的原理我在算法基础课中有详细讲过，还画了几次图来着哈哈哈哈感兴趣的可以了解一下：

最终输出dp[M]即可。

22.P1192 台阶问题

标签：计数dp、动态规划

我们定义dp[i]表示走到i的方案数，这个方案数可以划分为“往下第1个台阶过来“、“往下第2个台阶过来”、….、“往下第k个台阶过来”一共k个部分，于是可以得到状态转移方程：

dp[i] = sum_{j=1}^{k}dp[i – j]

注意取模和j的范围，最后输出dp[n]即可。

23.P1170 兔八哥与猎人

标签：数学

这是题目样例的情况，我们研究一下什么情况下是安全的。

如果两个点之间，存在一个整数点，则说明是安全的。

那么我们可以发现两点会形成一个直角边长度分别为|ax – bx|和|ay – by|的直角三角形，如果中间存在整数点，等价于|ax – bx|, |ay – by|不互质，即gcd(|ax – bx|, |ay – by|) != 1。

于是代码就很好写了。

24.P1181 数列分段 Section I

标签：贪心

这是一个很典型的贪心模型。

记录sum和ans（初始化为1），当sum超过m时截断，更新sum和ans即可。

25.P1364 医院设置

标签：图论、dfs

对于一棵树，我们可以将树以图的形式存下来，枚举根节点（任意一个点作为根节点都会生成一棵树），然后把医院放到根节点上，用dfs计算此时的答案（就是每个节点的权值乘上深度再求和），然后将答案取小即可。

ans=sum_{u in nodes}w[u] * dep[u]

第26~30题视频讲解：每天刷79题很难吗？哪李难了？分数涨没涨有没有认真刷题（第六期）_哔哩哔哩_bilibili

26.P1628 合并序列

标签：字符串、入门

因为数据量较小，直接使用string.find()函数来检查即可。

27.P1403 [AHOI2005] 约数研究

标签：数学、思维

如果对于每个数字i去枚举所有因子的话，复杂度是 O(nsqrt{n}) ，于是我们转换一下想法，用类似“埃氏筛法”的思路，我们不再去枚举约数，而是对于每个数字去枚举倍数。

第一重循环次数为n，第二重循环次数取决于第一重循环，整体复杂度为：

n+n/2+n/3+…+1=nsum_{i=1}^{n}lfloorfrac{1}{n}rfloor sim nlog(n)

28.P1644 跳马问题

标签：简单dp

设状态dp[i][j]表示到从(0, 0)到(i, j)的方案总数。

因为马只能从左往右跳，所以容易知道dp[i][j]能从dp[i – 1][j – 2],dp[i – 2][j + 2],dp[i – 2][j – 1],dp[i – 2][j + 1]转移过来。

初始化dp[0][0] = 1，最后输出dp[m][n]。

29.P1122 最大子树和

标签：dfs、简单树形dp、贪心

设dp状态：dp[x]表示以x点为根的子树中，包含x点的所有连通块的最大权值。

转移的方法就是，设y为x的儿子，那么贪心地想，dp[x]可能要连上y（dp[y] > 0），也可能不连上y（dp[y] <= 0）。

采用dfs来进行转移，求出dp数组，答案不一定是以1为根的，所以要遍历整个dp数组找到最优解。

30.P1510 精卫填海

标签：背包dp

设dp状态，dp[i]表示到当前石头为止（1~n顺序枚举），得到总体积为i的石头所需的最小体力。

需要初始化dp为无穷，dp[0] = 0。

实际上这里和01背包的优化方法很类似，原本是还有一维表示到第几个石头为止，但是给优化掉了。

这里篇幅有限，我在算法基础课里面有详细的讲解，如果感兴趣想要学习的同学欢迎点这里了解一下：

状态转移方程是：

dp[j] = min(dp[j],dp[j – k[i]] + m[i])

注意这里需要保证j >= k[i]，j的范围要到2e4（因为可能存在某些石头体积大而所需体力小），最后在dp[v ~ 2e4]找到最小值然后用c减去它即可。