DeNeRATe

题解

/ 注册

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

对称二叉树

分析一个非常自然的想法就是枚举每个节点作为对称二叉树的根然后左右遍历检查是否合格最后取一个max 那么这个时间复杂度是多少呢首先我们知道，若以为根节点那么只有当左右子树大小相等时可以向下遍历那么我们进而想，什么情况下会有最多的可以遍历的根呢当然就是完全二叉树的时候因为一个点会被遍历，当且仅当根为其...

2020-10-16

5 751

Quasi Binary

分析易证：对于一个位置上的1来说，直接消除，绝对比进位消除优（显然所以我们只需要每次贪心消去非零位上的一个1即可代码 //20zr 18 day4 C #include <algorithm> #include <iostream> #include <cstrin...

2020-10-15

2 722

物流运输

分析由于数据范围非常小我们可以有很多大胆的乱搞尝试Dijkstra + DP我们不知道哪一天会修改路线那我们就考虑吧所有的情况算出来也就是Va[i][j]表示第i天到第j天都使用一套方案的最短路那么我们就可以直接枚举断点也就是的暴力DP即可时间复杂度：（是因为边数可能会有）吐槽洛谷得了一个最优...

2020-10-15

4 830

Garland

分析首先我们考虑什么时候可能有解当整棵树的权值和为3的倍数时（显然至于判断是否可以分成这三个等分时我们先考虑两次分割深度最大的那一次分出来等于答案的一定是它的子树且我们知道，当一个子树权值和时我们必须要把它分出去否则它不可能存在于其他任何分区所以我们每次遇到子树权值和等于的直接减去即可代码...

2020-10-13

3 684

筱玛爱线段树

分析观察题目可以发现题目要求维护两种数组的区间加当Opt==2时，将操作区间加一当Opt==1时，将数组范围内的数加一我们还发现，第一种区间加，会影响第二种区间加所以我们在维护第一种区间加的基础上再维护第二种区间加并且我们发现第一种区间加会影响它之前的询问所以我们需要倒叙维护每个操作的次...

2020-10-12

6 656

Angry Cows(Silver)

分析题目中说的最小的满足值，那么就是二分答案Check:每次贪心当两个端点距离小于Mid时就增加一段即可代码 //P6174 #include <algorithm> #include <iostream> #include <cstring> #includ...

2020-10-10

3 651

网络优化

分析首先这儿有一道思想比较类似的题P1250 种树都是比较简单的贪心但具体的情况是不一样的我们发现，对于这个用户，所有可以覆盖他的段为那么我们按照为双关键字排序之后贪心得选取第一个可以继续放的区间一定是不会使结果劣时间复杂度：代码 // #include <algorithm> #i...

2020-10-03

4 675

Minimizing maximizer

吐槽看这道题的时候，由于英语太菜读题读了好久都没读懂依据暂时的理解打了一个程序之后发现一直WA最后在玄学注释（去掉排序）程序的时候，居然A了。。。之后在机房英语巨佬シンドリー的帮助下才懂得了题意。。。分析不太懂题意的，可以看看这位巨佬的Blog一眼题？（以前在Atcoder上边好像做过类似的题...

2020-09-29

4 721

Leaf Partition

分析本题初看没有任何思路但经过长达1个小时（有点夸张）的端详我们可以注意到对于一个图中所说的包含部分叶子的虚树上边的节点分为两类作为一条边经过，即：当前被染色，并且染了他的一个儿子作为一个LCA经过，即：当前节点被染色，并且它的两个及以上节点被染色为什么我们需要分开1个儿子和两个及以上儿...

2020-09-28

5 669

Stressful Training

分析看到这种满足要求的最小值第一个想法就一定是二分答案我们只需要明确一点即：一定会优先给最快要没电的人充所以很自然就会想到每个事件贪心维护最快要没电的人使用priority_queue（大佬们也可以手写堆。。。）时间复杂度：温馨提示如果队列里边没有元素了，那么就返回true，无需多留当前点...

2020-09-28

2 835