生之、如舟

分类

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

TA的专栏 67篇文章 1人订阅

Ryuichi的算法分享

67篇文章 1416人学习

全部文章（共166篇）

ZOJ1610-Count the Colors 【线段树】【区间覆盖】【区间合并】

Count the Colors 题目在[0,8000]区间进行N次区间染色，后涂的色可以覆盖之前涂的色，问N次染色之后，能看见的颜***间数量各是多少？分析其实这题区间覆盖这部分很好做，不需要离散化，因为只有8000长度的区间。我们要注意的是，需要将区间改成左开右闭的形式，比如给[0,2]，...

线段树

2020-02-28

0 1235

HDU2528-Mayor's posters 【线段树】【区间覆盖】【离散化+插点】

Mayor's posters 题目有一面墙，现在有M张海报要贴，海报的高度和墙的高度一样，每张海报会给出区间范围[l,r]，问最终墙上可见的海报有多少张？墙的宽度: 分析首先这题的墙的范围很大，所以必须离散化，然后在离散化之后的数据上建立线段树。要点这题对于染色后连续的区间[l,r]有可能...

线段树

2020-02-28

0 706

HDU1698-Just a Hook 【线段树】【区间覆盖】

Just a Hook 题目给定一个区间[1,N]，里面的元素都是1，现在有M次区间修改的操作，每次会选择一个区间将其置为1或2，或3，问最后区间[1,N]的元素总和为多少？分析这是一道典型的区间覆盖问题，用线段树可以很好的解决。只需要在定义结点的时候，加上sum和tag就行。sum表示此结点...

线段树

2020-02-28

0 974

acwing243. 一个简单的整数问题2 【线段树区间修改】【模板】

243. 一个简单的整数问题2 AC代码 #include <iostream> #include <cmath> #include <cstring> using namespace std; const int maxn = 1e6+10; typedef...

2020-02-27

0 607

LightOJ1220-Mysterious Bacteria 【唯一分解定理】

Mysterious Bacteria 题目意思就是给一个数x，现在要将它表示称次方形式，问最高能表示成多少次方？比如： 25 最高能表示成，它的次方形式表示最高是2次方分析这题最开始我写成了二分，按理说是可以过的，但是被WA飞了。好了，现在讲质因数分解做法。我们对N进行质因数分解的：那么如果...

唯一分解定理

2020-02-25

0 705

UVA11426-GCD - Extreme (II) 【欧拉函数】

GCD - Extreme (II) 题目题意很简单，就是给定一个N，让求出N范围内的所有gcd（i,j）的和，时限：10s 分析当我看见这题是时限我就觉得不简单，同时数据量N太大，都到4e6了。但是这题N范围内的答案都需要去求，因为这题没法在线处理，所以考虑暴力的优化。我们需要去枚举什么变量,...

欧拉函数打表

2020-02-25

1 1039

LightOJ1234 - Harmonic Number 【打表】

Harmonic Number 题目分析这题的打表比较有意思，一共有的计算量，这里有3秒的时限，是可以进行几次的的计算的，可是我们没办法开一个的数组来保存每一项的值，所以我们可以每隔50个打一个表，这样我们只需要进行一次的计算，之后次询问，每次我们只需要进行至多50次计算就可以了。 AC代...

打表

2020-02-25

1 779

UVA11752 The Super Powers 【暴力+数学】

The Super Powers 题目若x可以表示成两种及以上的幂形式，比如，被成为超级power数，现在让输出范围内的所有超级power数分析有限其实就是unsinged long long 的最大值,大概1e19，我们是无法通过直接暴力枚举的，那么就考虑下是否可以优化，题目说到至少要有2...

数学

2020-02-24

0 730

POJ2478-Farey Sequence 【欧拉函数】

Farey Sequence 题目 F2 = {1/2}F3 = {1/3, 1/2, 2/3}F4 = {1/4, 1/3, 1/2, 2/3, 3/4}F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}Fn表示分子分母小于等于n不可约的分数，之后...

欧拉函数

2020-02-24

0 675

LightOJ1213-Fantasy of a Summation 【快速幂】

Fantasy of a Summation 题意给你n,K,mod,让你计算上面代码的结果分析这题很明显不能直接暴力，而要从每个元素贡献方面着手，也就是算一下每个元素会被加多少次。举个例子以第二个样例为例：2 3 350001 2 1 2 1 2 1 2第二排的1，上面共有2条路径，下面...

快速幂

2020-02-24

0 623