CF83D[numbers] 前言： 很好的一道数学容斥题。考察时间复杂度的分析。 2021/1/6 update: 因为笔者 , 一开始的做法比较劣（于是将题解重写了） 题意简述: 给定三个整数 ,, () 你需要求出区间内，有多少个数 满足: && 不存在一个 ∈ 使得 其中 表示 被 整除。 分析思路 我们发现一个很显然的性质。倘若 不是质数，那么最后的答案肯定是 为什么呢？ 因为倘若 不是质数，假若 那么肯定存在一个不等于 的大于等于 的因子 也满足 ， ，这时候肯定没有一个满足条件的 ，所以最后答案是 因此我们只需要考虑 为...

前言 这道题目是一道非常巧妙的贪心。 难度：4星 简略题意： 给定一个长度为 的序列,在序列中取至多三个数，使得这取的数互不为倍数关系。 ， 具体做法： 因为是最多取 3 个数，不妨按取的数的个数进行分类讨论。 ： 取一个数 这样的话当然是取最大的那个数最优，Pass。 ：取两个数 通过手玩几组样例后，我们发现最大的那个数总是出现在 取两个数得到的最大值中。于是大胆猜想，最后的答案一定会包含最大的数。 首先约定最大的数为 接下来我们严谨证明这一点： 证明： （不能为最大值,有可能取不到） 这时候，进行分类讨论： 倘若 都是 的因子，不同，所以 = ，不等式成立。这时候显然应该...

在比赛之前就说出是哪一些排名的人可以获奖不是会有人恶意控排名吗...... 建议考完后Rand发奖比较好。

