__故人__

题解

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20)

/ 注册

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

Telephone Lines

分析因为有条可以免费，所以我们朴素的最短路算法不太好做。现在题解中有了二分最短路的题解。这里换一种思路。分层图。每一层和原图是相同的，层与层之间由边权为的边链接。最后一层的终点的权值就是我们要求的最小值。代码 #include<bits/stdc++.h> using nam...

2020-09-12

5 867

道路和航线

分析读完题，我们发现这道题就是让你求出在一张混合图中的单源最短路。因为有负环，直接考虑算法。因为题面上已经保证是没有负环的，所以一定有解。考虑到朴素的算法容易被卡，这里使用。将原队列改成双端队列，对要加入队列的点，如果小于队头元素的，将其插入到队头，否则插入到队尾。代...

2020-09-10

4 769

网格图

分析对于一个节点从恰好走步走到之类的都可以用来处理。定义代表第步，到节点，当前方向是的总方案数。那么一个节点可以从个方向转移过来，再枚举自己的方向。时间复杂度为。还有第一维可以用滚动数组优化空间。代码 #include<bits/stdc++.h&g...

2020-09-09

5 1156

Working out

分析一个节点到左上，右上，左下，右下的最大值路径是确定的。那么我们考虑见面的点是哪个点。因为见面点是不能计算贡献的，所以我们考虑第一个人和第二个人是分别从哪个方向来的。经过讨论也只有两种可能。枚举每一个点算出值就可以了。时间复杂度为。代码 #include<bits/stdc++.h&...

2020-09-08

3 650

摆渡车

题意安排摆渡车出发的时间，使这些同学的等车时间之和最小。分析一根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么 $$f_i = \min_{j\le i-m} \lbrace f_j+\sum_...

2020-09-07

7 760

牛客IOI周赛18-普及组

分析数据范围很小，可以考虑快排，再通过去重函数一下直接求解。时间复杂度为。也可以开四个变量扫一次得出答案。代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 10...

2020-09-04

5 715