在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #购物#

动态规划问题，一开始看到每天要买的糖果数还不一样，而且每个糖果还有他自己不同的价格。直接就想到了状压DP。但本题要求花费最小，而对于某一天买k个糖果来说花费最小其实就是从价格低的糖果来买就行了。那么某一天如何选糖果的问题就这样简答的解决了。那么状态数组为：dp[i][j]。i代表天数...

C++ 动态规划

2023-11-16

1 191

题解 | #逛公园#

本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。那么就可以知道之间可以使用动态规划去求解。但本题有要求路径长度不能超过n+...

C++ 动态规划迪杰斯特拉算法图论最短路径

2023-11-16

1 217

题解 | #[SCOI2012]滑雪与时间胶囊#

本题中a180285的时间胶囊操作其实相当于随意的去走一个树形的结构。那么很容易就想到了最小生成树算法。但是由于本题中必须从高度高的向高度低的去走。而且图是一个有向图，所以在这里克鲁斯卡尔算法不适用，因为克鲁斯卡尔算法的加边方式不会去在乎单向边的问题。那么使用prime算法，但是优先...

C++ 图论最小生成树克鲁斯卡尔算法

2023-11-12

0 239

题解 | #Forsaken喜欢独一无二的树#

由克鲁斯卡尔算法可以知道，将边排序后一股脑的加入到最小生成树里面，只要没有回路就是最小的生成树。那么排序过后可能会有一些边是长度相同的，这些边有可能不适用于当前的生成树，但正因为这些长度相同边的存在才导致最小生成树不唯一。那么将这些无法加进最小生成树，但长度相同的边删除就是结果。 ...

C++ 图论最小生成树克鲁斯卡尔算法

2023-11-12

1 143

题解 | #道路建设#

//最小生成树模板题，用普利姆算法或克鲁斯卡尔算法求解。 #include <bits/stdc++.h> using namespace std; #define int long long const int&nb...

C++ 图论最小生成树普利姆算法克鲁斯卡尔算法

2023-11-11

2 170

题解 | #[HAOI2012]ROAD#

通过建立糖果数变多的有向图来由拥有糖果数最少的那个人下手去计算出每个小朋友的最小糖果数。那么在这里增加一个0点当做起点，然后可以从起点出发求出每个点的最小糖果数。由于在这里我们差分的值就是最小值，所以我们要求尽量满足差分条件。那么我们在寻找的时候就要去寻找最大值。这样可以让每一条边的条件都...

C++ 差分约束图论 SPFA算法

2023-11-11

1 192

题解 | #Ranking the Cows#

//本题首先的困难在于要明白如果想知道一个序列的排序序列再不考虑传递影响的情况下需要有n(n-1)/2个大小关系。 //本题给出的大小关系里面有受传递影响可以推导出的一些大小关系，比如：2>1,1>4得到2>4; //那么将其扩展到n(n-1)/2里面的所有关系，也就是说需要求出间...

C++ 图论二进制优化

2023-11-09

1 207

题解 | #传送门#

这题还是再考最短路算法，在这里还是迪杰斯特拉。但难点在于建图，在这里将同一种种类的传送门具化成一个点，拥有这个传送门的可以通过这个传送门进行到达。但在花费上是二倍。还有就是不要使用map<pair<int,int>,int>来保存边。这个数据类型操作会导致这道...

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

2023-11-08

0 270

题解 | #分层图最短路#

直接建图利用最短路算法去搞。这里首先说一下最短路的几种算法以及各自的用途：迪杰斯特拉算法：求单源最短路的算法，要求图中不能有负边，否则就破坏了这个算法的贪心策略。 SPFA：也是求单源最短路的算法，这个算法在图中有负边的时候可以用，一般如果图中没有负边不用，毕竟是将图中所有点都...

C++ 图迪杰斯特拉算法

2023-11-07

1 221

题解 | #胖胖的牛牛#

因为正在练习图论，所以建图来做吧。可以假设某个各种的上下左右方向都有一个点，那么这些点的道路里面方向改变的，也就是某个格子上下左右相邻直接的道路的长度是1，其余是0。那么就可以转化成起点的四个方向点到终点的四个方向点的求解。那么直接套Dijkstra算法即可。就是建图有那么亿...

C++ 深度优先搜索图论迪杰斯特拉算法

2023-11-06

1 156