chstor

分类

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

/ 注册

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

2篇文章 0人学习

全部文章（共262篇）

P1049 装箱问题（01背包）

P1049 装箱问题要使得箱子的剩余空间最小，所占空间需要最大值问题转换为：任取若干个装入箱内，占用最大空间每个物品价值和体积都为v #include<iostream> #include<algorithm> using namespace std; con...

2020-12-14

0 477

P1048 采药（01背包）

P1048 采药法一：未优化空间，时间、空间复杂度均为O(NM) #include<iostream> using namespace std; const int N = 1010; /* 状态表示：f[i][j]表示取前i个草药，时间为j的最大价值状态转移： ...

2020-12-14

0 568

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 571

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 563

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 459

1549：最大数

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

2020-12-09

0 521

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 522

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 395

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 522

P1020 导弹拦截

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

2020-12-07

0 489