__故人__

分类

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

/ 注册

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

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

2020牛客国庆集训派对day1 I 来自专栏

分析我们先考虑如何求答案，我们发现其实答案等于，表示集合的个数，就就是连通块的个数，那么这个我们可以通过简单的并查集来维护。现在我们按照思路打一下，嗯。获得了 96分的好成绩。考虑我们的复杂度为什么如此高。其实是因为所有边都被我们枚举了一次，但是其中其实有许多无用的边。我们尝试给边定向...

2020-10-07

6 618

2020牛客国庆集训派对day1 H 来自专栏

分析我们可以分类讨论。首先如果这显然不需要进行操作。如果 , 我们可以进行一次操作将两个配对，可以证明这个操作是最优的。，，同理我们可以两次操作配对。那么最后剩下的就是四个一组的。根据鸽巢原理我们一定可以在次操作之内配对。那么我们现在只需要记录这四种情况有多少个，...

2020-10-07

7 610

2020牛客国庆集训派对day1 F 来自专栏

分析题目要求我们求出至少个数全部之后的最大值。我们考虑到。所以我们其实求出恰好个就好了。对于第位要为一，那么这个数这一位也必须全部为。如果可以在这一位找到个数，那么，保留除了这一位为的，然后继续考虑下一位。否则直接考虑下一位。这样的答案是不劣的，那么总的复杂度为...

2020-10-07

6 651

最小直径生成树

图片来源与引入这个是一个比较偏门的算法，但是并不排除考察的可能性。其中的思路比较灵活，这里介绍一下，希望起到抛砖引玉的效果。图的绝对中心概念，图的绝对中心可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小。那么我们首先的关键点就是求出图的绝对中心，我们可以分类讨论，...

2020-10-06

4 990

2020牛客国庆集训派对day1 G 来自专栏

分析要求多少种串，要求规定的串不能出现。这个我们先对所有不能到的串建一个自动机。那么我们可以根据指针指向最长后缀这个性质来更新，是否能出现这个串的标记。令表示节点表示的串能否出现，那么转移方式，简单的来说就是。那么我们定义为结尾的串的方案数。那么我们的转移为而且 ...

2020-10-05

5 577

2020牛客国庆集训派对day1 E 来自专栏

分析读完题分析一下发现是要我们求。我们可以发现最多也只有种取值，而且取值连续。那么我们考虑数论分块。至于数论分块的证明我这里放个网址这个有非常优秀的证明，便不加赘述。代码 #include<bits/stdc++.h> using namespace std; #de...

2020-10-05

6 623

2020牛客国庆集训派对day1 D 来自专栏

分析要求我们在一条直线上确定一个点。要求它覆盖的点最多。我们可以转换一下，对于每个点我们可以覆盖到它的地方有哪些。如此我们发现这些地方，一定在直线上构成一个线段，或者没有交点。那么我们就可以求出这个范围，然后通过差分就可以求出最多被覆盖的区间。这个我们可以通过勾股定理来求。但是我们最后得到的是一个...

2020-10-05

6 795

2020牛客国庆集训派对day1 C 来自专栏

分析给你一棵树，求至少要几次操作，变化为一条链。我们知道无论变化多少次总度数一定不变。而一条链的度数分布为根据鸽巢原理，只要对于的节点操作次就可以了。总的复杂度为。代码 #include<bits/stdc++.h> const int N = 3e5 + 100...

2020-10-03

6 574

2020牛客国庆集训派对day1 B 来自专栏

分析我们换一个题面，其实是要我们求。那么我们发现这个的出现太突兀了，考虑用枚举这个。那么我们枚举之后，就暴力枚举这个区间就可以了。为什么呢？我们可以证明只会有种取值。那么我们完全可以再枚举一个，又因为的大小是具有单调性的，所以二分枚举边界就可以了。关键是的枚举，...

2020-10-03

7 0

2020牛客国庆集训派对day1 A 来自专栏

分析我们需要加几个字符在末尾将其变为回文串。那么我们可以很容易考虑到，回文中心一定在这个字符串上。那么当一个回文中心确定时，这个串其实也就确定了。那么添加的长度为。所以我们就应该寻找最大的可行的。那么当一个字符可以为回文中心时当且仅当，回文中心加上回文半径覆盖了第个字符的。那么求出每个...

2020-10-03

5 787