__故人__

分类

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

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 847人学习

22篇文章 1707人学习

全部文章（共169篇）

CF460C

分析经典的字眼，要求最小值最大。考虑二分答案。如何判断合法性。对于二分出来的最小值。从左向右扫一次，在考虑时，我们已经保证是一个合法的区间了，所以只有向后加才有意义。所以遇到小于二分出来的数时，直接这个区间。用差分数组维护一下就好了，当操作次数大于时是不合法答案，时间复杂度为 ...

2020-09-14

5 538

牛客练习赛69 E

分析对于每个端点维护四个单调栈。表示这个端点作为最小值，最大值可以满足的合法区间。那么只有在的合法区间内，在的合法区间内，这个用扫描线维护一下就好了，要记住先加后减，否则会丢掉重合的方案。一些理解是我这个点可以延展的范围。如果我都不能到，那么我肯定不能作为端点出现。所以...

2020-09-13

7 993

牛客练习赛69 D

分析考虑如果一个数有选择，那么可能会影响它的也必须选择。所以这个就是个计数了。可以写个类似背包的转移来算出所有的可能方案，最后答案再除以所有方案数就好了。时间复杂度为。当然你可以滚动数组优化空间。一些细节表示可以选个人时的合法方案数，由于从转移过来的，所以可以滚动数组优化。...

2020-09-13

6 682

牛客练习赛69 C

分析考虑一个最大生成树，变化为序列之后一定有一种方案满足。所以这道题只需要求一个最大生成树即可。代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 5e5+1000...

2020-09-13

6 615

牛客练习赛69 B

分析对于一个确定的，答案一定是可以取到前个最大的值，所以只需要排序，再维护一个前缀和。最后时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 1...

2020-09-13

7 541

牛客练习赛69 A

分析按题意模拟即可，要注意四舍五入，所以全部，最后再除回来就可以了。代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL T,a; int main() { cin >>...

2020-09-13

5 606

Codeforces Round #670 (Div. 2) 题解

A 分析分出两个集合要求。考虑直接贪心选到不能再选，因为每个数的对答案的贡献都是，不错的签到题。代码 #include<bits/stdc++.h> using namespace std; const int N = 4e5+100,inf = 0x3f3f3f3f; in...

2020-09-13

3 562

牛客小白月赛27 J

分析对于这个其实是等价于的。所以只需要判断是否为偶数。代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6+100; char ch[N]; int n,sum; int main() { ...

2020-09-12

3 465

牛客小白月赛27 I

分析考虑答案的单调性，我们先钦定一个值为最小值或最大值。那么如果是一个满足的区间，那么也一定是一个合法区间。对于每一个数都求出它的分界点。那么。这个直接上单调队列。时间复杂度为。代码 #include<bits/stdc++.h> using namespace st...

2020-09-12

3 562

牛客小白月赛27 H

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

2020-09-12

3 521