DeNeRATe

分类

题解(55)

/ 注册

全部文章（共52篇）

倍增

说在前面的本人实力不高，求大佬轻喷，我尽量讲清楚一点。例题传送门在未作说明的情况下，有根树都以为根。表示，节点的最进公共祖先。表示，节点的深度。表示，节点的树上简单路径长度。倍增倍增法（英语：），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，...

哲哥

2020-11-25

14 929

Network

分析考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为。这个考虑树链剖分或者维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了实现，时间总复...

哲哥

2020-11-20

8 983

多项式开根号来自专栏

引入求出多项式是满足系数对一个数取模。推导还是利用牛顿迭代。那么代入牛顿迭代的公式为然后没有学习过牛顿迭代的朋友可以看我上一篇。当然这下面这份代码不能解决的情况。那个时候应该使用二次剩余。代码 #include<bits/stdc++.h> using ...

哲哥

2020-10-16

3 975

[ZJOI2006]物流运输

分析我们可以对于每一天考虑，如果有一天改了道，那么贪心的选择也应该是最短路，而不是其它的路径。这个还是比较显然的。那么现在考虑一个线性。令表示考虑从第天的最小代价和。那么转移为。这里引入了一个的数组。这里表示从第天到第天的合法的最短路。那么我们可以先预处理总的复...

哲哥

2020-10-14

6 668

网络优化

分析我们看出，这是一个匹配问题。左边的点只能匹配右边的节点。而一个节点可以匹配的数量为。我们可以考虑用网络流来解决这个问题。向左边节点连接一条容量为边。右边节点向连接一条容量为的边。如果右侧节点满足，那么左侧节点向连一条容量为的边。最后 ...

哲哥

2020-10-01

5 929

Mike and Friends

分析可以说是关于自动机运用的较难题了。但是能用坚决不用自动机。我们考虑一个串作为字串出现在其它字符串中，那么就是看这个串的结束节点的集合有多少这个区间的串。所以现在的思路就是，对所有串建一个广义后缀自动机，这里不能建那种之后就不管的伪自动机。要使用树建法，或者在线建法。然后...

哲哥

2020-09-28

6 638

[HAOI2008]硬币购物来自专栏

分析背包题。因为朴素的的时间复杂度为应该过不去。那么换种思路，先考虑没有个数限制，令为考虑前种物品，体积为时，总的方案数。发现我们对个数的限制可以考虑子集容斥。考虑到，恰好选个的方案数是等于至少选个的方案数减去至少选的方案数。那么现在是让我们求恰好选到个...

哲哥

2020-09-23

4 783

超能粒子炮 · 改来自专栏

分析如果我们读完题发现我们要求的是这个，定义一个二元组，根据定理，可以推导到在一波无情的推式子之后，这道题就做完了。代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL rea...

哲哥

2020-09-22

4 754

排列

分析我们对于一个节点考虑，如果有一个点两维都大于，那么这个节点肯定不可能作为结尾。因为考虑一下，如果排列先出现，那么这个两维都是单调不降的，所以不可能转移到，反之，如果先出现，它一定保持不住结尾，最后整个图构成了一个有向无环图，每一个节点可以等概率转移到后置节点。那么一个...

哲哥

2020-09-21

5 1019

牛客小白月赛28 J 来自专栏

分析其实如果一条边链接了两个颜色不一样的节点，其实这个边根本没有任何意义，因为你从任意方向都不可能进入这条边，那么我们只需要用并查集维护集合数量就可以了。代码 #include<bits/stdc++.h> using namespace std; int read() { ...

哲哥

2020-09-21

6 624