A题 没有什么好说的，按照题目意思进行模拟即可。 比赛AC代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 判断x是不是好数 * @param x int整型 待判断的数 * @return bool布尔型 */ bool judge(int x) { int len = 0 , N[1005]; if(x <= 9) return true; while(x) {...

A题 没有什么好说的，按照题目意思进行模拟即可。 比赛AC代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 判断x是不是好数 * @param x int整型 待判断的数 * @return bool布尔型 */ bool judge(int x) { int len = 0 , N[1005]; if(x <= 9) return true; while(x) {...

A题 没有什么好说的，按照题目意思进行模拟即可。 比赛AC代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 判断x是不是好数 * @param x int整型 待判断的数 * @return bool布尔型 */ bool judge(int x) { int len = 0 , N[1005]; if(x <= 9) return true; while(x) {...

前言 难度:3星 做法:dp + 滚动数组优化 题目翻译（摘选自luogu（我翻译的，引用应该没有问题吧.....））： 简化题意： 给定一个的矩阵的前行，求满足每行以及每列的和为2的01矩阵的数量 思路 (这里提供的是 O()) 的做法。 观察到数据范围，发现不大像数学题，但是貌似也不是模拟题，看到方案数，就想到了 。 考虑怎么去除掉给出的前 行的影响。实际上这 行的用处不是很大，只是限制了某些列上填入的一的个数。 然后很轻松的可以得到，哪些列只能填入一个 以及哪一些可以填两个。 这样就把 的影响去除了。 如何设立状态? 分析： 因为并不需要知道哪一些位置填了 ，实际上只要记录一下...

题意简化： 给定一个长度为的序列，m个询问,每次询问一个区间内最长的没有重复数字的子序列,以及 <= 样例: 9 2 2 5 4 1 2 3 6 2 4 0 8 2 6 output: 6 5 思路一: 简单暴力，枚举区间内的子序列，然后O扫一遍，总的时间复杂度是O 思路二: 借助线段树，枚举子区间，判断,总的时间复杂度是:O 显然上面两个都是错误的，但是第二个貌似时间上更优秀......继续想! 思路三: 二分最长的长度，对于判断，每一次枚举左端点，那么右端点便是固定的，然后借助线段树O 上面这个解法已经比思路一和二优秀很多了。但是还是过不掉这道题，怎么办? 继续思考。 思路四： ...

前言 思想：树链剖分 算法：一道不太难的换根(换根?感觉不算是)+线段树 难度:3星 首先我们明确一个众所周知的事情： 一个子树的(不是欧拉序！)序是连续的，子树的根节点的序是最小的。 然后这个子树中最大的序为 (写过树链剖分的都知道吧。) 思路 因为只需要选择出两个，所以考虑枚举其中一棵子树，然后求最大的和当前字树没有重复节点的一棵子树。 考虑每次我们向儿子换根，因为每一次换根后，我们能够选择的子树的数量相对与没换之前是不断在增加的，这样子比较好维护状态。 新的可以选择的子树有哪些？ 不难发现，新的 可以选择的子树 即: 当前节点的父亲节点为根的子树内， 除了当前点为根的子树内的所有点以...

前言 这是一道很棒的思维题/数据结构！ 难度：2星做法：二分，排序 线段树 题意： 给定 以及 个区间，区间 有左端点 和 右端点 以及 花费 ,要求你选出两个区间,满足下面两个条件: 两个区间没有交集 两个区间的长度和等于 (这里的长度为 ) 现在要求你选出的这两个区间的权值和最小，输出最小权值和。 做法： 因为是两个区间，考虑枚举其中一个区间。 因为两个区间要不相交，所以很容易想到把所有区间按照其 从小到大排序，如果 相等，则按照 从小到大排序。 通过枚举区间 ，只需要找到所有左端点 大于其右端点 的区间 ，这样子 , 两个区间就是不相交的。 可以通过二...

前言 在错了N次之后，改动了一个小地方，多了一个+1就过了这一题，太惨了。 思路 假设只有前两个操作，我们实际上只需要生成一个差分数组，维护一个单点修改以及区间查询最大值即可。 但是最难的是操作3，区间GCD。 小蒟蒻在这里卡了许久，冥思苦想还是没有想到办法，最后百度：差分数组 与 区间GCD 然后知道了这个柿子: 也就是: 于是整个题目的基本做法已经出来了： 维护一个差分数组的绝对值最大值以及绝对值的gcd，然后对于每次操作1，就相当于是进行了一次单点修改,然后要维护区间信息，剩余的两个就是区间查询.gcd是具有区间可维护性的，也就是gcd(a,b,c,d) = gcd(gcd(a,b)...

#### 前言 这道题目的解法很多种，这里提供一种看似错误时间复杂度的正确做法以及证明，容我大放狂词，这是本题最优秀的算法，时间复杂度大概是O(n)。 #### 解法 首先把数据给出的 n 条边进行从小到大排序。 相信最大值大家都会，也就是判断第一个满足条件的 a[i] < a[i - 1] + a[i + 2] 的 a[i] + a[i - 1] + a[i - 2] 最小值暗藏玄机。 这是我寻找满足条件的最小周长三角形的做法 ```cpp         for(int i = 3 ; i &lt...

前言 这道题目的解法很多种，这里提供一种看似错误时间复杂度的正确做法以及证明，容我大放狂词，这是本题最优秀的算法，时间复杂度大概是O(nlog(n))瓶颈在于排序。 解法 首先把数据给出的 n 条边进行从小到大排序。 相信最大值大家都会，也就是判断第一个满足条件的 a[i] < a[i - 1] + a[i + 2] 的 a[i] + a[i - 1] + a[i - 2] 最小值暗藏玄机。 这是我寻找满足条件的最小周长三角形的做法 for(int i = 3 ; i <= n && flag; i ++) { ...

前言 这道题目其实就是 NOIP 2020 T4 微信步数 的40分做法。 这里提供 O( + )的做法 ------ 二分 + 前缀和(时间复杂度就是O(n))。 题目分析 不难发现，这道题目是要我们求最少多少天就会杀死怪物，同时，这个东西是具有单调性的。 （有解的情况下） 天数越多肯定就会扣除怪物越多的血量，所以我们可以采用二分。 同时，这个题目肯定许多情况会循环往复进行许多轮，所以我们二分的对象就是会进行多少轮。 具体做法 二分的话check函数就是二分的灵魂，往往check函数就会决定二分的复杂度。 采用前缀和优化后，我们可以找一个前缀和数组中的最小值 ？ 求出来的 就是表示在同一...