Doran_dinosaur

分类

BFS(10) DFS(4) 二分答案(10) 前缀和(2) 排序算法(1) 树状数组(1) 模拟(1) 线性DP(8) 线段树(3) 背包DP(3) 蓝桥杯(4) 题解(13)

/ 注册

TA的专栏 2篇文章 0人订阅

2篇文章 879人学习

全部文章（共260篇）

interval GCD

interval GCD 题目分析: 把 A[l],A[l+1],…,A[r] 都加上 d 利用差分改变区间[l,r]的值a[l] += d,a[r + 1] -= d 询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD) 根据辗转相除法，gcd(a,b) = gcd(b...

2020-12-11

0 578

B-最好的宝石

B-最好的宝石询问区间[l,r]内宝石的最大价值，和最大价值的宝石有多少个在最大值上新添加一个属性区间最大值相同的个数cnt，建树的时候初始化cnt = 1（自身：区间[x,x]，cnt为1） tr[u].cnt = 0; if(tr[u].v == tr[u <<...

2020-12-09

0 568

Can you answer these queries III

Can you answer these queries III 区间查询，查询区间 [x,y] 中的最大连续子段和单点修改，A[x] 改成 y 维护三个属性lmax前缀最大和，rmax后缀最大和，tmax最大连续子段和，sum整段和 u.sum = l.sum + r.sum;//父节点整段...

2020-12-09

0 462

1549：最大数

1549：最大数向序列后添加一个数，序列长度变成 n+1 单点修改，把n+1这个位置上的点（初始化为0）修改为添加那个数的值询问操作：询问这个序列中最后 L 个数中最大的数是多少区间查询[n - L + 1,n],维护一个属性最大值v 代码如下： #include<bits/stdc...

2020-12-09

0 522

D：GCD

D：GCD 集合 S 包含 1 至 n 所有的数从集合S中找任意找子集T(T中包含k个数)，都存在(存在任意两个数x,y),满足gcd(x,y) > 1 求最小k 题目分析：最小k：最坏情况选择k个数满足条件素数满足两两互质、1与任何数都互质，gcd(a,b) = 1不满足gcd(...

2020-12-08

0 525

LCIS：最长公共上升子序列

LCIS：最长公共上升子序列法一：时间复杂度O(n^3) #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define...

2020-12-08

0 403

187. 导弹防御系统

187. 导弹防御系统代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long lon...

2020-12-07

0 527

P1020 导弹拦截

P1020 导弹拦截第一问：以后每一发炮弹都不能高于前一发的高度求最长不上升子序列长度，不再概述第二问：拦截所有导弹最少要配备多少套这种导弹拦截系统(最少需要几个最长不上升子序列) 法一：贪心从前往后遍历，取该值x,cnt表示子序列个数遍历所有（0~cnt-1）子序列，如果x大于当前...

2020-12-07

0 494

E-牛牛的加法

E-牛牛的加法模拟加法运算，需要进1的时候，不进位注意去掉前导0 代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make...

2020-12-07

1 545

C-滑板上楼梯

C-滑板上楼梯由于跳三阶特别累，所以他不能连续跳三阶那么就需要313131……这样交叉着跳，跳4阶，共两次刚好是4的倍数那么就需要n / 4 * 2次多一层或者两层，就需要再跳一次一阶或两次一阶,，+1或者+ 1 * 2 多三层，直接跳三阶，+1 代码如下： #include<bi...

2020-12-07

0 604