在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

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

题解 | #挖沟#

最小生成树模板题。 prim算法： #include <bits/stdc++.h> using namespace std; const int maxn = 2*500000+10; const ...

C++ 图论普利姆算法克鲁斯卡尔算法

2023-11-06

2 348

题解 | #Rinne Loves Graph#

//迪杰斯特拉算法配合上动态规划 //动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路 //一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。 #include <bits/stdc++.h> using&...

C++ 图论动态规划迪杰斯特拉算法

2023-11-02

1 369

题解 | #公交线路#

本题属于Dijkstra算法的模板题。只需要之前迪杰斯特拉算法求出起点s到每个点的最短距离。然后输出s到t的最短距离即可。这里简要说一下迪杰斯特拉算法的原理：迪杰斯特拉算法使用一个贪心的思想，在每一次的路径里面最短的那一个一定是确定的，也就是说不会被其他的路径影响从而边的更短。那么我...

C++ 图论 Dijkstra 迪杰斯特拉算法最短路径算法

2023-11-01

0 399

题解 | #任务安排#

//关键路径的模板题，首先按照拓扑排序的顺序去计算每个点最早的开始时间，在拓扑排序的过程中将节点保存进栈里面 //然后从栈里面挨个的取出，每取出一个去找他的出度边，去计算最晚开始时间。 //最后遍历一遍所有的点，如果最早开始时间和最晚开始时间相等那么就是关键事件。 #include <...

C++ 拓扑排序图论

2023-11-01

1 412

题解 | #[HNOI2015]菜肴制作#

//反向建边，在正常的拓扑排序里面我们只能按照起始的点去寻找最大或最小的字符序列， //但是在题目当中要求尽量先吃到质量高的菜肴，那么这就关系到终点了。 //所以我们可以采用反向建边的方式，去求一个字符序列最大的，这样就实现了尽量先吃到质量高的菜肴。 #include <bits/s...

C++ 拓扑排序图论

2023-11-01

1 393

题解 | #神经网络#

本题的需要将某个节点的所有入度计算完才算是完成，那么自然想到使用拓扑排序的做法，使用队列去保存遍历。然后在拓扑排序的过程中按照要求做一些改变就行。在这里保存图使用的是链式前向星。说一说我遇到的三个坑的：本题的题意多少有点隐含了。 1、在神经兴奋传递之后这个神经就会失去兴...

C++ 拓扑排序

2023-10-31

1 265

题解 | #[NOIP2003]加分二叉树#

二叉树？？树状dp？？NONONO！！！本题的树不固定，他要求去找出来一个最优的树，所以不适合使用树状dp去进行求解。但又因为题中所给的有中序遍历的序列，中序遍历序列最大的特点在于定根可将区间分成左右子树。那么分成两部分之后就可以分别去计算这两部分，也就是在这两小部分里面取找根。那...

C++ 动态规划区间dp

2023-10-29

1 383

题解 | #树学#

在树上进行操作的记忆化搜索，通过DFS加灵活换根的方式进行。首先先走一遍DFS，得到每个节点下的深度和，节点的个数和（包括节点自身）。然后让1成为根，那么再进行DFS下去的每一个节点都可以有一个动态规划递推式来快速计算得到加入某个节点为根的时候的深度和。递推式为：dp[x] ...

C++ 动态规划记忆化搜索

2023-10-29

1 300

题解 | #打砖块(brike)#

很折磨的一道题除了要进行转换以外，还要十分注意每层循环的范围。解释不了一点，直接挂一个我觉得写的比较好的博客吧。 (*´∇｀*) 欢迎回来！ (cnblogs.com) //首先矩阵旋转90度，去除后效性。 //f[i][j][k]表示截止到第i行，总共已经选j个砖块，...

C++ 动态规划变形动态规划

2023-10-29

1 493

题解 | #[SCOI2009]粉刷匠#

//分组背包问题，首先考虑一个木板的情况： //对于一个木板而言：dp[i][j]，i表示当前是第i次粉刷，粉刷第j块格子的情况。 //那么得到状态转移方程为：dp[i][j] = max(dp[i-1][l]+num[l+1][j])。 //其中num[l+1][j]表示在l到...

C++ 动态规划分组背包

2023-10-28

1 397