I 九峰与分割序列 其他题目题解点击此处 思路 求一种分割方法使得所有子区间的贡献之和最大，我们设为到为止所有子区间的最大贡献和，为到为止最后最后一段区间长度大于k的所有贡献之和。 那么就会有动态转移方程： 上部分为不分割，因为只是加一倍的原来的那段区间和，那么它的值也就是相当于当前的值加上前面那一段，下部分为符合分割条件可以分割，就是取可以分割的区间乘以2加上前面那一段。 的状态转移好理解，就是让后面k + 1个数取一倍，剩下的数取最大即可。 继续优化，看能不能将dp的转移方程的第二个条件的给优化一下。因为它的长度永远都是只能小于等于的，所以可以想到滑动窗口，也就是单调队列。让单调队列...

D 温澈滢的狗狗 其他题目题解点击此处，持续更新…… 思路 这个题目看了我好久，，（主要是太菜了）做题的时候想到了用二分，但是不知道怎么去定义它的性质。两两不同颜色的狗之间会产生亲密度，对每一对有亲密度的狗按照关键词进行排序，求第k对狗的下标。如果模拟的话肯定会超时，所以要往快速找到第k对狗的方向想，会想到使用二分思想。想到用二分思想就要想能不能找到一个能够二分的条件。第一关键词是按照亲密度去的，所以想想能不能以亲密度去划分。我们假设第k对的亲密度为x，那么就说明 的部分是不需要的，所以就有明显的二分性。 知道了以亲密度作为判断条件，那么接下来的步骤就是完善细节，计算每个亲密度的个数。只有...

G 九峰与蛇形填数 其他题目题解点击此处，持续更新…… 思路 这个题目直接暴力就可以了，不需要用啥线段树。每个点每次取值肯定是最后一个覆盖到它区域的值，所以直接取那个数即可。然后还有一个细节就是剪枝，预处理区域的大小，如果这个点不在这个区域直接break。不用赋值了。 AC代码 #include<bits/stdc++.h> using namespace std; #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rep(i, a, b) for (int i = (a); i <= (b...

前言 其他题目题解点击此处，持续更新…… 思路 很明显的动态规划题目，但是我就是想不到，我想到以子序列为dp的目标，但是没有想到以字符串k为dp目标。多尝试不同的条件，说不定就能碰出火花，不能懒！ 记住，动态规划不是一步就达到答案的，是一步一步转化之后才到达答案的。 表示前i个定序列匹配到字符串k第j位的所有合法方案， 所以分为取和不取两种选择，这就类似于01背包了，但是比01背包多了一个点就是取之前需要判断它是否能拼接成字符串k。 所以状态转移方程为 ： 利用滚动数组，将状态转移方程进一步转化为 ： 使用之前的值，所以别忘记了是逆序遍历。 AC代码 #include<bits/...

A｜B 反思：这个题目分类讨论没有到位，我只是讨论了首位为零的情况，其他位为零的情况没有考虑到。题目思路：将题目意思抽象出来，就是求1的所有符合条件1的摆放位置。 代码 #include<bits/stdc++.h> using namespace std; int main() { #ifdef LOCAL freopen("data.in", "r", stdin); #endif int T; scanf("%d", &T); while (T--) { ...

A｜B 反思：这个题目分类讨论没有到位，我只是讨论了首位为零的情况，其他位为零的情况没有考虑到。题目思路：将题目意思抽象出来，就是求1的所有符合条件1的摆放位置。 代码 #include<bits/stdc++.h> using namespace std; int main() { #ifdef LOCAL freopen("data.in", "r", stdin); #endif int T; scanf("%d", &T); while (T--) { ...

这个base怎么求得的？