题意： 给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。 思路：树形dp：从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。sum[i]表示以i为根的树使得删后的图每个连通块大小小于等于k的总方案数。sz[i]表示以i为根的树的节点数。当儿子v向父亲u转移时有两种情况：①父子节点在同一连通块：dp[u][i+j]+=dp[u][i]*dp[v][j];①父子节点不在同一连通块：dp[u][i]=dp[u][i] * sum[v...

题意：有一个n*m的矩阵，你可以进行k回合的游戏，每一回合将矩阵的一行或者一列的值置零并将分数加上。求你最后最多能得多少分？ 思路：由于消除行对列有影响，所以不能简单的贪心，但你n和m小于15，所以我可以枚举消除列的状态，然后对每一种合理状态再对行进行贪心操作，然后取最大分数值。 代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace std; inline int read() { int x=0,f=1; char ch=getchar()...

题意：在一个m*n的教室中，有D对交头接耳的同学，你可以用k行l列隔开，问怎么隔开上课时交头接耳的学生对数最少？ 思路：我们可以发现列和行之间没有联系，所以行列分别单纯贪心从最多隔断到最少。注意：输出结果时两行答案是升序的。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=998244353; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||c...

题意：有一家糖果店，每天可以生产m颗糖果，你在接下来n天会去买糖果，你每天必须吃一颗糖果，你买的糖果可以保存以后吃，你每天买糖果还需要额外花当天买的糖果个数的平方的钱，求这n天你最少花多少钱？ 思路：dpdp[i][j]表示前i天买j颗糖果的最少花费。sum[i][o]表示第i天买o颗糖果的糖果花费。前i天买的糖果为第i天买的糖果加上前i-1买的糖果，注意每天必须吃一颗糖果（既i<=j）。状态转移方程：dp[i][j]=min(dp[i-1][j-o]+o*o+sum[i][o]) (j>=i&&j-o>=i-1&&o>=0&&a...

题意：有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？ 思路：求任意两点树上的距离应该用LCA.由于多了个电缆，所以我们从x到y是有3种方案：①从x直接到y，不坐电缆。②从x到u，再从u坐电缆到v,最后从v到y。③从x到v，再从v坐电缆到u,最后从u到y。我们取这三种方案的最少值就可以了 注意：lca写的丑的会被卡时间，由于u，v固定，所以可以用dfs先求出树上每一个节点到u，v的距离进行优化。 代码： #include <bits/stdc++.h> typedef lo...

题意：给与一个区间，求在区间选二个数的异或值最大为多少？ 思路：对于区间[L,R]: ①：L的二进制串长度小于R的二进制串长度，例如L=101（5），R=1110(14)。由于3<4,所以111和1000一定在[L,R]区间，因为1000为二进制长度为4的最小值，111为二进制长度为3的最大值。 ②：L的二进制串长度等于R的二进制串长度，则在[L,R]区间中的每一个数的最高位都为1,最高位异或后一定为0，所以等价于求区间[L-(1<<(最高位)),R-(1<<(最高位))]（去掉最高位）的答案。特判：如果L=R，则输出0，因为二个相同的数异或为0. 代...

题意：有一棵n个节点的树，树的每一个节点有一个权值，定义path(i,j)表示 i 到 j 的最短路径上，所有点的点权异或和。求所有path(i,j)的异或和。 思路：我们可以统计一个点被计算了多少次来求解，一个节点x，以x为终点的path有（n-1）条，然后包括它的路径与它的子树有关，一棵子树的节点到另一颗子树的节点路径包括x，节点数为偶数的不考虑，计算为奇数节点的个数，因为奇数 * 奇数才等于奇数。然后判断奇子树二二组合的数目，然后就将这值与n-1加起来是否为奇数，为奇数则ans异或x节点的权值，否则不管。 代码： #include <bits/stdc++.h> typed...

题意：有一颗n层的技能树，第i层有n-i+1个技能,学习第i层第j个技能则必须先学习第i-1层第i和i+1个技能，第一层的技能可以直接学。你能学m个技能，求你最大的战力加成为多少？ 思路：dp我们发现如果第i层第j个技能学习了，则以它为底的倒三角的技能一定学习了。设dp[i][j][r]为第n列到第i列中学习了r个技能且第i列学习了前j个技能时的最大加成。sum[i][j]为第j列前i行的和。我们可以写出状态方程：dp[i][j][r]=max(dp[i+1][p][r-j]+sum[j][i])(p>=j-1(满足学习前置技能条件)) 代码： #include <bits/std...

题意：有n轮游戏，每轮你可以从二个数中选择其中一个数，求你选择数的种类最多为多少？ 思路：先离散化数据，然后我们将每一轮游戏当成一条边，如果成环了，则该环所以端点都能选择，且与环连通的点也能全部选择，你画个图就很容易理解了，由环往外扩散。如果连通块无环，则有一个端点无法选择。所以我们用并查集来处理数据，有环则给该连通块做个标记。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const int inf=1000000007; inline int read() { in...

题意：让你对n个长度的木板染色，每次可以对连续的任意长度染同一种颜色，初始没有颜色，求最少需要染多少次能染成目标颜色？ 思路：区间dpdp[i][j]表示从i到j的区间染成目标颜色的最少染色次数。当第i个格子和第j个格子的颜色相同时，第i个格子可以被dp[i+1][j]顺便染成、第j个格子可以被dp[i][j-1]顺便染成。他还可以由dp[i][o]+dp[o+1] [j] (i<=o<=j-1)转化来（二个区间的合并成一个区间，相当于一个区间分成二个区间分别染色） 代码： #include <bits/stdc++.h> typedef long long ll; ...

题意：有一个长度为n的一维数组，每个元素有一个分值，你一开始在第一个元素的位置（1），你有m张卡片，有1，2，3，4四种类型，使用卡片可以让你移动等价于卡片数值的格数，然后将移动后到达位置的分值加上，求最大分值为多少？（使用完所以卡片后一定到位置n） 思路：像这种类型的题九成用dp，做dp题你需要考虑一个状态是怎么来的。dp[i][j][o][l][r]表示在第i个位置有j张1，o张2，l张3，r张4的最大分数为多少。它可以是第i-1个位置使用一张1来。它可以是第i-2个位置使用一张2来。它可以是第i-3个位置使用一张3来。它可以是第i-4个位置使用一张4来。由于直接数值有点大，会爆内存，而一...

题意：给你一个n个结点m条边的有负权边无负环的有向图，为每条边赋一个非负新值，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。 思路：参考了多篇题解，我们造一个超级源点与每一个点相连，且边权为0，从超级源点开始跑spfa;我们这m条边的新值为d[u]-d[v]+cost(u,v);证明：spfa松弛的条件是d[u]+cost(u,v)<d[v],所以d[u]+cost(u,v)-d[v]>=0;如果新图有一条路为u-x1-x2-v。则路的距离为d[u]+cost(u,x1)-d[x1]+d[x1]+cost(x1,x2)-d[x2]+d[x2]+cost(x2,v...

题意：告诉你有n个整数，按顺序构建一棵二叉查找树，既树中每一个节点满足左儿子小于节点，右儿子大于节点。求每次插入一个整数后树中每一个节点深度之和？ 思路：学过二叉查找树的都知道插入操作最坏情况为O(n^2)（链状时），所以模拟肯定过不了。仔细观察二叉查找树，再分析下插入时进行的操作，我们可以发现对于一个节点，如果它是它父亲的左儿子，则它父亲是整棵树中大于它的最小的节点，如果它是它父亲的右儿子则它父亲是整棵树中小于它的最大的节点，所以你插入一个节点后，它的父节点要么不存在，要么就是小于他的最大节点或大于它的最小节点，那究竟是选哪个做父亲呢，由于在你没插入之前，他们是相邻的，所以他们相连，而你的大...