Maddison10

分类

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

/ 注册

全部文章（共33篇）

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

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

2020-12-18

3 681

每日一题倍增专题总结

本期每日一题的题目大概分成两种倍增：树上倍增和解决综合问题的倍增倍增的大致思想是利用二进制优化，来加快我们做一个事情，或者找到一个东西的过程，我们通常可以利用二进制拆分，或者是二分的思想在一个log级别的时间内快速求出我们想要的答案！我们分别介绍一下：首先是树上倍增，这个比较基础也是会经常考察到的一...

2020-12-10

5 710

每日一题 dfs序专题总结

Military Problem简单题，我们预处理出dfs序，然后查询的时候之间判断一下sz的大小，就可以了！代码： #include<bits/stdc++.h> #define fgx cerr<<"-----------------------"&l...

2020-11-20

2 736

2020牛客NOIP赛前集训营-提高组（第一场）题解

A:牛牛的方程式裴蜀定理裸题，注意判断一下gcd=0的情况，剩下然后我们判断一下是否整除 #include<bits/stdc++.h> #define LL long long using namespace std; LL gcd(LL x,LL y){ if(!y)retu...

2020-11-17

2 633

每日一题 CF786B Legacy 题解

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

2020-11-12

3 582

每日一题 [SCOI2011]棘手的操作题解

一道不错的有关于各种tag我们熟练维护的题首先这题可以1个log的左偏树做，但是考虑到细节较多我们用两个log的启发式合并来写，当然你也可以用splay可以自适应做到1个log。我们这里的splay换为set方便维护首先我们单点加和整体加都可以非常方便的维护，于是我们只剩下对于一个联通的集合加一个数...

2020-11-10

1 559

每日一题 01trie专题总结

The XOR LargestPair 奶牛异或这前两道题比较简单，而且我们直接运用01trie上查找最优值就可以，代码就不给了。主要讲一下底下的几道题吧Vitya and Strange Lesson这道题我们首先要发现一个性质，就是其实我们每次xor上一个数的时候都是整体xor上，因此所有数...

2020-11-05

2 671

并查集笔记&总结

并查集的主要用处是解决一类连通性问题的，遇到此类雷同问题，我们通常可以用并查集维护，往往可能在一些比较简单的问题中比dfs和bfs有更好写的优势。并查集的代码很短，主要我们是判断连通性和uni，就是我们把两个连通块合并的操作，接下来我们会引出几个具体的函数。具体呢，我们先讲并查集维护的思想首先我...

2020-10-15

2 869

牛客小白月赛28题解

A:牛牛和牛可乐的赌约简单题，我们还是正难则反，概率减一下全赢的概率就可以了。代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int P=1e9+7; LL qpow(LL x,LL ...

2020-09-26

1 638

牛客IOI周赛18-提高组题解

A:排列简单题，我们发现m不大，我们暴力模拟m次翻转过程。然后我们针对一次的变换求出倍增数组，倍增即可。复杂度：O(nm+nlogk)代码： #include<bits/stdc++.h> #define LL long long using namespace std; const i...

2020-09-26

1 663