数论——容斥原理。 从m种颜色中选出k种颜色给n个盒子上色，要求k种颜色都要用到且相邻盒子不能同色，求方法数。 首先，计算C(m,k)为选出k种颜色的方法数。 其次，k种颜色都要用到，换一句话说就是恰好用到k种颜色，显而易见应该转化为至少或者至多再考虑用容斥原理去重。记f(i)表示至多用i种颜色上色的方案数，容易得到f(i)=i* 。考虑对f(k)去重：最终方案数=至多用k种颜色方案数-至多用k-1种颜色方案数+至多用k-2种颜色方案数-至多用k-3种颜色方案数+...+(-)至多用1种颜色方案数。注意，其中用i种颜色的方案数，并不仅仅是f(i)，应该是C(k,i)*f(i)，因为要考虑至多用...

尺取法。 1.从第一个字符开始，向右移动右界至子串合法，用vis数组记录每个字母出现的次数，cnt表示vis记录次数为零的字母数。 2.当cnt=0时，此时每个字母都至少出现了一次，也就是说此时的长度就是一个合法子串的长度。更新ans。同时向右移动左界至子串不合法，移动过程中不断更新ans。返回第一步直至右界超过字符串长度。 3.输出ans。 代码： #include <iostream> #include <queue> #include <set> #include <map> #include <vector> #include...

插板条件：1.每个元素相同2.分成的组不为空 原始问题：将10个相同的球放到3个不同的篮子里，每个篮子至少有一个球，有多少种方法？用0代表球、-代表板子，则有：0-0-0-0-0-0-0-0-0-0，相邻两球之间插个板，共有9个板，我们只要从中选出两个板即可分成3个部分，也就是三个篮子。即C(9,2)。若将n个相同的球放到m个不同的篮子里，篮子不为空，则有C(n-1,m-1)种不同的方法。 变形1：将10个相同的球放到3个不同的篮子里，篮子可以为空，有多少种方法？因为篮子可以为空，所以不符合第二个条件。可以考虑加入三个球，按照原始问题的方法分成三个篮子后，每个篮子拿掉一个球，这样就考虑到了空篮...

解决问题：m次询问，每次给定一段区间，求静态区间kth。 考虑对每个点i建一棵权值线段树，维护1-i区间里的数出现的次数。例如给定6个数：1 3 2 3 6 1，第4棵树如下：n棵权值线段树形状一样，考虑对两棵树相减：第i棵树维护1-i区间里的数出现的次数，第j棵树维护1-j区间里的数出现的次数(i>j)，第i棵减第j棵则得到一棵新的权值线段树，维护j+1-i区间里的数出现的次数。这就是主席树的一个核心思想：前缀和思想。 现在看主席树的另一个核心思想：空间优化。建立n棵线段树需要的空间太大了，需要进行优化。观察每次添加新节点时树的变化，发现只有从某个叶子节点到根节点路径上的点的权值发生了...

