题意： 有n条蚯蚓，在m秒内每一秒选择最长的一条蚯蚓分成二份，其余蚯蚓增长q长度，然后按要求输出。 思路： 用二个队列进行模拟，维护二个队列的单调性，一个队列加入长的，另一个队列加入短的，这样二个队列就是单调的，队列中保持0时刻的长度。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e12; ll a[100005]; bool cmp(ll a,ll b) {   &nb...

题意：有一个有n个彩珠、m种彩珠的彩带，使每一种彩珠都包含的最小长度是多少？ 思路：离散+尺取法 代码： #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'||ch>'9') { if(ch=='-') f=-1; ch...

题意：你有n件装备，每件装备有两个属性，每件装备只能用一次，你打boss时属性只能从1开始连续用装备攻击，求你的最大攻击次数。 思路：二分图匹配问题，属性与物品编号连边，从1开始匹配，用匈牙利算法，冲突时进行改变。 代码： #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'||ch>...

题意：有一个由30001个小岛组成的群岛，编号为0-30000，一字排开，首先从0岛跳的d岛，然后每一次跳的距离与上一次的距离绝对值等于小于1，有些岛有宝石。 思路：dp:ma[i]表示i岛的宝石数目。dp[i][j]表示跳到i时跳的距离为250-j+d时收集的最大宝石数。初始化dp[d][250]=ma[d].s=250-j+d;dp[i][j]=max(dp[i][j],dp[i-s][j]+ma[i])dp[i][j]=max(dp[i][j],dp[i-s][j+1]+ma[i])dp[i][j]=max(dp[i][j],dp[i-s][j-1]+ma[i])(s>=2(因为这...

题意：给你一颗树，你选择一个节点当根，求所有点的深度和最少为多少？ 思路：树状dp+换根一开始随便选一个点当根计算结果。dp[i]表示以i为根的子树节点的深度和。se[i]表示以i为根的子树的节点数目。换根：dp[v]=dp[u]+n-2*se[v];(v为u的子节点，根从u转向v时，以v为根的子树中的节点深度全减一，其余节点深度加一) 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=1000000007; inline int read() { ...

题意：给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。 思路：树状dp+换根：flow[i]为以i为子树i到子树叶子节点的流量最大值。ans[i]表示以i为根节点时的答案。flow[u]= min(flow[v],cost(u,v))(v为u的子节点)。换根：ans[v]+=min(cost（u,v）,ans[u]-min(cost（u,v）,flow[v]));(为了节约空间，ans和flow可以共用一个数组)。 代码： #include<bits/stdc++.h> using namespace std; #define ...

题意：你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？ 思路：树状dp没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条件。se[i]表示以i为根的子树的节点数。根节点u，子节点v：dp[u][r+l]=max(dp[u][r+l],dp[u][l]+dp[v][r]);结果为dp[0][m];（0节点不是一门课，一开始m要+1，因为0节点一定会被选） 代码： #include <bits/stdc++.h&g...

题意：给与一棵n个节点的树，求每个点的连通点集的数量？ 思路：树形结构+换根dp[i]表示以i为根且包括i的这棵子树连通点集的数量。ans[i]表示包括i的连通点集的数量，既结果。父节点u与子节点v：dp[u]= (dp[v]+1) * dp[u];（v为u的子节点）换根时:ans[v]=((ans[u]/(dp[v]+1))+1)*dp[v];注意：0不能求逆元，所以当(dp[v]+1)%inf=0时，你就需要重新计算一下该点的结果。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; ...

题意：有一棵n个节点的树，第一天你在s点住宿，每一天你可以浏览与它距离不超过1的节点，你不能住宿在你已经浏览过的节点，求你最多住宿几天？ 思路：树状dp，以s节点为根。dp[i][1/0]表示在i为根的子树中是否在i节点住宿的最大住宿次数。如果u是父节点，v是子节点。dp[u][1]= dp[v][0]+1;(v为u的子节点)dp[u][0]= max(dp[v][1],dp[v][0]);(v为u的子节点)答案为dp[s][1]. 代码： #include<bits/stdc++.h> #define ll long long #define inf 1024523 using...

题意：有一颗n个节点的树，每个节点有一个权值k[i]，一开始树上节点全是白色的，你可以选择一个白色的节点进行染色，使该节点到根节点路径上的点距离该节点小于k[i]的节点染成黑色。求使该树所有节点变黑的最少操作次数。 思路：树形结构+贪心由于染色的节点在你选择的节点和根之间，所以叶子节点你一定会选择，然后从叶子节点到根的回溯上看，你可以在叶子节点可以染色的范围和不能染色到的第一个节点（考虑同叶子节点）中选择一个可以向根染色更近的一个节点进行贪心，记录你的操作次数。对于只能在白色节点染色的问题，你可以想象对节点染色顺序使从根节点到页节点进行的，所以你无需考虑。 代码： #include <b...

题意：有n件货物，每件货物有一个重量，我们有x个承重为w的箱子，求是否能全部装上？ 思路：dfs暴搜：先将货物重量从大到小排序，这样可以降低解空间。dfs时箱子使用个数不超过当前物品数，因为超过没有意义。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=1000000007; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9')...

题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 思路：建立dfs离散序，化树为序列。（既先序序列）树状数组维护序列数据。操作1：将加的节点重置为0；操作2：将i节点所在的序列位置到i节点所在的序列位置+i节点为根的子树大小-1进行区间加a，以为先序序列子树的是连续的一段，开始位置为根的位置。操作3：输出结果。 代码： #include <b...

题意：给你一个4 * n的矩阵，让你用1 * 2的矩阵填满，求有多少种方法？ 思路：n=1时有1种n=2时有5种n=3时有11种n=4时有36种由官方题解可知dp[i]=dp[i-1]+5d[i-2]+dp[i-3]-dp[i-4].所以我们可以用矩阵快速幂求结果。为了防止产生负数，所以-1可以等价于需要模的数-1。*代码：** #include <bits/stdc++.h> typedef long long ll; using namespace std; ll inf=998244353; inline int read() { int x=0,f=1; ...

题意：给你一个长度为n的序列，你是否能用两个栈用以下操作进行排序？操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列不能输出0，能则输出最小字典序的操作。 思路：对每一个数进行处理时能放入第一个栈就不放第二个栈，这样就能确保得到的是最小字典序的操作。什么时候可以放入第一个栈呢，就是该数后面的第一个大于它并且不能放入第二个栈的数的后面的数没有一个数比它小，既在遇到这个数时该数已经输出了。 代码： #include <bits/stdc...