分析 令 为以 结尾的最小代价。 ，后面的可以前缀和优化一下。 。令 为 的决策点，那么可以化简为 。那么这个就是个一次函数。其中 ，所以为了让 最小，那么我们显然要让 最小。那么现在就是要求 的最小值，放在坐标轴上，就是求直线 与所有一次函数的最小值，这个可以李超线段树来求，这样单次查询的复杂度为 。因为查询的直线有时间顺序，所以要可持久化一下，每次查询的就是一个前缀树，其实如果不是强制在线，这道题其实还可以 分治。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long...

分析 每条边的边权为 ，由于输入的图是一颗树，那么 之间有且仅有一条简单路径，所以合法的点对 中间只会有一个点。所以考虑枚举中间的节点。令 表示节点 为中间节点的权值之和，那么 。因为 ，所以可以先考虑有序点对的值最后再 就好了。所以 ， 表示在 为中间点， 为当前考虑点，已经计算过的权值之和。由于总的枚举数等于度数 ，所以时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 200010,p = 10007; LL read...

分析 类似 这样的式子，其实我们普通的快速幂是没法解决的，所以考虑拓展欧拉定理。 而题面上已经保证 了，所以可以直接根据 的来化简了 ，我们现在已经把幂降下来了。现在原问题等同于求这个东西 。那么我们现在有个初步的想法，令 表示 ，因为这个是在 意义下进行的，所以考虑枚举 有多少个数。那么总的方案数就可以写作，那么 ，这个显然是个多项式的卷积形式。所以考虑用快速数论变化优化一下，时间复杂度为 。也可以用生成函数来理解。 表示值为 可以出现的次数。那么令 的普通生成函数 ，同理可以求得 。那么最后 。有什么细节和代码上的不懂，欢迎私聊啊。 代码 #include...

分析 在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质 。所以异或两个相同的值时等同于没有异或。所以，树上的简单路径的异或值其实可以看做 。 表示节点 到根的异或和。因为 的值计算了两次，相当于是抵消了。那么题目转化为，在一个序列上找两个节点使他们的异或值最大。显然这个过程需要优化。我们可以考虑 。我们按位由大到小建树。这一类的 有个非常好的性质。在父亲节点就可以知道数的大小关系。这个性质还是比较显然，因为我们是按位由高到低考虑的，那么这一位是 的数，一定大于这一位是 的数。有了这样优美的性质， 就可以维护一些关于值域的题了。所以直接贪心作就好了。时间复杂度为 ...

分析 这个可以暴力求出一个循环内的变换。这样可以考虑置换乘法的结合率，然后把置换拆成循环。这样是可以通过的。但是其实现在等同于只有一个操作重复 次，这个其实可以倍增优化，时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 ...

分析 这题是一个经典的组合数学的题。先说题解的证明我是看不会的，以下给出一个较为简便的理解。先说明不下降和不上升子序列没有本质区别，只需要讨论一种即可。 简化问题 给你一个长度为 的序列，要求每个元素 ，求不下降子序列的方案数。先考虑到对于一个一个集合 一定只对应一个序列。那么我们转化一下 表示 这个数在集合中出现的次数，那么 就可以表示一个序列，其中 。现在就是求问这个集合有多少种方案。这个可以考虑插板法，现在等同于给你 一个长度为 元素全为的 的序列，两个板之间的 的个数就是 的大小。因为左右两个端点必须有个板的。所以 。可以看作 个位置中要挑出 个 的方案数。...

分析 在比赛中没有做出了，对矩阵的掌握还是太菜了。先对与原问题考虑。我们发现这个问题其实并不好考虑，其中涉及的状态太多，但是考虑一下用全部方案减去不合法的方案来计算。 。先看前面的 。这里有两种理解。 考虑在每个点后面是否划分那么总的方案数为 。 也可以用插板法来理解，那么我们总的方案数为 。 那么现在问题就是如何求出 。先考虑一个朴素的 ，令 凑成 时的不合法数量。那么 。因为 ，所以一个数的影响不会超过 。这个给我们矩阵优化的基础。那么用矩阵求出 ，复杂度为 ，代码的细节如有不理解的可以私聊啊 。 代码 #include<bits/stdc++.h&g...

分析 考虑只有一个区间有一对相同的值时才有答案。所以我们可以把所以点对存下来，这样是 。考虑如果有多个相同的话，其实只需要储存相邻的两个即可，这样就只有 级别的点对了。再考虑如果有一个大区间包含了一个小区间证明，如何任何时候大区间不可能是最优解，最后做一次区间最小值就好了。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = get...

分析 这题太糟糕了，对空间的要求简直变态。上面是题外话。考虑如何求出我的兄弟们，因为兄弟和我是在同一个子树中的，所以在一个相同深度的查询，那么这个一定是一个区间。那么现在就是求一个区间的静态第 小问题。这个可以主席树维护一下。现在的做法，对每个深度开一个主席树，然后二分出来我们要查询的区间。时间复杂度为 。 代码 #include<bits/stdc++.h> #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; int read() { ...

分析 这不是 的模板题。先对于每个节点的值分解为所有因数。然后处理一个节点时，先处理轻儿子，取消其贡献。再处理重儿子保留贡献。最后暴力加上轻子树。因为一个点到根节点只有 条轻路径，所以子树也只会被暴力加 次。总的时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(is...

分析 对于整个数列，因为每一个数只能被一个区间覆盖，所以考虑求出每个数的延伸范围。复杂度 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 2e6 + 100; int read() {int x;scanf("%d",&x);return x;} int L[N],R[N],n,a[N],Ans,Max; int main() { n = read(); for(int i = 1;i <= n;i++) { a[i] = read();L[i] = R[...