动态规划。 原问题：n个木板粉刷t次的最多粉刷个数子问题：前i个木板刷j次的最多粉刷个数描述：记dp1[i][j]表示前i个木板刷j次的最多粉刷个数推出dp1[i][j]=max{dp1[i-1][j-k]+第i个板粉刷k次的最多粉刷个数},k<=j 这又产生了新问题，如何求某个板粉刷某次的最多个数呢？用第二层动态规划：原问题：某板整体粉刷k次的最多粉刷个数子问题：某板前j块刷k次得最多粉刷个数描述：记dp2[j][k]表示某板前j块刷k次得最多粉刷个数因为每次粉刷连续一段，所以考虑第j块时可以考虑从第j块前面的第l块一直刷到第j块，刷的颜色取决于这一段红蓝两色应刷的个数；预处理sum[...

动态规划。 首先，题目说不限操作次数，但其实只要操作一次即可，因为每次操作得到的两堆重量差值均<=m，只要将每次得到的两堆按大小互补的方式与前一次的两堆合并到一起即可，最后相当于得到一次操作的结果。 其次，动态规划。原问题：从n个物品中选出两堆重量差不超过m时最大重量和。子问题：从前i个物品选出两堆重量差不超过j时最大重量和。描述：记dp[i][j]表示从前i个物品选出两堆重量差不超过j时最大重量和。分析状态之间的关系，对于第i个物品，有如下几种可能的情况：不选取，dp[i][j]=dp[i-1][j];加在大堆，dp[i][j]=dp[i-1][j-ar[i]]+ar[i];加在小堆，...

状态压缩动态规划，即状压dp，是利用二进制表示状态的一种dp。根据题意，标记为1的土地只有有人(1)和无人(0)两种状态，所以状压显而易见。 记dp[i][j]表示第i行状态为j的方案数，初始化dp[0][0]=1；同时采用二进制数ar[i]记录第i行的土地状态。首先，对于每一行i，状态j必须是合法的，得到((j|ar[i])==ar[i])&&(j&(j>>1)==0)，因为方案不能与土地冲突，同时同一行相邻的两个不能同时为1。其次，考虑第i-1行状态k转移到第i行状态j，得到(j&k)==0，因为同一列相邻两个不能同时为1，求得转移方程：dp[i...

树上dp。记low1[u]为从u向下搜索到的最大路径值加起点值，low2[u]为从u向下搜索到的次大路径值加起点值。考虑非叶子节点u及以其为根的子树：若u为端点，则ans=max(ans,low1[u]+weight[u])；若u不为端点，则ans=max(ans,low1[u]+low2[u])。 对于dfs遍历到的每个非叶子节点都以此更新ans的值；对于叶子节点则令low1[u]=weight[u]，low2[u]=-inf，因为同一段路径不能经过两次。 代码： #include <iostream> #include <queue> #include <se...

前向星是一种特殊的边集数组。不同于邻接表和邻接矩阵对顶点的处理，前向星存图处理的是边与边的关系。 int cnt; //记录边的编号 int head[maxn]; //head[u]表示上一个以u为起点的边的编号，初始化-1 struct st //储存边的信息 { int to; //边的终点 int w; //边的权值 int next; //下一个同起点边的编号 } edge[maxn];这里再解释一下head数组和edge数组: edge[i]并不是表示第i个顶点，而是编号为i的边，edge结构体不包含边的起点，但包含了与该边同起点的边的编号。 head[u]记录最后一条以u为起点的...

题意：给定一棵带权树和它的根，要求删除一些边使得叶子节点无法到达根节点，求删除边的权值之和的最小值。思路：树型dp，其本质为搜索，即遍历树并在返回时维护相关的值。将原树拆分成以其孩子为根的多个子树，对于一棵子树有两种情况：1.删除子树的根与其双亲相连的边。2.删除子树的边。只要对这两种情况取最小值再回代即可。代码： #include <iostream> #include <queue> #include <set> #include <map> #include <vector> #include <stack> #in...

题意：给定两个字符串a和b，从a和b中选取若干元素，不改变其在原字符串中的顺序，求能够形成的回文串的最大长度。思路：区间dp。用dp[i][j][k][l]表示从a串选取第i个到第j个元素，从b串选取第k个到第l个元素，这些元素能否形成回文串。可以这样考虑回文串的形成：一个回文串在两边加上相同的字符形成一个新的回文串。因为要求不改变字符在原串的顺序，所以两边加上的字符有以下几种可能： a[i]-a[j] a[i]-b[l] b[k]-a[j] b[k]-b[l]；得到以下状态转移方程：dp[i][j][k][l]|=(a[i]==a[j])&&dp[i+1][j-1][k][l...

题意：给定一个长度为n的序列和长度为k的窗口，求每次窗口滑动时窗口内元素的最大值和最小值。思路：经典的单调队列题目，这里采用双端队列处理，维护单调非递增(/减)队列考虑求最小值：若ar[i]小于等于队尾元素，则不断弹出队尾元素，因为ar[i]比它们有更大的发展空间；将ar[i]入队，因为当队首元素不断弹出时，其有可能成为最小值；若队首元素离开窗口则弹出；输出队首元素。最大值情况同理。代码： #include <iostream> #include <queue> #include <set> #include <map> #include &lt...

题意：给定一个长度为n的序列，选取两个不相交且长度为k的区间，求两个区间的元素之和的最大值。思路：记sum_right[i]为以i为右界且长度为k的区间内元素和，记left_max[i]为左界大于等于i的所有区间元素和的最大值。一趟遍历可求出sum_right，再利用其求出left_max，最后求得ans=max{sum_right[i]+left_max[i+1]};代码： #include <iostream> #include <queue> #include <set> #include <map> #include <vector...

题意：有n个士兵，每个士兵 i 有武力值v[i]和限制人数s[i]，即：若选择了第 i 个士兵则选择的总人数不能超过s[i]。求v[i]总和的最大值。 思路：贪心，优先队列。按s[i]从大到小的顺序进行排序并遍历，对于每项v[i]直接入队。若size<=s[i]直接更新ans；若size>s[i]则最小项出队后更新ans。此方案确保将v[i]足够大的留在队列中，同时也考虑到了v[i]大而s[i]小的情况。 代码： #include <iostream> #include <queue> #include <set> #include <ma...