louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 算法竞赛进阶指南闇の連鎖

思路删去一条树边能把树断成两个联通块.未删去的非树边不能把两个连通块再连回去(否则不是白搭了2333).如果一条非树边与树上的边构成一个环,删去这个环的树边的同时,必须将这两条边同时删去.如果某条树边同时在好几个环中,肯定不能删去这条树边,因为只能删一条非树边,删了条非树边,剩下的还是连通.对于一...

树上倍增前缀和

2019-08-21

0 509

题解 | 算法竞赛进阶指南次小生成树

思路先建出最小生成树,然后考虑删去树上一条边,加入一条非树边.枚举一条非树边加入,然后需要选出树上节点,之间的路径的一条边删去.很明显,删去的边应该越大越好,但是不能与边相等,否则就不是严格次小了,因此需要求出树上路径边权的最大值和最小值,可以使用倍增LCA解决qwq.最生成树复杂度为,寻找替换边...

树上倍增

2019-08-21

0 652

题解 | 算法竞赛进阶指南巡逻

思路当时,答案显然是树的直径减去新增的那条边.因为加上这条边,可以变成一棵基环树,那个环上的每条边只要走一编,其他边仍然要走两遍.当时,因为是两个环,要考虑这两个环是否相交.如果不相交,这两个环上的边都可以少走一遍.如果相交,这两个环共有的边仍然要走两遍(可以自行画图理解).这样就有一种做法,先找...

树的直径

2019-08-21

0 659

题解 | 算法竞赛进阶指南磁力块

思路一种简单的思路就是不断地将可以够到的磁力块进队列,并且将未进队列,但是队首磁石能够到磁石全部进队列.这样主要的复杂度就在于寻找磁石可以够到的磁石.如果暴力找的话复杂度就退化成了.用线段树等数据结构来维护似乎并不怎么可靠.所以就要用可愛い分块啦qwq.按照每个磁石与的距离排序并分为个块,每个块...

分块

2019-08-20

0 647

题解 | 算法竞赛进阶指南小Z的袜子

思路莫队基础题.对于每个区间,设颜色的出现次数为,答案就是,分子的意义是任意选两只袜子,颜色相同的对数(可重复选,与顺序有关)减去重复选同一只的情况.莫队维护.加入一个数,减去加入前该数出现次数的平方,加上加入后该数出现次数的平方,删去一个数则恰恰相反.因为是以前写的代码,计算时分子分母先除了个2...

莫队

2019-08-20

0 749

题解 | 算法竞赛进阶指南 Atlantis

(话说这篇题解我在洛谷发过,所以图有水印...) 思路扫描线经典题.图1我们从左到右扫描所有的纵向边. 图2 - 红色边即为依次扫描到的边. 这些边可以用一个结构体记录.需要记录横坐标,上下边界(纵坐标),是一个矩形的结束还是开始.扫描这些边时,我们用数据结构维护每个位置纵坐标被矩形覆盖了多少.如...

线段树扫描线离散化

2019-08-20

0 789

题解|信息学奥赛一本通-提高篇同余方程

思路简单的逆元入门题.如果是质数,直接用费马小定理求解即可.这里不一定是质数,所以要用.设存在整数使得.那么很明显.因此只要解出即可.直接用求出一组可行解,对取模即可.这里保证有解,因此不用判断是否为.复杂度为,也就是的复杂度. 代码 #include<bits/stdc++.h> u...

exgcd

2019-08-20

0 654

题解|信息学奥赛一本通-提高篇 Fibonacci

思路矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.代码中的矩阵可能稍微有点不同,毕竟是以前写的代码.不过只要理解矩阵加速递推就没问题了.由于这是多组数据,一种优化方法是将全部存起来(其中表示递推矩阵).大概可以减少一半的常数.注意边界问题复杂度大概为代码 #include&l...

矩阵乘法斐波那契数列快速幂

2019-08-20

0 717

题解|信息学奥赛一本通-提高篇佳佳的Fibonacci

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

矩阵乘法快速幂斐波那契数列

2019-08-20

3 714

题解|信息学奥赛一本通-提高篇 Fibonacci前n项和

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

矩阵乘法快速幂斐波那契数列

2019-08-20

2 848