题意 个点 条边的简单连通无向图，每条边有一个权值，定义一条路径的权值为这条路径上所有边的最大权值，定义 为点 到 的所有路径上最小路径权值。 给两个长度为 的序列 ，你可以任意排列 最小化 。输出最小值。 题解由于是最小化最大值问题，并且显然不能二分，考虑贡献法。 首先按照边权从小到大排序，依次加入图中，如果在加入途中已经可以保证两个分别来自 的点联通，则当前加入的边一定...

原题链接 题意给定一个长度为 的序列 ，问有多少个好的划分。 一个大小为 的好的划分定义为将 划分为 个部分（最后一部分可能少于 个数），每个部分内部都单调不降。 现在有 次修改，每次修改将 修改为 ，计算修改前和每次修改后好的分区的数量。 题解首先一个容易得到的性质是，如果一个数 满足条件，则 的所有因数均满足条件。 同时两个数 满足条件，则 也满足条件。 这提示...

原题链接 题意给一个长度为 （且 为奇数） 首尾相连的数组 ，每次操作你可以将 分别加上 注意 时， 指的是 ，同理， 时， 指的是 。 请你找出一个操作序列，即每个位置上需要操作几次，将 中所有元素变成相同值。 题解设第 个位置上需要操作 次，最后得到的值为 ，则有： 作差分可得即 ，由于 已知，记为 ，再将正负两两组合，即 ，再令 ，则 。 显然有...

原题连接tag: 树形dp, 贪心, *2100 题意给定一棵大小为 的树，每个节点都有一个海狸，每次去到一个结点必须取走一个海狸，如果目的节点的值为0则无法前往，最多能够取走多少个海狸。 题解首先可以发现每个子树如果能够最优显然问题就一定是最优解，所以联想到树形 dp。设 为从 出发，在其子树中的最优解。 考虑状态转移，父节点的 dp 值显然是由子树的贡献加上到达子树所产生的贡献（因...

原题连接 tag: DP 题意 个订单，分别在 天下达。 最多有 个订单可以同时发货 订单 只能在 ​ 天或之后发货 每次发货要 天后才能再次发货 每个订单的不满意度为实际发货时间 与订单下达时间之差，即 。 求所有订单的不满意度之和的最小值。 题解

A. Max Plus Size题意求奇数位之和和偶数位之和的最大值 题解略 代码1234567891011121314151617181920212223242526272829303132333435#include <bits/stdc++.h>using ll = long long;void solve(){ int n; std::cin >>...

原题链接 tag: 最小生成树，贪心，*2200 题意给定一个 个点， 条边的图，同时给定两个正整数 ，每条边有 两个权重，求图的一棵生成树 ，使得 ​ 最小，求出这个最小值。 题解考虑暴力的做法，由于是双变量最优化问题，考虑枚举某一个变量对另外一个变量进行优化。在本题中可以枚举最大的 值，用所有小于 的边建图，然后在这张图上以最小化 跑 最小生成树。这样做的时间复杂度为 ...

链接 VP赛时 ABCD，补题EF 分数：800 - 1200 - 1400 - 1800 - 2000 - 2900 A、B、C没什么好说的。 D题赛时卡了，没想到 这个条件怎么用，技巧 +1 E题回顾了一下一个较为经典的概率dp。 F题正好复习一下前段时间刚学会的 min_25 筛（确实好用，也顺便整理了一下 min_25 的板子。 A. Find Minimum Operations...

原题链接 tags: 思维，前缀和，*2600 题意给你一个长度为 序列 ，求 。 其中 将返回将数组 变为回文数组的最小操作次数，有以下两种操作： 选择数组中两个相邻的数 ，删除它们并用元素 插入。 选择数组中一个数 ，用两个正整数 替换它。 题解谁能想到一道 *2600 的题核心代码只有20行…… 显然存在一个上界 ，因为可以一直选两个数合并直到剩下一个数。 要...

原题链接 tags: 思维，数学，*2200 题意给你一个长度为 的序列 ，进行 次询问，每次询问给出 ，询问区间 中能否选出 个数组成两个非退化的三角形。 非退化三角形：边长分别为 ，则有： 题解一开始以为会是一道数据结构大题…… 但是很容易发现，如果一个区间中不包含两个退化的三角形，则一定有任意三个数都不满足上面三个条件，更具体的，任意选三个数，最小的两个数相加一定小于等于最...