思路 通过大胆猜想与小心伪证,我们可以得到一个结论:  在任何一条直径求得的最小偏心距都是相等的.  有了这个结论,我们就可以乱搞啦.对于直径,若选取的核为,最小偏心距只有可能为,,或者是选取整条直径为核时的最小偏心距.(十分好证)那么先求出某条直径的最小偏心距,然后在直径两端分别为虎一个指针,不断向中间靠拢,直到两个指针指向的节点小于为止即可.这样复杂度就是的,可以通过. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define MAXN 305 #define fp( i, b, ...

思路 好恶心的卡常题(虽然一边颓废一边写,还是卡了一下午).如果空间和时间足够大,我们可以考虑对每一种粮食开一个大小的数组,若某条路径放类型的粮食,,树上前缀和,然后找出最大值即可.不过这样就算是离散化后,时空复杂度都是.不过这样直接把开的数组改成动态开点线段树就好了.求前缀和的过程可以看成线段树合并.由于空间不是很足(主要是洛谷,牛客网给的内存海星,但是时间就...),因此需要对颜色进行离散化.时间复杂度为.然后只要注意常数问题就OK.("只要"?) 代码 #include<cstdio> #include<algorithm> using namespace std...

思路 我们需要把所求的东西转换一下.容易想象,取出所有节点建一棵虚树(放心,不用真的建,只要知道是什么就OK.也就是将所有节点以及两两之间的(以下称为关键点)取出来建树,若两个关键点之间的路径没有其他关键点,就将这两个关键点之间连边,长度为两个关键点的距离),虚树所有边长度和即为答案.想象遍历这颗虚树的过程,每条边恰好访问两次.按照DFS序排序,相邻两点以及DFS序第一个和最后一个之间的距离之和除以二即为答案.当然(前面也说过),不用这真的建虚树.直接将有异象石的节点取出来向上面一样处理即可.对于并没有异象石的却是关键点的节点,也不用担心,它至少有两颗拥有异象石节点的子树(将这两个节点设为,)...

思路 删去一条树边能把树断成两个联通块.未删去的非树边不能把两个连通块再连回去(否则不是白搭了2333).如果一条非树边与树上的边构成一个环,删去这个环的树边的同时,必须将这两条边同时删去.如果某条树边同时在好几个环中,肯定不能删去这条树边,因为只能删一条非树边,删了条非树边,剩下的还是连通.对于一条非树边,原树上至的路径所有树边都覆盖一次(这些边能与非树边构成一个环),只覆盖过一次或一次都没有的树边才有可能删去,删去覆盖过一次的树边只能删去与其构成环的非树边,删去没覆盖过的树边再删去任何一条非树边都没问题.所以说,只要计算每一条树边被覆盖了几次就OK了.暴力计算需要的复杂度,用树前缀和计算就...

思路 先建出最小生成树,然后考虑删去树上一条边,加入一条非树边.枚举一条非树边加入,然后需要选出树上节点,之间的路径的一条边删去.很明显,删去的边应该越大越好,但是不能与边相等,否则就不是严格次小了,因此需要求出树上路径边权的最大值和最小值,可以使用倍增LCA解决qwq.最生成树复杂度为,寻找替换边的复杂度为,然后预处理的复杂度为 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define MAXN 100005 #define MAXM 300005 #define fp( i, b,...

思路 当时,答案显然是树的直径减去新增的那条边.因为加上这条边,可以变成一棵基环树,那个环上的每条边只要走一编,其他边仍然要走两遍.当时,因为是两个环,要考虑这两个环是否相交.如果不相交,这两个环上的边都可以少走一遍.如果相交,这两个环共有的边仍然要走两遍(可以自行画图理解).这样就有一种做法,先找出直径,并把直径上所有的边长度变为原来的相反数,再找一次直径即可.找出直径具体包括哪些路径用两遍DFS更加方便,但是两遍DFS似乎不能处理有负边的情况,只能用树形DP. 代码 #include<bits/stdc++.h> using namespace std; #define MAX...

思路 一种简单的思路就是不断地将可以够到的磁力块进队列,并且将未进队列,但是队首磁石能够到磁石全部进队列.这样主要的复杂度就在于寻找磁石可以够到的磁石.如果暴力找的话复杂度就退化成了.用线段树等数据结构来维护似乎并不怎么可靠.所以就要用可愛い 分块啦qwq.按照每个磁石与的距离排序并分为个块,每个块内分别按照磁力排序.每个块维护一个指针,每块第一个元素至都已经进队过.每次用磁石吸引其他磁石时,对于所有所包含磁石距都不大于的半径的块,直接移动,将质量不大于的磁力的磁石全部吸引过来.剩下的可以吸引过来的磁石肯定在后面一个不完整的块,暴力枚举所有磁石并打上标记即可.前面进行的吸引时别忘了把打过标记的...

思路 莫队基础题.对于每个区间,设颜色的出现次数为,答案就是,分子的意义是任意选两只袜子,颜色相同的对数(可重复选,与顺序有关)减去重复选同一只的情况.莫队维护.加入一个数,减去加入前该数出现次数的平方,加上加入后该数出现次数的平方,删去一个数则恰恰相反.因为是以前写的代码,计算时分子分母先除了个2(表示与顺序无关),事实上是不用的. 代码 #include<bits/stdc++.h> using namespace std; #define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout ...

(话说这篇题解我在洛谷发过,所以图有水印...) 思路 扫描线经典题.图1我们从左到右扫描所有的纵向边. 图2 - 红色边即为依次扫描到的边. 这些边可以用一个结构体记录.需要记录横坐标,上下边界(纵坐标),是一个矩形的结束还是开始.扫描这些边时,我们用数据结构维护每个位置纵坐标被矩形覆盖了多少.如样例,当至时,覆盖了至的部分,当至时,覆盖了至的部分,以此类推.注意覆盖的部分不一定是连续的,因此我们数据结构只维护覆盖的长度,即覆盖了至,我们只记录覆盖长度为.然后我们就可以每一段分别求出覆盖的面积并加起来就是答案了. 图3 - 这些面积加起来就是答案 然后我们还需要解决怎么维护覆盖长度.如果暴力...

思路 简单的逆元入门题.如果是质数,直接用费马小定理求解即可.这里不一定是质数,所以要用.设存在整数使得.那么很明显.因此只要解出即可.直接用求出一组可行解,对取模即可.这里保证有解,因此不用判断是否为.复杂度为,也就是的复杂度. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i &...

思路 矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.代码中的矩阵可能稍微有点不同,毕竟是以前写的代码.不过只要理解矩阵加速递推就没问题了.由于这是多组数据,一种优化方法是将全部存起来(其中表示递推矩阵).大概可以减少一半的常数.注意边界问题复杂度大概为 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ...

思路 这题有好几种做法.你可以构造的矩阵,也可以的,还可以的.这里就讲的吧...   然后只要算出和就OK了.时间复杂度 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i ) #define go( i, b ) for ( int i(b), v(to[i...

思路 这题有两种思路. 思路1 构造矩阵直接求出然后跑矩阵快速幂即可. 思路2 怎么证明呢?我们可以使用数学归纳法. 时显然成立.对于,.因此就相当于求斐波那契数列第n+2项-1.很明显思路2的时间/空间/代码复杂度都更加优秀. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i &g...

思路 矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.矩阵构造方法很多,怎么构造开心就好.注意一些小细节,因为可能是,最后输出是也最好取模一下.平时写矩阵就注意下常数优化.毕竟矩阵乘法的常数还是比较大的. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >=...