DeNeRATe

分类

题解(55)

/ 注册

全部文章（共11篇）

Step to One 来自专栏

CF1139D Step to One 题目描述你手中有集合，然后每一次操作你都会从数集中等概率抽取一个数放到新的序列中，直到新的序列的的值为。求你的期望操作次数分析这道题十分的精妙，它集合了数学期望还有莫比乌斯反演，十分考验的基础能力数学期望首先知道，表示对于事件的数...

孟轲孟轲

2020-10-15

5 858

物流运输来自专栏

ZJOI2006 题目大意就是说，你需要跑次最短路，然后对于某些时间，有些点是无法到达的然后如果你跑路的路径发生了改变的话，那么对于每次改变都会有的花费分析那么显然贪心是错误的，考虑动态规划设表示跑到第天的最小花费，那么最后的答案显然是那么现在考虑转移：就是说从第天开始一直到...

孟轲

2020-10-14

3 765

[CQOI2017]小Q的表格来自专栏

[CQOI2017]小Q的表格题目描述给定一个表格，满足：有次操作每次操作修改的值，为了使整个表满足条件，所以要修改的点还挺多的然后让你输出的范围内的数的和 Solution 对于性质，观察发现它可以转化一下：对于转化到不太理解的同学，可以看看这个结论这里就不细说了所以可...

孟轲

2020-09-21

5 781

Closest Equals 来自专栏

Closest Equals 题目大意: 给你一串数,有次询问,每次求问一个区间,问在区间内最近的两个相同的数的距离是多少分析: 第一反应就是记录一下这个值上一次出现的位置,这就可以记录一次答案了然后可以构造出一个新的序列,因为当某两个可行的数在另外两个可行的数内时,外面的数是没有贡献的然后就...

孟轲

2020-09-15

5 910

Present 来自专栏

Present 题目大意: 先给你一串序列,你至多有次操作使得一段长度为的区间加一问这串序列的最小值最大可以是多少? 分析: 最小值最大或者最大值最小,我们的第一反应可能都是二分答案简单证明一下: 如果最小值最大为,那么只要我们少做一次操作,那么也是可行的这满足二分答案的性质,所以呢二分答案没...

孟轲

2020-09-14

3 629

Telephone Line S 来自专栏

Telephone Line S 题目大意: 首先你有一张图，问你从到的路径中第条最大的边最小有多大分析：这个题很显然是可以二分答案的但是我们考虑换一种做法：分层图那么就是跨层的时候让其代价为，那么一共就有层图在跑一个类似最短路的东西就可以了 #include <bits/stdc++.h...

孟轲

2020-09-12

4 704

牛客小白月赛27 H

分析由于没有修改操作，所以可以求出二维前缀和，从而达到判断。二分边长，对每个节点单独考虑就好了，总的时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; const int N = 5e2+100; int n,m,K;...

孟轲

2020-09-12

3 521

道路和航线来自专栏

道路和航线本质就是一个最短路，有负边，题目保证无环直接跑的正确性就不用证明了这道题卡掉了朴素的，用双端队列优化即可？ Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const i...

孟轲

2020-09-10

5 709

Working Out 来自专栏

Working Out 题目大意: 给定一个矩阵，每个点都有一个点权，让你求从矩阵中某一点到矩阵四个顶点的权值之和减去自己的四倍的值最大(就是这个点没有贡献) 分析：我们画两张图，看看他们的路径，就会发现其实只有两种情况一:二：就是说其实只有两种转移的方式那么我们用4个数组分别记录到四个顶点的最大...

孟轲

2020-09-08

4 751

摆渡车来自专栏

摆渡车题意你可以操控一辆车的发车时间，你也知道跑一次往返的时间，你还知道每一个人到达车站的时间让你找到一种方案使得所有人的等待时间之和最少，求这个最小时间分析第一反应是把到达车站的人作为一个整体然后我们可以枚举最近的一次发车时间假设现在的时间是，最近的一次发车时间是那么从的等待时间可以表示为...

孟轲

2020-09-07

4 791