题意 n 条木板，每条木板都被分成 m 段且每一段都有要涂的颜色，有 t 次机会涂色，每次可以选择一条木板的连续一段涂成同一种颜色，问最多可以涂对多少段。 solution 考虑四维dp的做法。 代表到第 条第 段时涂 次，当前段涂红或蓝的最大正确数，可以得到转移方程： 当 (属于当前木板第一段) 时，由上一个木板转移过来：   否则，由当前木板的上一段转移过来：   最后结果显然为 。 时间复杂度 ，空间上可以使用滚动数组压维，空间复杂度为 。 Code #include <bits/stdc++.h> using namespace std; const int N = 55;...

题意 给定一个 n 个点 m 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。 solution 求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，将走过的边加入边集，建一个新图出来。为了使路径最短，考虑最小生成树，但需要满足题目的条件，因此我们对新的图进行排序，以高度为第一关键字从大到小排，再以路径长度为第二关键字从小到大排，这样可以保证点最多的同时路径最短。 Code #include <bits/stdc++.h> using...

题意 给定一个长度为 的数组， 次询问查询区间 内 的元素个数。 solution 考虑树状数组。我们在查询区间 的个数时，为了更好计数，这个区间应该不包含 的元素才行。因此我们不妨离线，将询问的 从小到大排序，将数组也从小到大排序，这样从小到大处理询问，每次处理时只将 的数挂到树的对应下标上（因为询问的 是从小到大的，因此之前树上的数一定比当前询问的 要小），维护答案为 。 Code #include <bits/stdc++.h> #define x first #define y second using namespace std; const int N = 2e5 + ...

题意  件食材（每种食材的数量可以视为无限），小明连续工作 时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第 道菜肴有三个属性 ，，， 是该菜肴的美味值， 是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：，完成这道菜需要 的时间。求在这 时间内能做出菜肴使得总美味值的最大值。 solution 首先需要贪心确定顺序，考虑只有两道菜，可以得到：，化简后得到：。排序后背包即可（需要降维）。 Code #include <bits/stdc++.h> using namespace std; typedef long...

题意 给定一个长度为 的数组，求长度为 的不同子序列个数。（） Solution  表示长度为 ，删除 个元素的子序列个数，不考虑重复的话，有 （即已经删除了 个和已经删除了 个再删除这一个的情况）。 考虑去重。如果是单纯求不限长度的不同子序列的去重，容易得到： （ 为上一次 出现的位置），在此题中也是同理，我们需要剔除 之间的元素，假设我们当前需要剔除 个元素，那么在之前我们先需要剔除 个元素， ，初始化为所有的 。 Code #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const in...

题意 给定一个由n个元素组成的序列 { a1, a2, a3,..., an } ，她想知道其中有多少个子序列 { ap1, ap2, ..., apm } ，满足对于所有的 , apipj < apjpi成立。 Solution1 py + dp直接冲。 n, mod = int(input()), int(1000000007) a = list(map(int, input().split())) dp = [ 1 for i in range(n) ] for i in range(0, n): for j in range(i): if (a[j] ** (i + 1) &lt...

题意 给定一个长度为 的数组 A ，把所有长度 >= 的区间中的第 大值插入 B 数组中，求 B 数组的第 大数。 Solution 这种显然二分答案题我们主要关心 问题。 如何计算第 大数 的区间个数？ 假设区间 中刚好有 个数 ，则 区间全部满足第 大数 。 因此考虑尺取，若当前区间满足 个数 ，则计数 ，同时移动左边界；否则移动右边界直至。。。当 时，说明 过小，调整左边界，否则调整右边界。 Code #include <bits/stdc++.h> using namespace std; int t, n, k, a[100005]; long long m; bo...

Solution:木棍合理范围即初始区间是[0,n项和/k]，n项和/k是理想情况不考虑木棍分段的最大长度，或者默认用一个比较大的数字开始分也可以。然后二分棍子的长度，根据截得的段数总和来判断是否满足要求。 #include<stdio.h> int main() { long long n,k,num,i,j,p; double l,r,m,a[200005]; scanf("%lld%lld",&n,&k); for(i=0; i<n; i++) scanf("%lf",&a[i]); l=0.0,r=100000000000.0; for(i=0...

Solution:如果直接从前往后，则后面的又会影响到之前到，所有干脆从后往前考虑，这样就不会对之前计算到的造成影响。从后往前维护两个队伍各自的最大值和会被增加的战斗力，如果前面的战斗力小于另一个战队的当前最大值，则被消灭，保证了每个人只会被计算一次。 #include <bits/stdc++.h> using namespace std; #define x first #define y second typedef long long ll; const ll N = 2e5 + 5; pair<int, ll> p[N]; ll t, n, m, b[N]; ...

题意 题意很简单，求长度为n的01串逆序对数量和。( n <= 1e18 ) solution 任意选两个位置 ，令 ，这样一定能产生逆序对，这样有 种选法。剩下的位置随便放，有种选法，总方案数即为答案。( 注意 1 需要特判 ) #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll qp(ll a, ll b) { if (b == -1) return 0; ll ans = 1; while (b) { if (b & 1) a...

题意： 给定一棵n个节点的树，求偶数长度路径的数量。 Solution1: 考虑树的深度对距离的影响，可以发现，深度奇偶性相同的点之间的距离总是偶数。 证明：我们先将深度更大的点走到和另一个点深度相同，显然需要偶数步，然后两个点同时移动到最近公共节点，可知所用的步数是相同的，加起来也是偶数。 Code #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, idx, h[N], dep[N]; struct Node { int to, next; } E[N]; void add(in...

Solution：首先，一个区间的异或和可以由前缀异或和得到。即sum[l,r]=sum[r]^sum[l-1];枚举左区间的右端点，再枚举左区间的左端点，开一个桶记录个数，再以该左区间右端点+1为右区间左端点，记录与左区间异或和相等的右区间个数，以此累加即为答案。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e6+5; ll n,x,res,a[N],b[N]; int main() { cin>>n; for(ll i=1;i<=n;i++) {...

题意 给定一棵n个节点的树，边权值视作流量，找到一个源点使得从该点出发到所有叶子节点流量和最大。 思路： 我们先考虑这样一道题：指定一点使得到树上其他点的深度之和最小。 这显然是树的重心的性质：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。 我们先假设这棵树的根为1，进行一次dfs，可以求出每个点的深度 和子树大小 ，设某点作为根深度之和为 ( i )，显然： = 。 当根从 转移到子节点 时，以 为根的子树内所以节点 都减1，其余节点加1。从而得到状态转移方程：，答案取最小值即可，时间复杂度 。 Code #include <bits/stdc...

思路：我们可以发现叶子节点是一定要染的，如果从下往上染没染过的点，不一定是最优的，所以对于其他的结点，我们更新最大染色范围，如果该结点的子节点可以染色到它的话，那么他就不需要再染色，否则它就需要被染色，同时选择子节点内范围最大的点染色，更新最大范围。 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<int> v[N]; int n, res, k[N]; int dfs(int x, int fa) { int sum = 0; for (auto now : v[x...