微澜尛雨

题解

/ 注册

全部文章 / 题解（共32篇）

题解 | #[CQOI2010]扑克牌# 来自专栏

题目考点：二分 + 验证答案题目内容：给n种牌和一种Joker牌，问能合成几套牌，其中每一套牌要包含n种不同的牌（其中给定的n种牌中若有一种不够用，可以用Joker代替，Joker也只能在一套牌里出现一次）。题目分析：二分答案，例如题目样例： 3 4 1 2 3 //即第一种牌1张，第二种2张...

2021-05-16

1 576

题解 | #CSL分苹果# 来自专栏

题目考点：dp -- 01背包（无脑dfs肯定T ，后面附上60分dfs吧）题目大意：将a数组中的数分成两组，使得两组中的数的和尽量接近，输出两组数的和（若无法平均，优先输出较小的数）题目分析：01背包问题，若a数组中的数总和为sum ，可以假想一个体积为sum / 2的背包，将其尽量装满即可...

dp 01背包

2021-05-14

1 674

题解 | #Let's Play Curling# 来自专栏

题目考点：离散化（其实怎么写都行，以个人目前能力感觉离散化+前缀和比较好上手）题目大意：一条线上红蓝两种石头随机排列，易知存在若干点使得这些点前后均为红色石头，且绝对不含蓝色石头，找到这些点中的前后红色石头数量最多的那个点，输出最大数量题目分析：如图，我们可以确定a[4]和a[5]之间的点，前后...

离散化前缀和

2021-05-13

8 828

题解 | #字符串# 来自专栏

题目考点：尺取法（双指针）题目大意：给定一个字符串，问集齐26个字母所需要的最短区间是多长。题目分析：右指针字符串，当26个字母集齐之后移动左边界，维护最短长度即可；代码： #include<iostream> #include<algorithm> #include<...

尺取

2021-05-10

5 710

题解 | #[CQOI2007]涂色PAINT# 来自专栏

题目考点：区间dp 题目大意：将一个空白模板涂成目标颜色的模板，一次涂色的长度任意，求最少涂色次数，参考题目样例：例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。题目分析：用dp[ i ] [ j ] 表示从i涂到j所需要的最少涂色次数，则有以下两种情况...

dp 区间dp

2021-05-09

4 958

题解 | #方格取数# 来自专栏

错误思路：dp+贪心 86%测试点（题解里也有大佬用这种写法wa了，对我自己来说就是初学dp总是想贪）因此谨记：求解全局最优不要用局部最优思路！！！！！！！！！！！正确思路：四维dp 题目大意：n*n的地图上分布数字，从左上角走到右下角，走两趟，第一趟走过的地方变成0，求两次走完取到的总数...

dp

2021-05-08

2 659

题解 | #八数码# 来自专栏

题目考点：STL、 bfs题目大意：可以看成x上下左右移动最终复原八数码。题目分析：普通的bfs，不过是用map<string, int>储存状态（这里用的unorderedmap，比较快）（由于用字符串储存，速度会慢很多，建议改用map<int, int>储存，这里就偷懒了...

bfs

2021-05-08

5 579

题解 | #「木」迷雾森林# 来自专栏

题目考点：dp 题目大意：左下到右上的走法数量，遇到1不走，走到该位置无效（注意快读和取模）题目分析：过河卒的改版，不过是走的方向变了，思路还是一样的：走到该点的路径条数为左边点条数+下边点的路径条数，状态转移方程：mp[i][j] = mp[i+1][j] + mp[i][j-1] 特判...

dp

2021-05-07

2 922

题解 | #过河卒# 来自专栏

注意开long long !!!题目考点：dp题目大意：从起点到终点的路径数（多啰嗦一句，分析是dp还是bfs的点就是看求的是最短路径还是路径条数，两种算法解决的问题不同）题目分析：dp[ i ] [ j ] 表示走到（i,j）的路径数，正常情况下dp[i][j]等于上面走下来和左边走过来的路径条数...

dp

2021-05-07

1 598

题解 | #maze# 来自专栏

题目考点：bfs + 优先队列题目概述：每张地图有起点、终点、陷阱、传送门，求最短时间。注意情况有以下几种：起点有陷阱、传送门终点有陷阱、坐传送门还不如走过去时间短等。前两种问题用数组标记即可；第三种情况用优先队列维护，保证不管是坐传送门还是不开启传送门，到达该点的时间是划算的 #include&l...

bfs 优先队列

2021-05-07

1 599