louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共81篇）

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

思路一种简单的思路就是不断地将可以够到的磁力块进队列,并且将未进队列,但是队首磁石能够到磁石全部进队列.这样主要的复杂度就在于寻找磁石可以够到的磁石.如果暴力找的话复杂度就退化成了.用线段树等数据结构来维护似乎并不怎么可靠.所以就要用可愛い分块啦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

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

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

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

2019-08-20

0 611

题解 | 信息学奥赛一本通-提高篇矩阵 A×B

思路很基本的矩阵乘法.直接根据矩阵乘法的定义暴力求解即可.别忘了开long long. 复杂度为.事实上还有一种更优秀的做法Strassen可以把复杂度优化到.不过话说回来一般不会遇到这么毒瘤的出题人来卡你,感兴趣的童鞋可以去网上查找资料. 代码 #include<bits/stdc++.h...

矩阵乘法

2019-08-20

0 611

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

思路题意是求莫比乌斯反演最重要的当然就是推柿子.假设,不满足的话swap一下就OK了这就是一个用数论分块可以解决的东西.只要预处理一下前缀和就OK了.数论分块一次的复杂度为,因此总复杂度为.因为不是很卡常数所以没有优化除法....至于如何优化除法可以参考https://www.luogu...

莫比乌斯反演数论分块积性函数

2019-08-19

0 617