Solution安利一下我的线性dp博客：https://blog.csdn.net/JiangHxin/article/details/105184169一般情况下，动态规划的解题步骤是：第一步：根据原问题和子问题来确定状态（dp数组表示什么东西）第二步：根据状态确定状态转移方程（怎样求解dp数组 递推?dfs?）第三步：确定要不要优化和编程实现方式 （单调队列?线段树?） 而字符串的话：像回文串： 为字符串 的第 i 个字符到第 j 个字符的最长回文子序列长度。特殊的： 一般的： 即两个串的匹配可以用来表示s1的前 i 个字符与s2的前 j 个字符的最大匹配。但是这道...

Solution题意：给出一个数列，针对每个L,R,X 的区间求 [ L, R ] 中小于等于 x 的个数。 区间 个数 很容易想到树状数组来维护考虑 离线处理问题pair 存储数列的元素内容和索引 然后按照从小到大排序然后再对 存储询问的结构体 按 x 的值 从小到大排序 以上的前戏做完，就可以计算每个区间的答案了：遍历 pair ， 因为 pair 中的元素是递增的 且 结构体也是按 x 递增的 ， 所以前一个询问的答案也是后一个询问的答案一部分， 依次遍历 单点更新 区间求和。 Code #include<bits/stdc++.h> #define mp make_pair...

Solution题意：给出m道菜，有a,b,c属性，美味值是a-b*c,求T时间能制作出菜肴的最大价值和。 规定条件范围内的最大价值和/方案数，妥妥背包~跟国王游戏很像，每道菜的价值跟选取的顺序有关，所以要预处理出每道菜的顺序。考虑任意两道菜x和y的价值： x煮完后再煮y : y煮完后再煮x : 由于a属性与选取顺序无关，所以考虑 bc属性即可若情况1的价值更大，移向有： 所以以此为 cmp 排序即可。然后还要注意答案可能是负数，所以dp初始化为-1e18设 保证答案一定是由0开始转移的，最后 ans 取 max 即可。 Code #include<bits...

Solution题意：给出n个元素，每个元素不大于k，求 删除m个元素后的子序列个数。 子序列问题，通常可以联想到dp来做，考虑 维护 前 i 个元素删除 j 个元素的方案数，考虑第 i 个元素删或者不删，即有： 但是这样计算的话肯定会有重复的方案，拿样例2来说：4 2 21 2 1 2删除第一个元素和删除第二个元素 得到 1 2删除第三个元素和删除第四个元素 得到 1 2删除第二个元素和删除第三个元素 也得到 1 2这样就重复了。 如何计算重复的子序列？就像求路径一样，如果经过同一个点两次可以说明这条路已经走过了。那么如果 a[i]在 i 之前出现过，设距离 i 最近的一个下标为x，就有...

Solution题意：给定一个无向图，有一些边已经染色，求让你染色剩下的边使得每个环的异或和都为0的方案数。 好难想!好难想!好难想!重要的事情要说三遍! 1.思维点：题解很巧妙，把对边染色转移到对点染色，取边为两个端点的xor，这样的话每个环的异或和肯定为0，因为每个点都xor了两次~ 2.答案的贡献： 考虑一个联通块里面没有边被染色，那么每个点都有染成 0/1 的选择，设cnt为联通块中的点数目，那么可以考虑成 2^cnt， 但是想一下，因为是算边的染色方案而不是点的染色方案，如果对所有点取反，边权不变，所以每个联通块对答案的贡献为： 2^(cnt-1) 。 再考虑已经有x条边被...

Solution题意：求满足条件的子序列个数之和。 条件： 朴素做法1： 时间复杂度: 直接暴力枚举即可，关注点在于如何判断 直接计算可能会出现 100^100 这样是无法操作的考虑取对数，有 剩下的以 dp[i]维护 以i为结尾满足条件的子序列方案枚举更新即可 树状数组优化做法2： 时间复杂度: 考虑取对数，有 这样每项有 i 和 j 两个变量，所以只能暴力但是如果 移项的话有 : 这样的话 只跟 i 有关，所以只需要计算前面比小的个数即可不难想到求比自己小的个数就是树状数组维护偏序的套路 Code //做法2: const int mo=998244353; const int m...

Solution题意：B的元素取 对于A的每个长度大于k的子区间取第k大元素，求B的第m大元素。 知识点：二分 首先由于数据过大，枚举区间肯定不行，在题解中有一句话非常好：考虑把求值变成验证。求第m大元素，即判断第k大元素比m大的区间数是否>=m。想到二分，但是不会计算区间数就很尴尬，还是很佩服大佬们，自己看了题解才想清楚。用双指针求区间数，当一个区间满足mid为第k大时，左边界为l，右边界为[r,n]，所以这个区间对答案的贡献为 n-r+1最后判断的时候如果ans>=m即说明mid小了所以指针右移，反之指针左移。 Code #include<bits/stdc++.h&gt...

Solution 知识点：枚举/暴力+前缀和+思维 因为只要在队列后面出现能力值大于自己的能力值且与自己不是同一个阵营的自己就会去世，加上前 i-1 秒发功增加的能力值不会影响第 i 秒，所以可以考虑一下倒着遍历 n 秒，边枚举边更新最后面的最大值，这样的话复杂度最坏情况是，考虑用前缀和优化把能力值加在每个能力者这一过程，可以达到。 Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #pragma GCC optimize(2) #define io...

Solution二分答案模板题。先给出俺的万能二分模板： (ans为答案且注意初始化为0，其他只要改一下check函数就可以用于其他题) ll l=1,r=max,ans=0; while(l<=r){ ll mid=l+r>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; }这道题的话就是直接枚举木棍的长度，然后判断切出的数目是否大于等于k。 Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #de...

Solution取任意两点，一者为0，一者为1，其他任意排列，则： 由于取模，所以有两种选择：1.逆元2.预处理由于组合数比较小，所以选择了预处理。Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; inline ll read(){ll s=0,w=1;char ch=getc...

Solution记得寒假牛客有道题就是这道题的扩展，好像是求路径数目+博弈论。 表示以 i 为根的子树到 i 的距离为偶数/奇数的数目。那么在dfs过程中，以 u 为根且子结点为 v 对答案的贡献是: (子结点与父节点距离相差1，所以应操作不同奇偶性)当然遍历完也需要把 v 的路径数合并到 u里面去: Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin...

Solution前缀和优化，用维护的区间异或和，那么的区间异或和即。那么遍历 i ，枚举 i 作为右端点统计区间异或和，再枚举 i+1 为左端点统计答案。关键点在于左边区间统计，右边区间更新而不统计，保证区间不重叠。 Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; inlin...

Solutionemm昨天看了但是没有写出来，因为不会处理回溯过程中的更有利涂黑的情况。题解很巧妙，没想到可以用另外一个数组d来记录可以最多涂黑到哪个点，当数组d为0时就代表需要多操作一次，而这个更新操作次数正是这道题的灵魂所在。简单来说就是： 更新回溯过程中最远可到达的距离 更新回溯过程中无须操作就可到达的距离而当为0时就代表需要多花一次操作次数。 Code #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define inf 0x3f3f3f3f #define m...

A.Solution因为是非递减数列，所以只移动k位是最佳的，那么对于原数列的美丽值来说移动k位所造成的变化是增加了 而减少了，所以遍历大于k的部分， =，那遍历取max即可。Code #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define inf 0x3f3f3f3f using namespace std; inline ll read(){ll s=0,w=1;char ch=getchar(); while(ch&...