DeNeRATe

分类

题解(55)

/ 注册

全部文章（共52篇）

牛客小白月赛27 E

分析根据多元均值不等式。代码 #include<bits/stdc++.h> using namespace std; int main() { int n;cin >> n; printf("%.3f",pow(n,1.0/3)*...

哲哥

2020-09-12

3 463

牛客小白月赛27 D

分析因为保证在任何时候数字不重复，当一个区间满足时这个区间就是合法的。对于每个询问只需要求出区间就可以了，用线段树维护，时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; const int N = 4e5+100...

哲哥

2020-09-12

3 607

Telephone Lines

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

哲哥

2020-09-12

5 867

牛客小白月赛27 C

分析对于这张图的关键点非常少，对于每一个点对我们可以求出之间的距离，我们考虑状压转移。，表示节点为根节点，已经走过的节点集合为所需要的最小步数。总的复杂度为，表示有多少个坏掉的电线杆。代码 #include<bits/stdc++.h> using names...

哲哥

2020-09-11

3 637

牛客小白月赛27 B

B 乐***对分析考虑，表示以结尾可划分出的最多队伍数。对于不合法的方案只有可能最大的那个人的要求大于了总人数。而对于转移只有两种决策。加入上一组。新开一组。代码 #include<bits/stdc++.h> using namespace std; con...

哲哥

2020-09-11

2 530

牛客小白月赛27 A

A 巨木之森分析先有一个思路，考虑一个点的答案记录。因为除了起始节点之间的路径，其它的路径都要经过两次。所以一个节点的答案为，表示总路径的长度，表示从节点开始的最长路径。现在就只需要考虑快速算出所有的节点的答案，这里我们抛出一个引理:对于树上的每个节点，距离他最远的点一定是树的直径...

哲哥

2020-09-11

2 559

道路和航线

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

哲哥

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