20250206 部分作业

好多题，不嘻嘻。

只保留了我认为比较有意义的题。

QOJ9540 Double 11

题意

现在有个物品，每一个物品有一个销量。

你现在需要将所有物品分为组，设为第个物品分到了哪一组。

现在需要对每一组选出一个非负实数权值，满足。

在此条件下，需要让最小，求出这个最小值开根后的结果。

。

题解

考虑若已经确定了分组的方案，如何确定最优的。

设第组物品共有个，他们的之和为。

根据柯西不等式，有。

那么可以得到。

而题目需要我们求出最小值开根后的结果，也就是。

假设我们现在已经固定了的取值，如何进行分组。

那么此时可以发现，将初始的排好序之后，一组物品一定在一个区间内，以分为两组进行举例。

假设两组分别有个，所有物品总销量为，那么代价为。

不难发现，是下凸的，也就是说某个区间的最小值在两个端点处取到。

也就是说，第一组物品销量和应该尽可能小或者尽可能大。

那么第一组物品一定是所有物品中最左边的个或最右边的个，这自然是一个区间。

这样我们就证明了，同一组的物品一定在一个区间内。

考虑暴力，设表示前个物品分为组的最小方案。

设，那么有。

~~这里应该有一个证明，但我不会证~~

这样我们就证明了是满足四边形不等式的，也就是说是一个蒙日矩阵。

原题相当于在蒙日矩阵上做最短路，要求恰好走条边。

那么直接 wqs 二分然后二分栈优化 dp，时间复杂度是。

提交记录。

QOJ9737 Let's Go! New Adventure

题意

游戏中有个怪物，你可以创建若干个账号刷怪。

一个怪只能被打一次，一个账号打的所有怪，编号必须是一个完整的区间。

第个怪可以提供的经验值。游戏的满级是级，从级升到级需要的经验值。

一个账号带来的收益是他的等级减去一个常数，求所有账号收益和的最大值。

，保证。

题解

首先令，这样就可以忽略等级只有种。

令为的前缀和，为的前缀和。

令表示如果打怪总共获得了的经验，足够升到多少级。

设。

由于递增，那么容易发现是凸的。

考虑列出 dp 方程，表示当前打了前个怪，最大总收益是多少。又变成了蒙日矩阵上的最短路问题（实际上是最长路（对。

时间复杂度，后面的来自求的二分。

提交记录。

~~似乎可以优化到单，但我没太懂~~

ABC383G Bar Cover

题意

现在有个数字，第个数字是。还给定了一个数字。

对于一个数字，你需要选出个长为的互不相交的区间，一个方案的权值是被覆盖的所有数字的和。

对于每一个，求出最大的权值。

，。

题解

令，那么问题相当于从中选择个数字，满足选中的位置下标至少差了。

考虑暴力 dp，设表示前个数字中选出了个，上一个选中的数字和的位置差，最大的权值和。

那么 dp 值关于这一维应当是凸的，也就是说可以使用闵可夫斯基和进行合并。

考虑从转移到的过程，相当于乘上了一个的矩阵，矩阵中每个元素都是一个凸的函数。

分治求出的矩阵，时间复杂度。

CF1787H Codeforces Scoreboard

题意

现在有道题，你每一分钟可以提交一道题，同一道题目只能提交一遍。

如果第分钟提交了第个题目，将会获得的分数。

求最多能获得多少分。

。

题解

假设所有题目初始会有的分数贡献，然后提交会获得的分数。

显然，如果取到那还不如不提交，也就是说可以直接假设可以获得的分数。

后面和这个一样，平衡树解决。

时间复杂度。

CF1534G A New Beginning

题意

平面上有个点，第个坐标为。

你初始在平面的上，每一次可以向右或向上走一步。

若你当前在点，则激活一个点的代价为。

求激活所有个点的最小代价和。

。

题解

考虑激活一个点的代价是当前位置与那个点的切比雪夫距离。

那么我们应该只会在走到的时候激活这个点。

设表示当前走到了这个坐标，最小代价是多少。

转移分为两种，第一种是向右或向上走一步，方程为。

第二种是激活一个点，那么相当于给整个加上。

考虑维护 dp 值的差分的差分。

由于一次操作只会给差分的差分带来的变化，所以我们维护差分的差分每一个的位置。

（也就是说如果，那么我们维护序列）。

现在考虑两种操作怎么维护。

第一种操作相当于是给原来函数谷值右边的部分往右平移一个位置。

也就是说，将维护序列的后半部分，整体。

