C 我们先定义两种计算：  前向，即给出 ，计算 这个序列的和，其中序列长为 。 反向，即给出 ，计算 这个序列的和，其中序列长为 。  然后我们可以把新牌堆分拆成上下两部分：下面 张牌，上面 张牌，分别计算这两个部分对答案的贡献。 先分析下面 张牌的成分。一开始做了 次操作后，原牌堆自底向上变成： 其中 。 然后下面的 张牌中：  自底向上的第 张牌，对应原牌堆自底向上的第 张牌。 自底向上的第 张牌，对应原牌堆自顶向下的第 张牌。  那么如果要计算自底向上 区间的牌的和，可以换回到原牌堆求解。具体而言，结果就是前向计算 和后向计算 的和。如果要计算 的和可以用前缀和减一下。 再分析上面 张...

题意 给定一个 的矩阵，。求从矩阵中选出 个不相交小矩形，使得它们的权值和最大。 题解 先研究 的情况。显然这等价于经典的“最大 子段和”问题。可以在线性时间 内解决。  再研究 的情况。设 为前 行中选出了 个矩形可以得到的最大权值和。那么转移方程为 三个选项中取最大值。其中 表示第 列中，第 行到第 行之间的一段数的最大 子段和的值。这个可以在 时间内预处理得到。 初始条件为 时 。答案为 。 总的时间复杂度为 。应当可以优化到更低。 #include <bits/stdc++.h> using namespace std; int sumg[105] = {0}, sumh[...

题意 给定一个迷宫，迷宫中 A 可以向 8 个方向移动（八联通的 8 个方向），B 可以向 4 个方向移动（四联通的 4 个方向），但一单位时间可以移动两次。不能通过障碍物。问 A 和 B 是否能相遇、最早什么时候相遇。 题解 一开始理解错意思了，以为相遇必须是在某一时刻到达同一个格子。于是开始纠结 B 的“走两步”算一个还是半个时刻。 后来发现想多了，只要 A 和 B 都到达过某个格子就行了。那么直接上双向 BFS 即可。 #include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #define ...

题意 给定 种牌和每种的个数 ，给定 个王牌。有两种方案构成一套牌：   种牌各一张。  种牌各一张加上一张王牌。  问最多可以构成的套牌数目。 题解 一开始写了一个贪心，利用堆每次选择数目最少的种数，用王牌去补。然后超时了，因为 可以很大。 然后开了窍，写了一个二分。大概就是二分答案为 。设 ，表示对第 种牌，王牌补了多少张。那么首先要有 。其次要有 。 时间复杂度为 。可以通过一些技巧降掉一个 。 #include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #define MAXN 200005 ...

题意 一个 的方格，有的地方能放人，有的不能。人不能上下左右相邻放置。问放置方案总数。 题解 看到 这么小就知道是状压 DP。 以表示行的状态为例，设 为前 行处理完并且第 行的状态为 时的方案数目。那么只需要以行编号为阶段，内部枚举本行状态和上一行状态进行转移即可。 时间复杂度为 。 （注意非法状态的处理。） #include <bits/stdc++.h> #define INF 2000000000 #define MOD 100000000 #define MAXN 200005 #define REP(temp, init_val, end_val) for (int t...

题目大意 给定长为 的序列 ，设 。现在希望找到一个尽可能短的，设长为 的序列 使得 。求 。 题解 大概可以猜到 是 的子集。那么我们考虑一开始令 为空，然后不断往 中加入 的元素，且维持 尽量小。 那么加入的顺序必然是从小到大。当 中已有元素可以拼出 时就不加入 ，否则加入。“是否能拼出”可以用完全背包求出。 因此总的时间复杂度为 。 #include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #define MAXN 200005 #define REP(temp, init_val, end_...

