题意： 给定一棵个点的树，问有多少种删边方案使得删边后每个连通块大小不大于，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对取模数据范围： 题解 ：表示以为根，连通块的大小为的方案数。考虑的一个儿子：  和的边被断开，则的连通块大小对无影响， 与的边未被断开，则  可以注意到这是一种背包，关于选或不选的问题。普通背包第一层是枚举物品种类，这里即枚举第几个。第二层枚举体积，这里即枚举连通块大小，故先逆序枚举的连通块大小，然后枚举（不考虑顺序）子集连通块来更新即可。这里需要注意在枚举时，保证当前的中没有出现过，否则会出现重复方案。 代码： #include<...

题意： 小需要储备天的面包，面包店每天生产个面包，第天生产的第块面包的价格为，同时，一天购买块面包需要额外花费，现在问储备至少块面包的最低价格是多少。数据范围： 题解：分组背包问题。从低价到高价开始选择面包，本题关键是考虑额外的部分。考虑第天的第块面包，需要多加，对于第块面包，需要多加，所以对于第块面包多的价值就是。所以预处理下第天的前缀和即可。同时要考虑到每天得有面包吃，所以转移时前一个状态必须从开始。时间复杂度： 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; template<...

题意： 给定组数，每组两个数，和。在第组数时，有三种操作：可以不选，如果未被选过，可以选择，或者没被选过，可以选择，但是一次最多选一个数。现在问组数最多可以选择多少个。 题解： 考虑将和连条边。假设最后有个连通分量，考虑第个连通分量，如果该连通分量的边数不小于点数，则加上点数，否则加上点数减。可以这么理解：考虑一个连通分量： 图中每选取一个点，就要切割点这个点的一条边。因此当这个图中有点，边时，只能选个点，而当边数大于等于点数时，优先选择边数等于的点，最后会剩下的点边数多于的点再被选择。所以无论如何所有点都会被选择。 代码： #include<bits/stdc++.h> usin...

题意： 太长了，懒得解释了。 题解： 暴力模拟即可，官方题解给定的是有相关证明在内一定可以找到解，所以直接暴力冲。但是如果极端情况的话还是可能被卡的可能，毕竟组，所以感觉还是可能的。具体就是直接模拟前两个个模块的是否相同，出现了该模块的三个直接，如果前两个某个模块不是且相同，则第三个模块也必须和他们相同。或者前两者不同，则第三个和前两者也要都不同。管你看没看懂，模拟就完事了！（皇化100%。 代码： #include<bits/stdc++.h> using namespace std; const int N = 300; struct Node{ string card[4];...

题意： 有种菜，每种菜利润为，数量为，问在尽可能服务多的客人的情况下，可以获得的最大利润是多少（可以为负数）。注意：除了吃第一种菜，吃第种菜前必须先吃第种菜。总共有组数据。数据范围： 题解：最多客人数即。 第一种：整体考虑。由于第一种菜必选，故从第二种菜开始考虑每次贪心地选可以吃到的总利润最大的菜，且的前置所有菜都没有被其他先来的客人吃完。则吃完后可以区间修改都减 第二种：拆分考虑。考虑到第种菜的利润是否大于前面吃到的最大利润，如果大于，则把这个菜全部吃掉（最多吃盘），否则继续往后考虑直到利润大于前面吃到的最大利润。 拆分考虑的代码： #include<bits/stdc++.h>...

题意： 给定一棵个点的树，边权均为，以及多出的一条边权为的边，询问树上两点之间的路径的最小权值。 题解： https://ac.nowcoder.com/acm/problem/19814 这道题的弱化版，只多出了一条边权为的边。预处理树上倍增关系，然后加入这条边权为边，每次取直接在树上走的最短路权值和经过该条边的最短路权值的最小值即可。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T> inline T Read(){ T s = 0,...

题意： 给定一个长度为的颜色序列，初始颜色序列无颜色每，次可以选择使得都变成一种颜色，问最少多少次可以使得整个区间变成给定的颜色序列。数据范围：，还是baidu才知道的~。题解：由于数据范围很小且涉及到区间操作，所以考虑区间。 表示将涂成状态转移：对：  当，涂时可以顺便把涂了，涂时可以顺便把涂了，故此时 当，此时没法一并涂颜色了，枚举，故此时 代码：*  #include<bits/stdc++.h> using namespace std; const int N = 55; char s[N]; int f[N][N]; int main() { scanf("%s", s ...

题意： 给定，在中选取两个数使得两数异或值最大。数据范围：  题解： 考虑二进制形式，则二进制的最高位最高越好，同时选取的两个数二进制位不同的部分越多越好。考虑一个极端情况：即答案的二进制形式为那么取,取则两者异或答案最大。这里的为，则为。对于和,当两者的二进制最高位相同时，无论怎么选择最高位对最终答案都无贡献，所以考虑将最高位删去后继续考虑，直到存在的二进制最高位大于的二进制最高位，那么答案就是，如果删至两者均为，则答案为，此时的情况是 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; t...

