分析 由于每一位之间的计算是独立的并且最后选择每个位上的数时一定是贪心取0而后取1所以我们可以对于每一位取1或0进行操作但这样的话复杂度比较高我们直接考虑用一个全1的二进制数（-1）和全0的二进制数（0）进行所有操作最后贪心取0或1即可时间复杂度：期望得分：100分温馨提示：注意细节，需要判到32位，不然只有90。。。 代码 //P2114 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #de...

分析 我们发现一个点是否可以作为魔法书的点当且仅当距离他最近的点的距离所以我们可以像求树的直径一样DP求得每个点向下的距离最大值和距离次大值以及向上的距离最大值最后在求完之后，统计一下有多少个点满足 即可时间复杂度：期望得分：100分 代码 //CF337D #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long long #define Cl(X,Y) memset((...

分析 首先我们可以列出一个转移方程式 我们发现这个转移式其实是01背包和完全背包的合并版所以我们可以分开进行维护温馨提示:一定要理清思路之后再下手,不然就在线%JK_LOVER巨佬 代码 //P1941 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long long #define Cl(X,Y) memset((X),(Y),sizeof(X)) #define FO...

BIBI 昨天没打挑战赛，今来补一下题。。。看到E是一个构造，我就来了 /jk 分析 （听说这是一道2019年上海高三数学竞赛的压轴题）（个人还没有看MO的题解，所以我就先说说我的思路吧）（这里我们把换成表示）我们考虑巨阵和巨阵之间的关系---他们之间两两的三条边会不会有公用的边显然可知，不可能存在这种情况，即，只会出现图中所示的情形进而，我们考虑构造题的套路---是否能够得到一个上界，我们再想办法去构造它假设总共有个巨阵，共有行（列）那么我们考虑每个点的出度在个巨阵排成一串时共有个点出度为，且个点没有出度（这个很好想到）又因为一个巨阵消耗个出度那么我们可以列出一个表达式： 我们做一下简单的化...

分析 一个非常自然的想法就是枚举每个节点作为对称二叉树的根然后左右遍历检查是否合格最后取一个max 那么这个时间复杂度是多少呢首先我们知道，若以为根节点那么只有当左右子树大小相等时可以向下遍历那么我们进而想，什么情况下会有最多的可以遍历的根呢当然就是完全二叉树的时候因为一个点会被遍历，当且仅当根为其祖先那么完全二叉树时，总共有个祖先所以总的时间复杂度为： 代码 由于这道题是很久以前做的，码风比较清奇 #include<iostream> #include<cstdio> #include<cmath> #include<queue> #inclu...

分析 易证：对于一个位置上的1来说，直接消除，绝对比进位消除优（显然所以我们只需要每次贪心消去非零位上的一个1即可 代码 //20zr 18 day4 C #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long long #define Cl(X,Y) memset((X),(Y),sizeof(X)) #define FOR(i,A,B) for(int i=A;i&l...

分析 由于数据范围非常小我们可以有很多大胆的乱搞尝试Dijkstra + DP我们不知道哪一天会修改路线那我们就考虑吧所有的情况算出来也就是Va[i][j]表示第i天到第j天都使用一套方案的最短路那么我们就可以直接枚举断点也就是的暴力DP即可时间复杂度：（是因为边数可能会有） 吐槽 洛谷得了一个最优解，牛客始终拿不到，Rank 1那位巨佬%%% 代码 //P1772 #include <algorithm> #include <iostream> #include <cstring> #include <queue> #include <c...

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

分析 观察题目可以发现题目要求维护两种数组的区间加  当Opt==2时，将操作区间加一 当Opt==1时，将数组范围内的数加一  我们还发现，第一种区间加，会影响第二种区间加所以我们在维护第一种区间加的基础上再维护第二种区间加并且我们发现第一种区间加会影响它之前的询问所以我们需要倒叙维护每个操作的次数由于是区间加，并且需要遍历数组，所以我们直接考虑差分即可最后再来从头到尾扫一次数的差分数组即可得到答案温馨提示：到处都要记得取模，否则/xyx 代码 //Nowcoder 25737 #include <algorithm> #include <iostream> #inc...

分析 题目中说的最小的满足值，那么就是二分答案Check:每次贪心当两个端点距离小于Mid时就增加一段即可 代码 //P6174 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long long #define Cl(X,Y) memset((X),(Y),sizeof(X)) #define FOR(i,A,B) for(LL i=A;i<=B;i++) #def...

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

吐槽 看这道题的时候，由于英语太菜读题读了好久都没读懂依据暂时的理解打了一个程序之后发现一直WA最后在玄学注释（去掉排序）程序的时候，居然A了。。。之后在机房英语巨佬シンドリー的帮助下才懂得了题意。。。 分析 不太懂题意的，可以看看这位巨佬的Blog一眼题？（以前在Atcoder上边好像做过类似的题）我们需要的是按照题目给定的序列顺序找出其中的几段能够使得每两端之间有至少一个交点的情况下覆盖整段序列我们设DP[i]表示覆盖完所需要的最小段数所以我们可以得到DP方程 发现，这个状态转移是一个区间最小值的转移所以我们直接上线段树优化DP即可 代码 //POJ 1769 #include <a...

分析 本题初看没有任何思路但经过长达1个小时（有点夸张）的端详我们可以注意到对于一个图中所说的包含部分叶子的虚树上边的节点分为两类  作为一条边经过，即：当前被染色，并且染了他的一个儿子 作为一个LCA经过，即：当前节点被染色，并且它的两个及以上节点被染色  为什么我们需要分开1个儿子和两个及以上儿子呢？因为第一种情况无法作为当前虚树的根节点反之，第二种情况就是可以的当然，对于整棵树来说，就还有一种类型的节点  没有被染色  想到这里，剩下的工作也就不太麻烦了，只是转移非常的细节我们设DP[][0]表示上边的第三种情况DP[][1]表示上边的第一种情况DP[][2]表示上边的第二种情况所以我们...

分析 看到这种满足要求的最小值第一个想法就一定是二分答案我们只需要明确一点即：一定会优先给最快要没电的人充所以很自然就会想到每个事件贪心维护最快要没电的人使用priority_queue（大佬们也可以手写堆。。。）时间复杂度： 温馨提示  如果队列里边没有元素了，那么就返回true，无需多留 当前点会在限定时间内没电，那么才会进队 尽量不要使用过多的除法运算（因为我就是被这个东西卡了10+次提交） 由于这道题答案有点大，所以二分的有边界需要设到2e12cai'ke  代码 //CF1132D #include <algorithm> #include <iostream&gt...