__故人__

题解

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

/ 注册

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

牛客挑战赛42 C

分析这题太糟糕了，对空间的要求简直变态。上面是题外话。考虑如何求出我的兄弟们，因为兄弟和我是在同一个子树中的，所以在一个相同深度的查询，那么这个一定是一个区间。那么现在就是求一个区间的静态第小问题。这个可以主席树维护一下。现在的做法，对每个深度开一个主席树，然后二分出来我们要查询的区间。时间复...

2020-09-15

5 596

牛客挑战赛42 B

分析这不是的模板题。先对于每个节点的值分解为所有因数。然后处理一个节点时，先处理轻儿子，取消其贡献。再处理重儿子保留贡献。最后暴力加上轻子树。因为一个点到根节点只有条轻路径，所以子树也只会被暴力加次。总的时间复杂度为。代码 #include<bits/stdc++.h>...

2020-09-15

3 585

牛客挑战赛42 A

分析对于整个数列，因为每一个数只能被一个区间覆盖，所以考虑求出每个数的延伸范围。复杂度。代码 #include<bits/stdc++.h> using namespace std; const int N = 2e6 + 100; int read() {int x;scanf...

2020-09-15

4 487

牛客练习赛69 F

分析首先得明白。那么我们原式子化为。卷上一个之后。。这里再卷上一个之后，令左侧等同于，所以。这个根据积性函数线性筛就好了。要注意，可以先把一起筛出来。一些符号的使用代码 #include<bits/stdc++.h> using nam...

2020-09-14

5 630

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