题目大意 给定一个排列和 ， 在该排列中。求该排列的长为奇数且以 为中位数的子段个数。 题解 考虑将排列映射成另一个序列，某一位置上的数为 那么映射后这一位置上的数变为 。那么必然映射后的序列会有一个 。 问题转化为求新生成的序列中，包含这个 在内且子段和为 的子段个数。这个可以用前缀和比较简单的做到。 #include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #define MAXN 200005 #define REP(temp, init_val, end_val) for (int temp...

题目大意 略。 题解 由于每一个位置上的描述会涉及当前状态及相邻状态，用 表示**满足前 个字符的要求**，且当前位置状态为 ，后一个位置状态为 时的方案数目。则转移方程不难写出。 初始状态为 ，答案为 。 理论上只刻画当前状态和此前状态似乎也可以，但是讨论就很麻烦。 #include <bits/stdc++.h> #define INF 2000000000 #define M 1000000007 using namespace std; typedef long long ll; int read(){ int f = 1, x = 0; char c = getchar(...

题意 有 个数。 时刻开始时第 个数自增 ， 时刻结束时可以选中一个数让其自增或者自减 ，也可以什么都不做。求可能的最小时刻 ，使得 时刻结束后所有数相等。 题解 可以转化为对每一个位置 求其为结束位置时可能的最小时刻 。则 。 到位置 之前会跑若干轮，设轮数最小为 。则 。 设数列为 。分析可知只需要关注数之间的相对大小关系，那么对于每一个位置 ，实际上希望求解的是：找到一个 ，使得 全部通过自增/自减变成 的次数最小。 容易发现最优的 就是 的中位数。找到了 就可以算出这个最小的操作次数 。然后考虑至少需要几轮才能做完这些操作，由于需要 可以算出最少需要对这 个数跑 轮。 这样就做完了。维...

题意  个长为 的 01 序列，可以涂色 次。一次涂色涂一个序列的某一段（连续），获得的分数为这一段中 0 或者 1 的个数。一个位置不能重复涂。求最大分数。 题解 对每一序列暴力 DP 即可，可以算出每一序列涂 次的答案。于是可以转化为一个背包问题。时间复杂度为 。 #include <bits/stdc++.h> #define INF 2000000000 using namespace std; typedef long long ll; int read(){ int f = 1, x = 0; char c = getchar(); while(c < '0' |...

题目大意 给定长为 的序列，求其所有长度 的子区间的第 大数，所构成多重集的第 大数。 题解 二分。 现判定 。问题转化为求第 大数 的子区间个数，若其 则判定失败，否则判定成功。 如果将原始序列转化为一个 01 序列，某位置上为 表示原始序列上这个位置的数 ，否则为 ，那么区间个数就等于为该 01 序列中子区间和 的区间个数。这个显然是可以用尺取法计算的。 #include <bits/stdc++.h> #define INF 2000000000 using namespace std; typedef long long ll; int read(){ int f = 1,...

题目大意 略。 题解 容易想到按秒处理。发现前 个能力值加一可以转化为后面 个能力值减一。 于是维护到当前时间为止，当前位置及后面位置能力值被削减的量。之后就是简单的用两个堆处理一下即可。 #include <bits/stdc++.h> #define INF 2000000000 using namespace std; typedef long long ll; int read(){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = g...

题目描述 略。 题解 二分长度即可。 #include <bits/stdc++.h> #define INF 2000000000 using namespace std; typedef long long ll; int read(){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();} while(c >= '0' && c <= '9')x = x * 10 + c - '0', c ...

题目大意 求所有 长的 01 序列的逆序对数之和。 题解 一种方法是考虑所有 对，其中 。这必然产生一个逆序对。对于其他位置则没有要求，因此这个对的贡献为 。总共有 种这样的对，因此答案为 。 另一种方式是 DP。取 为长为 时的答案，则 。这似乎是一个可以求解的递归式，取 ，那么可以解出 。从而答案和上面相同。 #include <bits/stdc++.h> #define INF 2000000000 #define M 1000000007 using namespace std; typedef long long ll; int read(){ int f = 1, x...