__故人__

题解

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

/ 注册

全部文章 / 题解（共116篇）

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

题意给你两个整数，要求求出约瑟夫问题中最后一个人是谁。分析总所周知，约瑟夫问题有模拟，线性。这里解释一种的解决方法。考虑到我们每次走个删一个，那么在一圈以内我们可以删掉个。我们可以模拟这个过程递归求解。由于每次递归问题规模变为。通过归纳验证时间复杂度大概是代码...

2020-10-13

4 846

Garland

分析我们对于每个子树的答案是可以预先知道的，那么如果那么一定无解。之后我们可以直接遍历整个树得到的节点。那么当这样的节点个数超过的时候，这个树就是合法的，输出两个非树根的节点就可以了。那么总的复杂度为。代码 #include<bits/stdc++.h> usin...

2020-10-13

5 628

筱玛爱线段树

分析我们主要考虑如何处理的操作又重新做一次，这个我们考虑区间加，定义为第次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做，那么最后的复杂度为。差分，我们定义数组，如果原值为。那么满足。那么给全部等同于。这样我们对...

2020-10-12

11 688

Angry Cows(Silver)

分析我们可以考虑一个合法答案，那么，则也是一个合法答案。那么这个满足单调性，我们可以考虑二分，如何判断是否是一个合法解。我们考虑贪心，从左向右考虑，每次考虑最靠左而且没有被现在的区间覆盖的点。对于这个点也可以二分，好像直接做也没有问题。那么最后判断是否就可以了。代码中所有二...

2020-10-10

3 685

牛客练习赛71 C 来自专栏

分析我们可以假象一个假的限制记录前个条件都满足，但第个条件不满足的方案数，考虑之间的数随便排列，，然后第个条件不满足，前个条件都满足，乘；对于不同的，方案是不相交的，且计算了所有不应该在中计数到的方案数所以。思路来源与不知名的大佬。我这里只是分享一下做法...

2020-10-10

9 552

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牛客国庆集训派对day1 G 来自专栏

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

2020-10-05

5 577

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

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

2020-10-05

6 623