合集 - 算法提高课-原神社区-米游社

排序：最早

1.1 数字三角形模型

107.摘花生题目: Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地（如下图），从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有

0

3

1.2.1 最长上升子序列模型(1)

110.怪盗基德的滑翔翼题目: 怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操

1

5

1.2.2 最长上升子序列模型(2)

115.拦截导弹题目: 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，

0

3

1.3.1 背包模型(1)

118.多重背包问题III 题目: 有N种物品和一个容量是V的背包。第i种物品最多有Si件，每件体积是Vi，价值是Wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出

0

3

1.3.2 背包模型(2)

122.二维费用的背包问题题目: 有N件物品和一个容量是V的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是vi，重量是mi，价值是Wi。求解将哪些物品装入背包，可使物品总体积不超过背

1

3

1.3.3 背包模型(3)

127.背包问题求具体方程题目: 有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi，价值是Wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最

0

4

1.3.4 背包模型(4)

131.货币系统(1) 题目: 给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。输入格式第一行，包含两个整数n和m。接下来n行，每行包含一个整数，表示一种货币的面值。输出格式共

2

10

1.4 状态机模型

137.大盗阿福题目: 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有N家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，

0

5

1.5 状态压缩DP

141.小国王题目: 在n×n的棋盘上放k个国王，国王可攻击相邻的8个格子，求使它们无法互相攻击的方案总数。输入格式：共一行，包含两个整数n和k。输出格式：共一行，表示方案总数，若不能够放置

0

1

1.6 区间DP

145.环形石子合并题目: 将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。请编写一个程序，读入堆数n及每堆的

1

5

1.7 树形DP

150.树的最长路径题目: 给定一棵树，树中包含n个结点（编号1~n)和n—1条无向边，每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说，要找到两个点，使得它们的距离最远。注意：路径

0

4

1.8 数位DP

156.度的数量题目: 求给定区间 [X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15,Y=20, K=2, B=2，则有且仅有下列三个数满足题意：

0

3

1.9 单调队列优化的DP问题

162.最大子序和题目: 输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。输入格式第一行输入两个整数n,m。第二行输入n个数，代表长度为n的整数序

0

2

1.10 斜率优化的DP问题

168.任务安排1 题目: 有N个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这N个任务分成若干批，每一批包含连续的若干个任务。从时刻0开始，任务被分批加工，执行第i个任务所需

1

5

2.1.1 BFS中的Flood Fill和最短路模型

172.池塘计数题目: 农夫约翰有一片N*M的矩形土地。最近，由于降雨的原因，部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内，如果包含雨水，则用 W 表示，如果不含雨水，则用

0

3

2.1.2 BFS中的多源BFS-双端队列BFS

178.矩阵距离题目: 给定一个N行M列的01矩阵A，A[i][j]与A[k][l]之间的曼哈顿距离定义为： dist(A[i][j]), A[k][l])=|i-k|+|j-l| 输出一个N行M列

0

3

2.1.3 BFS中的双向广搜和A-star

181.字串变换题目: 已知有两个字串 A,B及一组字串变换的规则（至多6个规则）: A1->B1 A2->B2 规则的合义为：在A中的子串 A1可以变换为 B1、A2可以变换为 B2…。例如：A=

0

3

2.2.1 DFS中的连通性和搜索顺序

184.迷宫题目: 一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n*n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense

0

4

2.2.2 DFS之剪枝

189.小猫爬山题目: 翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲港的它们再也不想徒步走下山了（鸣咕>_＜）。翰翰和达达只好花钱让它们坐索道下山。

0

5

2.2.3 DFS之迭代加深、双向DFS、IDA

193.加成序列题目: 满足如下条件的序列X（序列中元素被标号为1、2、3...m)被称为“加成序列： 1、X[1]=1 2、X[m]=n 3、X[1]<X[2]<...<X[m-1]<X[m] 4

0

4

3.1.1 单源最短路的建图方式

197.热浪题目: 德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!! 他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。农夫John此时身先士卒地承担起向德克萨斯运送大

1

9

3.1.2 单源最短路的综合应用

203.新年好题目: 重庆城里有几个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同

0

6

3.1.3 单源最短路的扩展应用

207.选择最佳线路题目: 有一天，琪琪想乘坐公交车去拜访她的一位朋友。由于琪琪非常容易晕车，所以她想尽快到达朋友家。现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。

34

3.2 floyd算法及其扩展应用

211.牛的旅行题目: 农民John的农场里有很多牧区，有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条

1

8

3.3.1 最小生成树的典型应用

215.最短网络题目: 农夫约翰被选为他们镇的镇长! 他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。约翰

6

17

3.3.2 最小生成树的扩展应用

220.新的开始题目: 发展采矿业当然首先得有矿井，小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记了考虑矿井供电问题。为了保证电力的供应，小FF想到了两种办法： 1.在

3

30

3.4 SPFA找负环

224.虫洞题目: 农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。虫洞非常奇特，它可以看作是一条单向路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。农夫约翰的每个农场中包

0

11

3.5 差分约束

227.糖果题目: 幼儿园里有N个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分

7

42

3.6 最近公共祖先

231.祖孙询问题目: 给定一棵包含几个节点的有根无向树，节点编号互不相同，但不一定是1~n。有m个询问，每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。输入格式输入第一行包括一个整数

21

3.7 有向图的强连通分量

235.受欢迎的牛题目: 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，编号从1到N，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C

0

4

3.8 无向图的双连通分量

239.冗余路径题目: 为了从F个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的

0

5

3.9 二分图

242.关押罪犯题目: S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个

0

17

3.10 欧拉路径和欧拉回路

247.铲雪车题目: 随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双向车道，道路的两个方向均需要铲雪。因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它

