A 夹娃娃 求一下前缀和，即可 回答询问。整体复杂度 。 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, k, a[N]; int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i] += a[i - 1]; } while(k--) { int ...

题意： 给定一个 的矩阵，从中选出 个互不重叠的子矩阵，使得总分值最大。 其中 。 题解： 注意到 。 先考虑 的情况，是一个比较经典的最大 子段和问题，可以用 求解，复杂度为 。具体做法这里就不说了。 再考虑 的情况，由 的求解做法接着往下考虑。子矩阵可以是第一列的连续行，或者第二列的连续行，或者两列的连续行。 因此可以设计 状态： 表示第一列 行，第二列 行，其中选取了 个子矩阵的最大和。 注意这里并不包含第一列以 为结尾，第二列以 为结尾，即 必选。 那么不选取以 或 不选 的转移为： 选择一个以 为结尾的子矩阵的转移为： 选择一个以 结尾的子矩阵...

题意： 给定一棵 个节点的树，初始选择节点 ，之后每次选择可以取一个之前未选择的且不与之前选择的节点相邻的节点，问最多可以取多少个节点？ 题解： 树形 。 初始节点 ，当作树的根。那么之后每次节点选择，都是在已选择节点的子节点树中进行选择。我们可以尝试把这个过程倒过来，由子节点对应的子树选择的结果来决定当前节点对应的子树的选择。这样就是经典的树形 了。 如果选择了某一个节点，由题意知它所对应的子节点都不能选。那么可以设计 状态： 表示节点 是否选择 的情况下，以 为根的子树可以选择的最多的节点数。 表示选， 表示不选。 可以列出 方程： 为 的子节点。在 选取的情况...

题意： 给定 ，其中 。求有多个 ，满足 。 题解： 需要一些简单的数论知识： 费马小定理：若 为质数，而整数 不是 的倍数，则 。 逆元：定义整数 在模 意义下的逆元为 ，则 ，可记作 。在 条件下，有 。因为 。 然后到这道题：首先由 费马小定理 可以得到 ，因此可以设 。然后推式子： 由于 ，范围为 。故可以枚举 ，通过上式计算 。需要用到快速幂，一次计算的复杂度在 级别。整体估计复杂度是可以通过的。 在已知 的情况下，我们根据这个式子可以求出一个 ，显然任意 ，即 ，都有： 时 。 有限制条件： 。对于一个确定的 ，我们要求的就是有多少个整数 ，使得 ...

题意： 支队伍一共参加了三场比赛。一支队伍 认为自己比另一支队伍 强当且仅当 在至少一场比赛中比 的排名高。 求有多少组，使得 自己觉得比 强， 自己也觉得比 强。 算一组。 解法： 题目应该是有个没有显式声明的条件：一场比赛种不存在两支队伍排名相同。如果加上这个条件，也能做，处理一下这种情况即可。 第一点：考虑符合要求的队伍 和 三场比赛的排名。显然只有两种情况： 出现两次， 出现一次；或者 出现两次， 出现一次；那么我们从中任取两场比赛，对满足 和 各出现一次的做统计，结果数即为 。那么最终答案就是 。 因为同一对满足条件的 ，两种情况都是重复统计一次。 第二点：考虑...

题意： 有上下两个管道，上管道有 个球，下管道有 个球，每次可以从上管道或者下管道末尾取出一个球。对每种最终取出的小球序列统计方案数。记不同的序列数为 ，第 种序列的方案数为 。显然有 。 需要你来计算 ，结果对 取模。 数据范围: 解法： 关键点：需要将求和式中的平方转化出来：视为两个相同的管道系统，独立取出小球，最终序列相同的方案数。 第 种序列方案数为 ，那么第一个和第二个均有 种方案，那么两者相同的方案数就是 。 对于类似的 次方，均可以按照这个思路转化一下。 视为两个系统取出小球，dp 求解就比较显然了。 表示两者都取出了 个小球，前者取出了上管道的 个小球，后...

题意： 有 头奶牛在践踏花田，第 头牛每分钟会毁坏 朵花，把第 头牛关进栅栏里需要 分钟。关进栅栏的过程中，不会毁坏花朵。同一时间只能处理一头牛，问怎样安排可以使得被毁坏的花朵数目最少。 题解： 贪心。比较典型的贪心题目。因为同一时间只能处理同一头牛，所以我们只需要确定顺序即可。确定顺序再结合求最小，就可以想想是不是贪心。 对于这类题：可以通过比较第 个和第 个，或者比较第 头牛或者第 个，怎样的顺序会更优。即确定一个偏序关系。 这里比较一下第 个和第 个的顺序。 和 这两部分的毁坏花朵数数与 和 的顺序无关。记前 头牛处理完的时间为 。那么若 排在 前面...

题意： 有 种面值的货币，第 种货币面值为 。这组货币组成的货币系统定义为 。求与 等价的货币系统 中，最小的 。 两个货币系统等价定义为：任意面额 ，要么均不能被两个货币系统表示出来，要么均能被表示出来。 题解： 考虑 中会存在哪些数：考虑某个面额 ：若 不能被表示出来，那么 中肯定没有这个元素。若 能被表示出来，那么这个元素必然是由 中其它元素表示出来的，所以删掉也不影响系统的表示能力，而且货币数更少。 因此 中的元素必然是 的一个子集。若 ：考虑 是否能由其它元素表示出来，若不能，那么 中必须要保留这个元素。若能，则可以去掉这个元素。 那么我们要做的就是考虑 ...

题意： 个建筑，每个建筑有完成的持续时间 ，以及截止时间 。同一时间只能抢修一个建筑，每个建筑需要在截止时间前完工，否则就报废。问最多能有多少建筑抢修成功。 题解： 贪心。先按截止时间排序。然后顺序抢修，能抢修成功的则抢修。同时维护一个优先队列/堆，堆里存放抢修成功的建筑的持续时间。当不能抢修成功的时候，比较当前建筑的持续时间与堆顶元素（最大值），若当前值更小，则替换之。 Code: #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; using ll = long long; struct N...

题意： 给出 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 。 题解： 先考虑一段区间中位数为 有什么性质：这一段区间内大于 的数和小于 的数一样多，并且包含 。然后做一个简单的转化，大于 的数记为 ，小于 的数即为 。那么中位数为 的区间就有： 区间包含 所在的位置 ，即区间 满足 。 转化后的区间和为 0。 求区间和为 的数量有一个常用的技巧：前缀和。区间 和为 ，等价于区间 的和与区间 的和相等，即前缀和 。然后用一个 map<int, int> 保存前缀和为某个值对应的数量。这样从左至右遍历统计就可以了。 这道题还有和包含位置...

题意： 给定无权双向图，顶点数为 ，边数为 。从顶点 开始遍历，每次“走两步”。问最少需要添加多少条边，可以走遍整个图。 解法： 先考虑连通块内的情况： 对顶点进行黑白染色，那么和顶点 颜色相同的点，都可以直接通过原图中的边走到。 然后再考虑从某个点如何“走两步”走到另一个颜色不同的点：若某个顶点的邻接顶点中包含颜色不同的点，那么就可以以这个顶点作为“两步”的中间点，从而做到从一个颜色“走到”另一个颜色。 如果不存在呢？显然必然存在一种颜色的顶点数 ，且存在一条边的两端顶点颜色不一致。那么只需要加一条边，就可以满足上面的情况，及可以走遍整个图。假设颜色1的顶点数 ，某条边两端顶点为 ，颜色...

题意： 给定 个整数对 ，问存在多少个 满足 ： ，其中 。 题解： 先对数对按 排序，那么对于 ，会有 。因此，对于，我们只需要考虑是否存在。这样我们逆序遍历，维护一个后缀最大的 值，即可判断 是否满足条件。 Code： #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; struct Node { int a, b; Node() { } bool operator < (const Node &t) const { return...

题意： 一共有 个数，第 个数是 。 可以取 中任意的一个值。设 ，求 种类数。 解法： 比较典型的分组背包问题：第 个数取 中的任一个值。 表示前 个数的平方和为 是否可行。初始化：转移方程： 复杂度为 。由于 这一行的值仅与 有关。故可以优化空间，第一维大小为 ，即仅保存上一行的值，交替更新。这样常数也会小一些。再使用 压位，可以优化为 。 可以视作一个一维数组，第位对应对应平方和为 是否可行，对应位为 。转移则可以使用移位实现 。 Code： #include <bits/stdc++.h> using namespace std; const i...

题意： 比赛中有 道题。对于第 道题，你有 的概率自己解出来，有 的概率从左边队伍听到题解，有 的概率从右边的队伍听到题解。问解出 道题的概率各是多少？ 解法： 枚举对于第 道题，最终能解出来的概率为 。然后二进制枚举每道题是/否解出来，计算对应情况的概率，加到对应题数复杂度为 dp 表示前 个问题，解出 个的概率。 初始化 转移方程为： Code： 枚举 #include <bits/stdc++.h> using namespace std; double a[12], b[12], c[12], p[12], ans[13]; int main()...