__故人__

分类

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

/ 注册

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

30篇文章 847人学习

22篇文章 1707人学习

全部文章（共169篇）

牛客挑战赛42 D

分析类似这样的式子，其实我们普通的快速幂是没法解决的，所以考虑拓展欧拉定理。而题面上已经保证了，所以可以直接根据的来化简了，我们现在已经把幂降下来了。现在原问题等同于求这个东西。那么我们现在有个初步的想法，令表示，因为这个是在意义下进行的，所以考虑枚举有多少...

2020-09-17

5 561

The XOR-longest Path

分析在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质。所以异或两个相同的值时等同于没有异或。所以，树上的简单路径的异或值其实可以看做。表示节点到根的异或和。因为的值计算了两次，相当于是抵消了。那么题目转化为，在一个序列上找两个节点使他们的异或值最大。显然这个过程需要...

2020-09-16

6 1122

牛客IOI周赛18-提高组 A

分析这个可以暴力求出一个循环内的变换。这样可以考虑置换乘法的结合率，然后把置换拆成循环。这样是可以通过的。但是其实现在等同于只有一个操作重复次，这个其实可以倍增优化，时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; ...

2020-09-16

4 696

牛客IOI周赛18-提高组 C

分析这题是一个经典的组合数学的题。先说题解的证明我是看不会的，以下给出一个较为简便的理解。先说明不下降和不上升子序列没有本质区别，只需要讨论一种即可。简化问题给你一个长度为的序列，要求每个元素，求不下降子序列的方案数。先考虑到对于一个一个集合一定只对应一个序列。那么我们转化一下 ...

2020-09-16

4 637

牛客IOI周赛18-提高组 B

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

2020-09-15

5 541

CF522D

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

2020-09-15

9 861

牛客挑战赛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