微澜尛雨

题解

/ 注册

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

【蓝桥杯校选2】来自专栏

【T1】出租签到题，没什么考点，第二个数组找第一个数组的下标就好 #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue&...

C++ 深度优先搜索双指针二分查找 dfs 分治 DP

2021-12-07

7 589

题解 | #统计数字# 来自专栏

（截止2020-9-3题目有说是多组输入吗？？？？）题目考点：数位DP（小学奥数分情况讨论？）题目大意：统计0 ~ n中的所有数字中，0到9在每个数字的每一位上出现的次数。题目分析： 1、举例分析：统计数字2在（0 ~ n=324）的个位上出现的次数，个位有（32 * 1+1）次，在十位...

dp 数位dp

2021-09-03

6 658

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

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

dp 01背包

2021-05-14

1 674

题解 | #[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

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

题目考点：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