【题解】模拟赛 20231111 部分题题解

Zxd2009 · 2023-11-12 13:17:56 · 个人记录

官方题解下载

如果有错欢迎讨论交流

opt / 暴力操作

据说这题数据出锅了，不建议大家提交。

首先，当 a 是非负整数，b、c 都是正整数时，\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor = \lfloor \frac{a}{bc} \rfloor。

我不会证，改天补上，有人会的话可以告诉我。

我们可以发现，把一个数 a_i 变为 \lfloor \frac{a_i}{x} \rfloor 可能会有很多种方案（以下简称这个操作为 a_i 整除 x），例如把一个数整除 4，可以一次整除，也可以两次都整除 2，对应也可能会消耗不同的代价。所以我们要做的第一件事情就是 "修补" 代价数组。

• 由于把一个数整除 1 不会改变序列，而且题目保证 c_i （即代价序列）为正整数，所以这样做还会浪费钱，肯定不优，所以 c_1 就可以视为花费 0 元。
• 上面的例子也说明了，把一个数整除 (i \times j) 等价于把一个数整除 i 再整除 j，所以 c_{(i \times j)} 就需要更新为自己和 c_i \times c_j 中的最小值。
• 由于把一个数整除更大的数肯定比整除更小的数更优，所以就把 c_i 设为自己和它后面的数的最小值，这样能保证序列是递增的。
• 有些时候，i \times j > m，但没法存进数组里面。综合上面的内容，就可以把 c_{m + 1} 设为这些值的最小值。
  （这里 std 采用的操作是先进行前面的操作，再进行这种操作，最后再进行递增修补，但可能是数据原因，洛谷那道评测题并没有卡这个操作的数据，所以我也没办法验证是否有更加简化的做法。）

对应的伪代码如下：

c[1] = 0;           // 整除 1 没有意义
c[m + 1] = 1e18;    // 这个位置本来没有初始值，因为要更新最小值，所以设为极大值
for(int i = 2; i <= m; i++)    // 整除 1 没有意义，所以可以从 2 开始
{
    for(int j = 2; j <= i && i * j <= m; j++)    // 同上
    {
        c[i * j] = min(c[i * j], c[i] + c[j]);
    }
}
for(int i = m - 1; i >= 1; i--)
{
    c[i] = min(c[i], c[i + 1]);    // 递增修补
}
for(int i = 2; i <= m; i++)
{
    for(int j = 2; j <= i; j++)    // std 写法和这种是等价的
    {
        if(i * j <= m)  continue;
        c[m + 1] = min(c[m + 1], c[i] + c[j]);
        break;    // 这样的操作只进行一次，可能是因为之前修补好了，避免超时
    }
}
for(int i = m; i >= 1; i--)        // 注意范围带上了 m
{
    c[i] = min(c[i], c[i + 1]);    // 递增修补
}

修补这个数组之后，我们还要做什么呢？由于这道题目没有一个很明显的贪心策略，动态规划的状态设置也会爆炸，我们就可以考虑 二分答案。

我们二分一个 v，如果这题要问最大值，那么我们就可以把 a 数组中的每个 a_i 全都刚好操作成小于等于 v 的最大数，因为这样最省钱，可以尽量多地操作。最后判断花费的钱是否小于 k 就行了。

现在的问题可以看成，找到一个最小的 u，使得 \lfloor \frac{a_i}{u} \rfloor \leq v。

这一块我也不会证明，感性理解一下，就是当 a_i \leq v 时 u = 1，当 v < a_i \leq 2v + 1 时 u = 2，以此类推，就可以得到 u = \lfloor \frac{a_i}{v + 1} \rfloor + 1。

现在要问中位数，该怎么操作呢？我们只需要修改数组中一半的元素（n / 2 + 1）就可以了。很明显，修改更小的一半肯定要比修改更大的一半更优。到这里，这道题就做完了。

伪代码如下：

bool check(long long v)
{
    long long sum = 0;
    for(int i = 1; i <= (n + 1) / 2; i++)    // 对于前一半元素
    {
        sum += c[a[i] / (v + 1) + 1];
        if(sum > k)  return false;    // 如果钱数已经超了，就退出
    }
    return true;
}

// 接上一部分代码
sort(a + 1, a + n + 1);  // 将 a 数组从小到大排序
l = 0, r = a[n];  // 整除最小可以除到 0，所以 l 得是 0
while(l <= r)
{
    mid = (l + r) / 2;
    if(check(mid))
    {
        ans = mid;
        r = mid - 1;
    }
    else
    {
        l = mid + 1;
    }
}

完整代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

long long n, m, k, l, r, mid, ans, a[500005], c[500005];

bool check(long long v)
{
    long long sum = 0;
    for(int i = 1; i <= (n + 1) / 2; i++)
    {
        sum += c[a[i] / (v + 1) + 1];
        if(sum > k)  return false;
    }
    return true;
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        scanf("%lld", &c[i]);
    }
    c[1] = 0;
    c[m + 1] = 1e18;
    for(int i = 2; i <= m; i++)
    {
        for(int j = 2; j <= i && i * j <= m; j++)
        {
            c[i * j] = min(c[i * j], c[i] + c[j]);
        }
    }
    for(int i = m - 1; i >= 1; i--)
    {
        c[i] = min(c[i], c[i + 1]);
    }
    for(int i = 2; i <= m; i++)
    {
        for(int j = 2; j <= i; j++)
        {
            if(i * j <= m)  continue;
            c[m + 1] = min(c[m + 1], c[i] + c[j]);
            break;
        }
    }
    for(int i = m; i >= 1; i--)
    {
        c[i] = min(c[i], c[i + 1]);
    }
    sort(a + 1, a + n + 1);
    l = 0, r = a[n];
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}