前言

这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。

锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。

对应题目点链接即可做。

本期涉及算法：模拟

并查集，暴力枚举

id="_20">题目清单

1.寻宝

题目：

href="https://www.luogu.com.cn/problem/P1076"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/c3940d877f2c48af81e383a6d8edb2bf.png#pic_center">

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/87de8a84a9ec45dda4f269977392e280.gif#pic_center">

解法：模拟

优化

src="https://i-blog.csdnimg.cn/direct/f6f7df6d94b74421b4150328dddb1cf8.png#pic_center">

但是每层楼都去找那个房间的话，时间复杂度大，可以优化，用一个cnt[i]数组存：表示第i层楼有楼梯的房间数，用要找的第s个%cnt[i],

注意如果取模后=0，就是找第cnt[i]个符合要求的房间。

代码：

string"><iostream>

class="token

comment">//注意：房间编号从0开始

class="token

punctuation">}

2.村村通

题目：

href="https://www.luogu.com.cn/problem/P1536"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/620be81c454f4d33ba7955582d178d76.png#pic_center">

解法：图的性质

并查集

这道题要将已经连接好的部分城镇和未连接的城镇都连通（可以是间接连接），连接的边数

输入多组数据按ctrl

string"><iostream>

class="token

punctuation">}

3.Diamond

S

题目：

href="https://www.luogu.com.cn/problem/P3143"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/cc6b308cc8ad47c4aee0d4744e50d552.png#pic_center">

解法：暴力枚举

预处理

滑动窗口（优化）

错误的解法：贪心

滑动窗口，先选⼀段长度「最大」的，再选⼀段⻓度「次大」的。

但是这样是错误的，因为第⼀次

的选择会影响第⼆次的选择，两者加起来「不⼀定是最优」的。

比如：

[1,

7。

因此，先选⼀段最长，再选⼀段次长的方法是不对的。

两个同时要考虑:

那么我们可以

i

位置为「分界点」，「左边」选⼀段，「右边」选⼀段：

左边选：[1,

[1,

的长度。

这样我们就可以枚举出所有的情况，「左右两部分相加」的最大值（max）

n]区间内，符

合要求的「最长子串」的长度，类似动态规划预处理：

数组f[i]表示[1,

[1,

的最长子串的

长度，两者最大值即可；

对于g[i]，先找出

[i

的最长子串的

长度，两者最大值即可。

如何找出

为结尾位置」

的最长子串的长度：

在滑动窗口的过程中，我们每次找到⼀段「符合要求的子串」时，都可以知道这段⼦串的终止位置right。

因此，做⼀次「滑动窗口」，就可以把所有位置的信息都「预处理」出来。

「以

为起始位置」

的最长子串的长度，倒着再来⼀次即可。

代码：

string"><iostream>

class="token

string"><algorithm>

class="token

punctuation">[right

class="token

punctuation">[right

class="token

punctuation">[right

class="token

punctuation">}

4.Apple

G

题目：

href="https://www.luogu.com.cn/problem/P2690"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/1188f3b0f6da443d9e5c2d9c866762d9.png#pic_center">

解法：线性dp

1.状态表示：

f[i]

[j]

时，能拿到的最⼤分数。

2.状态转移方程：

先计算当前这个时刻，移动

次之后，能否拿到苹果：

如果

c.

3.最终结果：

f[n]这⼀行中的最大值。

string"><iostream>

class="token

punctuation">}

Summing

S

题目：

href="https://www.luogu.com.cn/problem/P3131"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/0d70c6b77f904421a82afbe4c7b51fa4.png#pic_center">

解法：前缀和

哈希表

同余

挑一个和为7的倍数的最长区间。

sum[i]

-sum[j]

x，为了使得区间更长，j要尽可能靠左，区间长度ret

j

x

src="https://i-blog.csdnimg.cn/direct/20db7a5fb75b42058c4f090996ea3642.png#pic_center">

那么，这道题就转化为之前常做的题：找一个和为一个数（这里是7的倍数）的最长区间，前缀和

哈希表

下标，注意初始化：mp[0]

当然，由于一个数

0~6，那么可以用数组来存，id[n]

0~6，

7，数组值：下标。

注意，初始化id[0]

0,

0,而数组有默认值，为了不让其产生影响，就用memset(id,

-1,

id),将为处理的标记为-1，用于后面的判断。

代码：

1.哈希表：

string"><iostream>

class="token

string"><unordered_map>

class="token

punctuation">;unordered_map

class="token

punctuation">}

2.数组代替哈希表：

string"><iostream>

class="token

string"><cstring>

class="token

punctuation">}

6.图的遍历

题目：

href="https://www.luogu.com.cn/problem/P3916"

rel="noopener

src="https://i-blog.csdnimg.cn/direct/2359c2f4c7c34d0e8ff92b0d4dcb931c.png#pic_center">

解法：正难则反-反图

从任意⼀点出发，去找能到达的最⼤结点，用dfs/bfs暴搜，n^2，(10

^2,

最差情况（特殊图，要把所有结点都遍历一次）时间复杂度会超。

正难则反-反图：但是如果对原图建⼀个反图，从节点编号最大的点出发，能走到的点都是原图能到达的点。

这样走会使时间复杂度降低。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/a520d9237b9145a49b5daeb79dae7e9b.png#pic_center">

因此，建⼀个反图，按照节点编号从大到小dfs搜索⼀遍即可(这里从大到小还会起到一定的剪枝作用)。

代码：

string"><iostream>

class="token

string"><vector>

class="token

punctuation">;vector

class="token

comment">//存结果，同时看是否走过

class="token

comment">//存反图edges

class="token

function">push_back

class="token

punctuation">}

src="https://i-blog.csdnimg.cn/direct/086eeb3102ad48e8b2b0659e901295a2.gif#pic_center">

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/863256cbcc2449a681f64e2aa0449d44.gif#pic_center">

加油！

志同道合的人会看到同一片风景。

看到这里请点个赞，关注，如果觉得有用就收藏一下吧。

后续还会持续更新的。

class="post-meta-container">