第二种操作相当于是给某个位置的差分的差分加上。

相当于是给序列中插入两个相同的数字。

使用对顶堆维护即可。

时间复杂度。

提交记录。

QOJ8362 game

题意

现在有个怪物，打败第个怪物会掉点体力，打完之后会获得点体力。

任何时候你的体力值不能是负数。

对于每一个求出，现在需要打至少只怪物，初始体力值最少是多少。

。

好像这题的样例输出 1 是错的，然后输入格式是对的。

题解

先考虑，如果我们已经确定了初始的体力值，我们如何确定怪能否全部打完。

相当于是确定一个打怪的顺序。

首先可以知道，一定是先打的怪，再打的怪。

为什么呢，假设存在一个，并且其后有一个满足。

我们不妨设为最小的这样的，则对于任意都有。

那么我们将打怪物的时机调到的前面一个，其他顺序不变，可以发现这样打每一只怪物的初始体力都不劣于之前。

所以至少存在一个合法的方案，先打了所有的怪物，再打了所有的怪物。

对于的部分，因为我们的体力会越打越多，所以肯定是按照从小到大的顺序去打。

对于的部分，不难发现我们其实可以知道所有怪物打完之后的最终体力值（如果能打完的话）。

那么这部分和上面那部分应该是对称的，也就是说这部分应该按照从大到小的顺序去打。

这样我们就确定了一个打怪的顺序出来。

那么来思考第一部分。

由于第一部分我们是按照从小到大的顺序去打的。

那么可以发现，我们一定是打了一个前缀的所有怪物（因为如果某一个怪物打不了，后面的所有怪物就都打不了）。

我们容易预处理出，如果第一部分要打个怪物，那么最小的初始体力值是多少，以及中间过程体力值会变化多少。

假设我们能够算出，在第二部分中，打个怪物需要多少的初始体力，那么直接双指针一下，问题就解决了。

所以本题难点在于第二部分。

对于第二部分，我们已经知道了打怪的顺序，那么就可以先看看暴力。

设表示这些怪物中，需要打个怪物，最小初始体力值是多少。

那么有方程。

考虑会说明什么事情。

对于任意的，可以发现会有。

而。

这说明的值永远不会再变化了，这是一个很棒的性质。

设表示最大的满足。那么：容易发现，对于的部分，相当于是和这个数列做卷积，得到。

由于它们都是凸的，所以这可以直接闵可夫斯基和优化。

值得注意的事情是，也是需要转移的，我们这个时候可以把当作来弄。

时间复杂度。

提交记录。

GYM103202L Forged in the Barrens

题意

给定个数字，对于每一个求出将整个序列划分为段，每一段极差之和的最大值。

。

题解

和上面那个 ABC 基本一样。都是区间分治一下维护矩阵。

直接做状态是，分别表示这个区间有没有选定最小值和最大值。

这样直接做可能会寄，考虑如果一个区间同时选定了最小值和最大值，我们直接强行让这个区间结束。

这样就只需要记三种状态，复杂度，其中。

GYM102586B Evacuation

题意

现在有一共个城市，第个城市有一个避难所，容量为。。

如果第个城镇没有遭遇陨石袭击，那么可以容纳的人，否则可以容纳个人。

现在一共有个人在同一个城市，具体在哪个城市并不确定，和组询问。

第组询问给定，现在的城市遭遇了陨石袭击，问最劣情况下人员迁走的代价，每一个人每走一步代价为。

。

题解

首先可以知道，这个人初始位置肯定在中间，不然就不用搬走了。

考虑如果已经确定了初始位置，如何知道答案。

所有人应该都优先往两边最近的避难所走，所以二分一下然后前缀和瞎算一下就对了。

容易发现，一个询问中，当所有人初始点在区间左半边某个点的时候，区间右端点在哪里不影响答案，因为左端点左边的位置可以放下所有人。

同理，区间右半边也是一样的。

所以考虑对两种情况分类讨论，考虑求出起始点在区间右半边的最劣情况。

设为所有人起始点在，区间右端点在，最大的答案是多少。

考虑是多少。

若，那么。

同时还有。

可以推出。

若，则可以知道，可以得出相同的结论。

移项可以知道。

也就是说是满足四边形不等式的。

而我们求的相当于。

考虑将所有询问离线，然后建一棵线段树，将所有询问挂到对应的区间上。

然后对于一个区间来说，每一行是这个区间里面的一个点，每一列是挂在这个区间上的询问。

然后我们对这个询问跑分治，就能跑出所有询问的答案。

时间复杂度是。