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

1549：最大数  向序列后添加一个数，序列长度变成 n+1 单点修改，把n+1这个位置上的点（初始化为0）修改为添加那个数的值 询问操作：询问这个序列中最后 L 个数中最大的数是多少 区间查询[n - L + 1,n],维护一个属性最大值v  代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define i...

D：GCD  集合 S 包含 1 至 n 所有的数 从集合S中找任意找子集T(T中包含k个数)，都存在(存在任意两个数x,y),满足gcd(x,y) > 1 求最小k  题目分析：  最小k：最坏情况选择k个数满足条件 素数满足两两互质、1与任何数都互质，gcd(a,b) = 1不满足gcd(x,y)>1，都要加上 素数和1选择完毕，需要加上一个合数，这样就满足条件 最小k：把(1~n)中所有素数筛选出来，加上1和一个合数 k不存在的情况是：k > n，没有k个数可以选  代码如下： #include<bits/stdc++.h> using namespace ...

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 ll long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define lowbit(x) (x) & (-x) /* */ const int N = 3010; int n; int a[N],b[N]; int ...

187. 导弹防御系统 代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define lowbit(x) (x) & (-x) /* 最少的最长上升子序列个数 + 最少的最长下降子序列个数 求解：枚举(0,n - 1):dfs(u,su,sd) */ co...

P1020 导弹拦截 第一问：以后每一发炮弹都不能高于前一发的高度  求最长不上升子序列长度，不再概述  第二问：拦截所有导弹最少要配备多少套这种导弹拦截系统(最少需要几个最长不上升子序列) 法一：贪心  从前往后遍历，取该值x,cnt表示子序列个数 遍历所有（0~cnt-1）子序列，如果x大于当前子序列的最小值，就取找下一个子序列 把该值放到当前位置k 当前位置为cnt，那就需要新开一个序列  int cnt = 0; for(int i = 0; i < n; i ++ ){ int k = 0; while(k < cnt && g[k] < a[i])...

E-牛牛的加法  模拟加法运算，需要进1的时候，不进位 注意去掉前导0  代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define lowbit(x) (x) & (-x) string a,b; vector<int > A,B; vec...

C-滑板上楼梯  由于跳三阶特别累，所以他不能连续跳三阶 那么就需要313131……这样交叉着跳，跳4阶，共两次 刚好是4的倍数那么就需要n / 4 * 2次 多一层或者两层，就需要再跳一次一阶或两次一阶,，+1或者+ 1 * 2 多三层，直接跳三阶，+1  代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #d...

1285：最大上升子序列和  最长上升子序列的长度转换为最大上升子序列的和  代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define lowbit(x) (x) & (-x) const int N = 1010; int n; int a[N]; ...

1263:友好城市    北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同 在保证任意两条航线不相交的情况下，被批准的申请尽量多题目分析： 如图：最开始所有点为图1这种情况，我们需要处理不相交 那么转换为图2，需要先把第一列数从小到大排列 为了求得最多的情况，求第二列数的最长上升子序列（保证这列坐标从小到大，这样就不相交）  代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll...

P1091 合唱队形  求N-K的最小值，转换为求k的最大值 与登山类似  代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define lowbit(x) (x) & (-x) const int N = 1010; int t,n; int a[N];...

1283：登山  每次所浏览景点的编号都要大于前一个浏览景点的编号 不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了  题目分析：  先登山后下山（不上山你怎么下山？） 登山：求（1~n）的最长上升子序列 下山：求（n~1）的最长上升子序列 总路长为s上山+s下山-1  代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<i...

1286：怪盗基德的滑翔翼  初始时，可以选择任意一个点进行下降，可以选择一个方向逃跑（线性：左或者右），中途不改变方向 求(1~n)：以a[i]结尾的最长上升子序列 求(n~1): 以a[i]结尾的最长上升子序列 最后，取最大值  代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #define pii pair<int,int> #define inf 0x3...

G-滑板比赛  双指针 牛牛的动作n>=m，所以要对牛妹的m个动作进行分析 首先，对它们的华丽值进行从小到大排序， 然后，从大到小去枚举m个动作 i表示牛妹第i个动作，j表示牛牛第j个动作 若牛牛的华丽值小于或者等于牛妹的华丽值，这个动作不进行操作 否则，进行比较，赢一次(ans ++)，进行下一个动作的比较（j --）  #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long long #def...