Solution题意:无向图有n个点，从点1开始遍历，每次走两步，遍历整个图。问最少加几条边，可以完整的遍历整个图。 思路：首先可以想到的是如果图不连通，那么答案至少需要 (联通块的数目-1) 来把各个联通块连起来。而走两步的话，不难联想到奇偶形，考虑奇环的话两步可以到达环内任意一点，所以只要连通后的图有奇环存在，那么答案就是 (联通块的数目-1) ， 否则需要多一条边来构造奇环，则答案为 (联通块的数目)。 Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long ...

Solution题意:题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。范围：st 属于[1,10], 石头数量<=100, L<=1e9思路：很明显的dp题，dp[i]维护到达 i 点的最少步数：   但是要考虑到木板的范围高大 1e9 ，就需要离散化因为 st 范围较小，所以我们可以把[1,10]的公倍数求出来，2520，即只要距离超过了2520就可以由[1,10]构造出来。那么我们可以先对石头排序，然后求出他们相邻的距离，对2520取模，把数据压缩一下。在枚举的时候我们可以直接把离散后最后的一块石头当成终点，然...

Solution题意: 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰 ？：未告诉你本格情况 求满足条件的方案数。 思路： 考虑用 表示第 i 个字符 是/不是 火焰 以及 下一位是/不是 火焰的情况。因为前一位是 所以可以递推，然后只考虑下一位的情况。 eg:初始化：    结果,因为最后一位可以是1也可以是0：    ,前一位肯定不是火焰:   ,前一位是火焰下一位不是和 前一位不是下一位是：    ,前一位肯定是火焰: ,两种情况都要考虑：  ,所有情况都要考虑：...

  我正在学习课程《牛客算法竞赛入门班》，快来和我一起学习吧 https://www.nowcoder.com/courses/cover/live/368

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/stdc++.h>...

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 mod=1...

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 #define ll long...