题意维护一个长度为$n$的序列，一开始都是$0$，支持以下两种操作：$U \ k \ a$ 将序列中第$k$个数修改为$a$$Z \ c \ s$ 在这个序列上，每次选出$c$个正数，并将它们都减去$1$，询问能否进行$s$次操作每次询问独立，即每次询问不会对序列进行修改数据范围：$1 \le n,m \le 1000000$题解对于一个询问，记$\ge s$的数有$x$个，$< s$...

题意从$1$开始，跳到比当前矮的不消耗体力，否则消耗$1$点体力，每次询问有一个步伐限制，求每次最少耗费多少体力数据范围：$2 \le n \le 1000000$题解用$f[i]$表示前$i$个的步数，易得状态转移方程$$ f[i]=\min_{j=i-k}^{i-1}\left\{ \begin{aligned} &f[j] &a[j] > a[i]...

题意给出两$n \times m$的矩阵，保证每个矩阵内元素互不相同且权值均在$[-10^6,10^6]$之间，请能否把其中一个矩阵通过若干次交换两行或者交换两列的操作变成另外一个矩阵数据范围：$1\le n,m \le 1000$题解结论：任何一行/列中的元素不会变暴力判断即可代码：#include<iostream> #include<cstdio> #inclu...

题意有$n$个数，可以进行$k$次操作，每次操作可以选择一个区间让每个数$+1$，求最后最长不下降子序列长度数据范围：$1 \le n \le 10000,1\le k \le 500$题解首先明确一个事实：每次操作的区间的右端点一定是$n$容易证明：这样不会使答案变小，并且如果不这样可能会使答案变小用$f[i][j]$表示第$i$个数已经被操作了$j$次，当前的答案，状态转移方程为$$f[...

题意树上操作$u$到$v$的路径上权值$+1$询问每个点的权值数据范围：$2 \le n \le 300000$题解树剖裸题注意每次的终点作为下次的起点，会多$+1$，记得$-1$；最后一次也是，题目有特殊要求代码：#include<iostream> #include<cstdio> using namespace std; #define ls rt<<...

题意有$n$头奶牛，$m$条约束$(a_i,b_i)$，表示$a_i$到$b_i$间有且仅有一头带斑点的奶牛，求最多可能有多少只斑点奶牛数据范围：$1 \le n \le 200000,1 \le m \le 100000$题解将有且仅有一头拆解为至多一头+至少一头初步思路为差分约束，但明显复杂度过高发现可以$dp$，用$f[i]$表示第$i$头奶牛有斑点的情况下前$i$头奶牛最多有多少斑点...

题意给出$n$个数，从中选出一些，求选出的数能分成相等的两份的方案数数据范围：$2 \le n \le 20$题解对于每个元素，无非$3$种状态：$0$ 不选$-1$ 左$1$ 右但直接搜索复杂度达到$O(3^n)$考虑折半搜索将组合二进制压缩，前半搜索记录下可能的$sum$，后半搜索从前半中找到相等的$sum$（其实是找$-sum$，但是是等价的），则此种选择方案成立由于$sum$较大，需...