0

25

3.11 拓扑排序

251.家谱树题目: 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。输出一个序列，使得每个人的孩子都比那个人后列出。输入格式第1行一个整数n，表示家族的人数

5

35

4.1 并查集

255.格子游戏题目: Alice和Bob玩了一个古老的游戏：首先画一个nxn的点阵(下图n=3)。接着，他们两个轮流在相邻的点之间画上红边和蓝边： [图片] 直到围成一个封闭的圈（面积不必为1)为

1

7

4.2 树状数组

260.楼兰图腾题目: 在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上（比楼兰古城还早）生活着两个部落，一个部落崇拜尖刀('V')，一个部落崇拜铁锹('^')，他们分

3

25

4.3.1 线段树(1)

265.最大数题目: 给定一个正整数数列a1, a2, ……,an，每一个数都在0~p-1之间。可以对这列数进行两种操作： 1.添加操作：向序列后添加一个数，序列长度变成n+1； 2.询问操作：询问

2

12

4.3.2 线段树(2)

268.一个简单的整数问题2 题目: 给定长度为N的数列A，然后输入M行操作指令，每条指令可能是以下两种之一: 1、“C I r d”，表示把A[l]，A[l+1]，...，A[r]都加上d。 2、“

5

22

4.4 可持久化数据结构

271.最大异或和题目: 给定一个非负整数序列a，初始长度为N。有M个操作，有以下两种操作类型： 1、"A x"：添加操作，表示在序列未尾添加一个数x，序列的长度N增大1。 2、"Q I r x"：

6

8

4.5 平衡树——Treap

273.普通平衡树题目: 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1.插入数值x。 2.删除数值x（若有多个相同的数，应只删除一个)。 3.查询数值x的排名（若

2

4

4.6 AC自动机

275.搜索关键词题目: 给定n个长度不超过50的由小写英文字母组成的单词，以及一篇长为m的文章。请问，有多少个单词在文章中出现了。输入格式第一行包含整数T，表示共有T组测试数据。对于每组数据

2

7

5.1 筛质数、分解质因数和快速幂

278.哥德巴赫猜想题目: 哥德巴赫猜想的内容如下：任意一个大于4的偶数都可以拆成两个奇素数之和。例如： 8=3+5 20=3+17=7+13 42=5+37=11+31=13+29=19+23

1

6

5.2 约数个数与欧拉函数

284.轻拍牛头题目: 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。贝茜让 N 头奶牛（编号1到N）坐成一个圈。除了 1 号与 N 号奶牛外，i 号奶牛与 i - 1 号和 i

1

6

5.3 同余和矩阵乘法

290.同余方程题目: 求关于x的同余方程ax≡1(mod b)的最小正整数解。输入格式输入只有一行，包含两个正整数a, b,用一个空格隔开。输出格式输出只有一行，包含一个正整数x，表示最小

4

9

5.4 矩阵乘法和组合计数（一）

295.佳佳的斐波那契题目: 佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用 S(n) 表示 Fibonacci 前 n 项和 mod

7

5.5 组合计数（二）

299.车的放置题目: 有下面这样的一个网格棋盘，a, b, c, d表示了对应边长度，也就是对应格子数。 [图片] 当a=b=c=d=2时，对应下面这样一个棋盘： [图片]要在这个棋盘上放k个相互

1

6

5.6 组合计数（三）和高斯消元

303.有趣的序列题目: 我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件： 1.它是从1到2n共2n个整数的一个排列{aᵢ}; 2.所有的奇数项满足a₁＜a₃<…＜a₂ₙ₋₁，所

0

2

5.7 容斥原理、概率与数学期望

306.Devu和鲜花题目: Devu有N个盒子，第i个盒子中有Aᵢ枝花。同一个盒子内的花颜色相同，不同盒子内的花颜色不同。 Devu要从这些盒子中选出M枝花组成一束，求共有多少种方案。若两束花

1

4

5.8 博弈论

310.移石子游戏题目: 给定一个有 N 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。对于给定的图和

3

6

6.1 位运算、递推与递归

313.64位整数乘法题目: 求a乘b对p取模的值。输入格式第一行输入整数a，第二行输入整数b，第三行输入整数p。输出格式输出一个整数，表示 a*b mod p 的值。数据范围 1≤a,

4

5

6.2 前缀和、差分、二分

317.激光炸弹题目: 地图上有N个目标点，用整数Xᵢ, Yᵢ表示目标在地图上的位置，每个目标都有一个价值Wᵢ。注意：不同目标可能在同一位置。现在有一种新型的激光炸弹，可以摧毁一个包含R × R

3

14

6.3 排序和RMQ

321.七夕祭题目: 七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是 TYVJ 今年举办了一次线下七夕祭。 Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYV

2

10

没有更多数据了

东方根号八

关注

扫码下载米游社App

了解提瓦特最新资讯

社区地图

了解我们

米哈游官网

相关信息

米游社隐私政策

米游社服务协议

米哈游用户协议

儿童隐私政策

联系我们

地址：上海市徐汇区宜山路1295号1幢10层

电话：400-666-6312（每日08:00 - 23:00）

扫码下载米游社App

了解提瓦特最新资讯

© 2018 米哈游版权所有｜沪公网安备31010402009271号｜沪ICP备2021018283号-1

沪网文（2021）3859-324号 | 增值电信业务经营许可证：沪B2-20220200

互联网违法不良信息举报电话：021-60371750（工作时间：每天10点-20点）｜互联网违法不良信息举报邮箱：tousu@mihoyo.com

亲爱的市民朋友，上海警方反诈劝阻电话“962110”系专门针对避免您财产被骗受损而设，请您一旦收到来电，立即接听。

扫码下载

米游社App