Maddison10

每日一题题解

NOIP模拟赛题解(1) 每日一题笔记(3) 比赛总结(3) 牛客周赛普及组&提高组(2) 牛客多校比赛(4) 牛客练习赛|挑战赛|小白月赛题解(5) 知识点学习笔记(3) 题解(1)

/ 注册

全部文章 / 每日一题题解（共11篇）

每日一题 CF916E Jamie and Tree 题解

会写就行了，我们先求出在root情况下的lca，发现实际上是所有lca中深度最大的那个，于是我们可以分情况大力讨论一下lca和root的关系，同理我们query的时候也是讨论一下当前x和root的关系剩下就只需要一个求k级祖先的过程，这个我们可以长链剖分，但是作者直接写了个倍增的log求法剩下树剖就...

2021-01-26

0 626

每日一题 CF620E New Year Tree 题解

首先我们把树上的子树问题转化成一维序列上的问题之后我们发现颜色数的处理暴力合并比较慢，但是由于颜色数较小，我们可以直接压位一下，然后直接取个or就可以了实际上不需要什么bitset，builtinpopcountll也是O(1)复杂度的！具体实现线段树上打tag常规操作做一下。代码： #includ...

2021-01-21

0 716

每日一题最长树链题解

这道题之前可以用4e8左右的复杂度通过，现在加强了一发好像有很多质数，我们只需要套用millerRobin就可以通过现在的数据了，但是其实还有办法卡，因为标算应该是还要加上pollardrho，我们只需要对于所有的质因数见一个树，实际上不用建出来，然后根据这个质因数在树上DFS，还是按照平常找直径的...

2021-01-20

0 610

每日一题 CF798D Mike and distribution 题解

与其说这题是贪心题这题更像一个构造题，非常开阔思维首先我们随便以一个A或B为关键字排序，然后发现N/2+1这个加1很重要，根据经验暗示我们选第一个然后接下来我们钦定假设以A为第一关键字排序于是我们剩下的每两个选一个B那位max的，可以发现B显然是满足条件的，那么A满足条件吗？a[1].A>=m...

2021-01-19

0 577

每日一题小M和天平题解

提供一种新做法，理论复杂度更快，我们用bitset加速维护发现一共只有三种可能，放左边放右边和不放我们初始设定一个sum以防负数，然后左右移位就可以了代码： #include<bits/stdc++.h> using namespace std; #define LL long long...

2021-01-18

0 619

每日一题 CF665E Beautiful Subarrays 题解

这题还是有点新意的，套路部分就不讲了，我们套路前缀和，然后就知道要用一个trie树这样的东西来维护一下，如果有人这里不是很熟可以看一下我之前写的https://blog.nowcoder.net/n/744869ac01154d47b1240cfaebc3839e接着我们来看一下如何处理，我们有点像...

2021-01-14

0 665

每日一题 [HAOI2006]旅行题解

简单题，我们发现边数和点数都很小允许我们可以用平方做法来做，然后我们直接枚举最小的边权，依次往上最小做生成树，然后把所有得出的答案取个最优就可以了，在这里我们可以把并查集的复杂度看成是O(1)的，因为边数只有500。具体细节需要我们判断分数的大小和一些无解的情况，看一下代码就ok了代码： #incl...

2021-01-14

1 596

每日一题 CF83D Numbers 题解

首先我们发现要记录的东西可以搞成一个最小表示法来记录我们只需要把这个最小的k作为表示方案就可以了然后具体的我们每次求这个答案需要递归容斥下去首先要是能被k整除的，其次我们把小于k的方案减去即可具体我们写个calc函数然后不断递归就可以了！细节是我们要判断一下不是质数的情况直接return 0我们可以...

2021-01-14

0 602

每日一题 [JLOI2016/SHOI2016]侦察守卫题解

这题是一个比较妙的DP题，我们并不能像处理普通的树形DP题那么做我们发现我们一个点覆盖距离小于等于d的所有点，不仅仅是只涉及到祖先节点，还包括一条折线的情况，因此我们不是能很好的直接利用子树信息转移我们在首先定义一个F的dp数组外还要定义一个G我们定义F[x][i]代表x的子树还有i层没有完全被覆盖...

2020-12-18

3 683

每日一题 CF786B Legacy 题解

普通建图的最短路肯定跑不过，我们要尝试优化建图具体两种方法：1.线段树优化建图我们类似于线段树区间操作区间连边其实每个节点我们分别设一个in和out代表向儿子连边，以及儿子向自己连边即可2.倍增优化建图同样的道理用类似st表维护，但是会在操作很多点数较少的时候有较大的优势，因为每次操作两条边就可以搞...

2020-11-12

3 586