分析 我们先考虑如何求答案，我们发现其实答案等于 ， 表示集合的个数，就就是连通块的个数，那么这个我们可以通过简单的并查集来维护。现在我们按照思路打一下，嗯。 获得了 96分的好成绩 。考虑我们的复杂度为什么如此高。其实是因为所有边都被我们枚举了一次，但是其中其实有许多无用的边。我们尝试给边定向。如果学习过三元环的朋友，那么后面就好理解了。我们求出每个点的度数，那么当一个点的度数小于 。那么边就由小的指向大的。如果两个都大于 那么就链接双向边。我们考虑为什么是对的。 当一个点的度数 那么总边数为 。 当一个点的度数 那么我们可以证明这样的点一定不超过 个。所以总的边数为 ...

分析 我们可以分类讨论。 首先如果 这显然不需要进行操作。 如果 , 我们可以进行一次操作将两个配对，可以证明这个操作是最优的。 ， ， 同理我们可以两次操作配对。 那么最后剩下的就是四个一组的。根据鸽巢原理我们一定可以在 次操作之内配对。 那么我们现在只需要记录这四种情况有多少个，然后由前到后考虑就可以了，总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 1000; char A[N],B[N]; int get(char ch) {if(ch=='A')re...

分析 题目要求我们求出至少 个数全部 之后的最大值。我们考虑到 。所以我们其实求出恰好 个就好了。对于第 位要为一，那么这 个数这一位也必须全部为 。如果可以在这一位找到 个数，那么，保留除了这一位为 的，然后继续考虑下一位。否则直接考虑下一位。这样的答案是不劣的，那么总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; vector<int> A,B; int n,k; int main() { scanf("%d%d",&n,&k); for(int i ...

图片来源与 引入 这个是一个比较偏门的算法，但是并不排除考察的可能性。其中的思路比较灵活，这里介绍一下，希望起到抛砖引玉的效果。 图的绝对中心 概念，图的绝对中心可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小。 那么我们首先的关键点就是求出图的绝对中心，我们可以分类讨论，因为我们可以知道图的绝对中心一定到至少两个最远点的距离相同。 那么 当绝对中心在点上时。 当绝对中心在边上时，我们可以通过移动绝对中心的位置 可以按照 做出如下图像。那么我们可以枚举每个交点。那么我们可以发现，由于斜率相同。所以我们可以先按 排序，找到第一个 而且 。那么它们的折线...

分析 要求多少种串，要求规定的串不能出现。这个我们先对所有不能到的串建一个 自动机。那么我们可以根据 指针指向最长后缀这个性质来更新，是否能出现这个串的标记。令 表示 节点表示的串能否出现，那么转移方式，简单的来说就是 。那么我们定义 为 结尾的串的方案数。那么我们的转移为 而且 都没有 标记。那么这个朴素的转移为 由于 很大， 又很小。所以我们考虑矩阵优化转移，那么总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 100,mod = 1e9 + 7;...

分析 读完题分析一下发现是要我们求 。我们可以发现 最多也只有 种取值，而且取值连续。那么我们考虑数论分块。至于数论分块的证明我这里放个网址 这个 有非常优秀的证明，便不加赘述。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL a,b,ans; int main() { cin >> a >> b;a--; for(LL l = 1,r = 1;l <= b;l = r + 1) r=b/(b/l),ans += (r-l+1)*(b/...

分析 要求我们在一条直线上确定一个点。要求它覆盖的点最多。我们可以转换一下，对于每个点我们可以覆盖到它的地方有哪些。如此我们发现这些地方，一定在直线上构成一个线段，或者没有交点。那么我们就可以求出这个范围，然后通过差分就可以求出最多被覆盖的区间。这个我们可以通过勾股定理来求。但是我们最后得到的是一个数值。而有可能在直线的后方相交。为了得到有向距离，我们还要用叉积来判断正负。 要注意因为不能漏掉恰好重合的端点，所以我们要把差分的正负反一下。 用的的公式 和 ，结合代码食用更佳。代码 #include<bits/stdc++.h> using namespace std; #de...

分析 给你一棵树，求至少要几次操作，变化为一条链。我们知道无论变化多少次总度数一定不变 。而一条链的度数分布为 根据鸽巢原理，只要对于 的节点操作 次就可以了。总的复杂度为 。 代码 #include<bits/stdc++.h> const int N = 3e5 + 1000; int du[N],n,ans; int main() { scanf("%d",&n);for(int i = 1,a,b;i < n;i++) scanf("%d%d",&a,&b),du[a]++,du[b]++; for(int i = 1...