题意： 给定一棵个点的树，每个点有点权，问树上所有两点之间的最短路径异或和为多少，即求树上所有两点的路径所经过的点的点权的异惑和。题解：既然是考虑异或和，那么就要考虑一个点是否对答案有贡献。考虑一个点在所有路径中出现的次数，由异或的性质，可以知道当一个点在所有路径中出现总次数为偶数时，则对答案无贡献。对于树上任意一点，考虑这个点的路径计算：  当这个点作为一条路径的端点时，共次。 考虑这个点的所有子树中的两点路径经过该点的次数 考虑这个点的子树与这个点的父亲结点除子树外的其他子树之间的路径经过该点的次数设共有个子结点，则答案为  代码： #include<bits/stdc++.h&gt...

题意： 给定一个倒三角，共行，第行有个元素，选取必须先选取和，现在要求选择个元素，求选取的个元素可以获得的最大值。 题解：学习参考了该篇题解：https://blog.nowcoder.net/n/4f95681bfb9e4bf29b49ce9aa321248d由于选择一个元素，以其作为倒三角的顶点的三角形必须全部选中，所以从给定的倒三角的最右端开始，先处理第列，再处理第列，...，最后处理第列。 表示当前已经选择了这个元素，并且总共选择了个元素可以获得的最大值。状态转移方程为其中是该状态必选的。 状态转移的解释：由于这个状态必然选择了这个元素，  对于第一维，由于第必然已经被选择了，所以该状...

题意： 给定一个个点条边的无向连通图，所有边边权均为，次询问，每次询问图中两点的最短路径，保证无自环与重边。数据范围： 题解：由于是无向连通图，一眼看上去是一个不可做题。卡了很久很久才发现了数据范围有点不寻常，考虑最多有条多余的边，其余边可以组成一棵树。那么如果是一棵树则可以先预处理后用，本题相较于树多了一些边，这些边可能会使得由树得到的树上两点唯一路径变得不再唯一，那么就可能会使得树上两点的路径变得更短。那么考虑何时会导致这些边有效果：对于一条边，如果树上两点距离大于，则途径这条路的所有路径都会被更新。那么只需要用多余的边依次对树上的路径进行更新即可，即加上这条边对图进行一次最短路求解即可，...

题意： 给定长度为的序列和,求，其中，答案对取模数据范围： 题解：先计算  首先考虑长度为的 继续考虑长度为的，考虑取第一项的的，第二项的，...以此到最后一项取的。所以从第二项开始每项的第一个元素都多了出来即多了，即答案为 再考虑长度为的，第一项取的，第二项取，第三项取,...最后一项取得；继续取第二项剩余的，第三项的，第四项的，...最后一项的得,剩余可以取第三项的，第四项的，...倒数第二项的，最后一项的得：。所以得出结论为负责为对于： 继续考虑长度为时，只有一个 再考虑长度为时，只有 再考虑长度为时，只有可以发现长度为和长度为的一样，长度为和长度为一样，长度为和长度为一样。长度为和长度...

题意： 共个格子，每个格子有相应的分数，张卡牌，卡牌上的数字表示可以从当前格子往后走格，初始在一号格，自动得到一号格的分数，问选择卡牌进行走格子的方式中可获得的最大值为多少。数据范围：，卡牌数字，每种卡牌数量为，保证题解：这种数据范围自然想到的是爆搜加剪枝。由于最多有个状态，因为先使用一次号牌再使用一次号牌，与先使用一次号牌，再使用一次号牌是一种情况，如果重复递归的话复杂度爆炸，故想到记忆化搜索。 表示剩余个号牌，个号牌，个号牌，个号牌，当前在号格子走到号格子可得到的最大分数。每次记忆化一下即可。代码： #include<bits/stdc++.h> using namespace...

题意： 给定个矩形的宽和高，求可以得到的矩形的最大面积。题解1：本题一眼看上去就是笛卡尔树的题，可惜笛卡尔树当时学到半路放弃了。回想过来笛卡尔树是由单调栈延伸过来的，所以考虑能不能用单调栈瞎搞。本题的难点在于如何处理一定宽度和高构成的矩形面积，即可能更长的宽度和较短的高度也会构成更大的面积。考虑单调栈，由于短板决定高度，所以要构造一个单调递增的栈。  当时，直接入栈，最后的栈一定是单调递增的，所以对于栈内每个元素，出栈时其必然比之前的元素高度低，所以可以直接叠加他们的宽度计算。 当时，短板决定高度，所以要将当前栈的所有元素高度全部切成不高于才能继续发挥作用。切成的高度相当于给增加宽度，所以对于...