又在摸鱼的大熊猫很勤奋努力

分类

题解(38)

/ 注册

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

36篇文章 1215人学习

全部文章（共28篇）

牛客IOI周赛18-提高组 B

分析在比赛中没有做出了，对矩阵的掌握还是太菜了。先对与原问题考虑。我们发现这个问题其实并不好考虑，其中涉及的状态太多，但是考虑一下用全部方案减去不合法的方案来计算。。先看前面的。这里有两种理解。考虑在每个点后面是否划分那么总的方案数为。也可以用插板法来理解，那么我们总的方案数为 ...

XZC

2020-09-15

5 541

CF522D

分析考虑只有一个区间有一对相同的值时才有答案。所以我们可以把所以点对存下来，这样是。考虑如果有多个相同的话，其实只需要储存相邻的两个即可，这样就只有级别的点对了。再考虑如果有一个大区间包含了一个小区间证明，如何任何时候大区间不可能是最优解，最后做一次区间最小值就好了。代码 #includ...

XZC

2020-09-15

9 861

牛客挑战赛42 C

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

XZC

2020-09-15

5 596

牛客挑战赛42 B

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

XZC

2020-09-15

3 585

牛客挑战赛42 A

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

XZC

2020-09-15

4 487

牛客练习赛69 F

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

XZC

2020-09-14

5 630

CF460C

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

XZC

2020-09-14

5 538

牛客练习赛69 E

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

XZC

2020-09-13

7 993

牛客练习赛69 D

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

XZC

2020-09-13

6 682

牛客练习赛69 C

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

XZC

2020-09-13

6 615