题解I --from imicola

Problem - 2144D - Codeforces

Background

给定一个数组 $A$ 和两个整数 $k, x$ 其中 $x > 1$ 你需要求出 $i = 1 \sum n - 1 ⌈ \frac{a _{i}}{x} ⌉$ ,同时 $k$ 表示 $a_{i}$ 变为 $⌈ \frac{a _{i}}{x} ⌉$ 后需要的代价,但是如果原本的数组中存在元素 $⌈ \frac{a _{i}}{x} ⌉$ 就不用付出代价,你的任务是最大化 $i = 1 \sum n - 1 ⌈ \frac{a _{i}}{x} ⌉ - q$ 其中q代表付出的总代价

我们最核心需要解决的问题是解决题目的求和式子,对于这个式子,我们可以将其映射到[1 - n]长度数组中,这样方便我们进行下面的整除分块

同时这是一个变形的整除分块问题,与一般整除分块的分子分母呈反关系,我们来研究这个式子

对于 $i = 1 \sum n ⌈ \frac{i}{x} ⌉$ 有固定x,其值一定是类似 $11122 \dots$ 上升的,而对于每个块的长度,不难看出都是 $x$

有了块长,块值,我们可以这样书写这个代码

for(i64 l = 1,k = 1;l <= n;l += x,k++){
	i64 r = max(n,l + x - 1);
	// k是整除数
	// x是当前分母
}

这个算法复杂度为 $O (⌈ \frac{n}{x} ⌉)$

那对于这一题我们就可以枚举分母 $x$ 然后对每个分母求和进行整除分块,同时我们前面映射到连续[1 - n]的cnt数组也是方便我们进行分块

AC solution

void solve()
{
    i64 n, k;
    cin >> n >> k;
    vint c(n);
    vint cnt(2e5 + 10);
    i64 maxnum = -1;
    // cout << mp[0] << endl;
    for (i64 i = 0; i < n; i++) {
        cin >> c[i];
        cnt[c[i]]++;
        maxnum = max(maxnum, c[i]);
    }
    i64 ans = LLONG_MIN;
    if (maxnum == 1) {
        cout << n << endl;
        return;
    }
    vint pre(maxnum + 10);
    for (i64 i = 1; i <= maxnum; i++) {
        pre[i] = pre[i - 1] + cnt[i];
    }
    for (i64 x = 2; x <= maxnum + 1; x++) {
        i64 kk = 0;
        i64 p = 0;
        for (i64 l = 1, op = 1; l <= maxnum; l += x, op++) {
            // op 整除数
            i64 r = min(l + x - 1, maxnum);
            if (l > r) continue;
            // 块长 
            i64 LR = r - l + 1;
            // 块内容
            i64 k2 = pre[r] - pre[l - 1];
            // 块贡献
            p += k2 * op;
            kk += (cnt[op] >= k2 ? k2 : cnt[op]);
        }
        ans = max(ans, p - max(0ll, n - kk) * k);
    }
    cout << ans << endl;
}

Problem - D - Codeforces

backgrounds

我们需要从一个无穷序列 $12345 \dots 910111213 \dots$ 中求出第 $k$ 个下标前所有数的总和

一个很麻烦的数学与数论模拟

我们的主要思路是求出 $k$ 下标代表的数然后求和前面所有数的数位和然后加上自身的剩余的数字

对于这个无穷数列,我们可以将其看作是多个数块

1数块,由 [1,9] 构成,每个数1位,一共占据9个位置
2数块,由 [10,99] 构成,每个数占2位,一共占据 $90 \times 2 = 180$ 个位置
d数块,由 [ $1 0^{d - 1}, 1 0^{d} - 1$ ] 构成,每个数占 $d$ 位,一共占据 $9 \times 1 0^{d - 1} \times d$ 个位置

我们需要确定 $k$ 处于第几个数块之中,然后将 $k$ 所属数块前的所有数块的数位和加起来,最后再计算 $k$ 所处的不完整数块的和,并且相加

计算数位之和不能使用常规思路,否则会超时,这里介绍一种计算 $i = 1 \sum n d (i)$ 的思路

Important

当我们计算 $d (i)$ 时候我们可以按照数位的贡献来计算,例如计算 $d (114)$

个位数的贡献:

从 [1 , 110] 0~9完整的循环了11次,其和为11*45

从 [111,114] 有1 2 3 4,和为10

十位数的贡献:

从 [1,99] 0~9 在100个数中完整循环1次,和为1*10*45

从 [100,110] 有和为10

以此类推迭代

solution

unordered_map<i64, i64> mp;
i64 f(i64 n)
{
    if (mp.contains(n)) return mp[n];
    if (n < 10) return n * (n + 1) / 2;
    string s = to_string(n);
    i64 d = s.size();
    i64 p = 1;
    for (i64 i = 0; i < d - 1; i++) {
        p *= 10;
    }
    // 第一个数位
    i64 d1 = n / p;
    i64 res = 1;
    res = d1 * f(p - 1)             // 这部分计算 0-99, 100-199, 200-299 中除了最高位之外的数字和
          + (d1 * (d1 - 1) / 2) * p // 这部分计算最高位的和，例如 100-199 的最高位'1'，200-299的最高位'2'
          + d1 * (n % p + 1)        // 这部分计算当前最高位的和,例如 300-345 的最高位'3'
          + f(n % p);               // 这部分计算末尾不完整部分
 
    mp[n] = res;
    return res;
};

有了解决方案就可以按我们说的方法去写代码了,代码写起来还是很考验代码力的

AC Solution

void solve()
{
    i64 k;
    cin >> k;
    i64 sum = 0, d = 1, cnt = 9, pow10 = 1;
    while (1) {
        // 第几个数块
        i64 d_block = d * cnt;
        if (k > d_block) {
            k -= d_block;
            i64 l = pow10, r = pow10 * 10 - 1;
            sum += f(r) - f(l - 1);
            // 更新到下一个块
            d++;
            cnt *= 10;
            pow10 *= 10;
        }
        else
            break;
    }
    i64 num = (k - 1) / d;
    if (num > 0) {
        i64 l = pow10, r = l + num - 1;
        sum += f(r) - f(l - 1);
    }
    i64 last = (k - 1) % d + 1;
    i64 pnum = pow10 + num;
    string pnums = to_string(pnum);
    for (i64 i = 0; i < last; i++) {
        sum += (pnums[i] - '0');
    }
    cout << sum << endl;
}

2139 C

被初见杀了，主要思路是从结果出发，将题目限定条件带入就能得到正解

这类题的特点是正常往下进行会有很多支路，但是从结果出发就会发现只有一条路径走向结果

AC solution

void solve()
{
    i64 k, x;
    cin >> k >> x;
    i64 have = (1ll << k);
    i64 sum = have * 2;
    i64 b = sum - x;
    i64 cnt = 0;
    vint res;
    while (x != have) {
        if (x * 2 > sum) {
            x -= b;
            b *= 2;
            res.emplace_back(2);
        }
        else if (x * 2 < sum) {
            b -= x;
            x *= 2;
            res.emplace_back(1);
        }
    }
    ranges::reverse(res);
    cout << res.size() << endl;
    for (auto &&i : res) {
        cout << i << " ";
    }
    cout << endl;
}

Problem - 2149E - Codeforces

Note

想要实现这个，其实可以用容斥差分来写
对于目标:正好到 $k$ 个可以分解为

最多有 $k$ 个

最多有 $k - 1$ 个

我们令 $G (k, t)$ 表示最长为 $t$ 的子区间中最多有 $k$ 个的情况，那么我们的答案即可表示为：

G (k, r) - G (k, l - 1) - G (k - 1, r) + G (k - 1, l - 1)

对于每一个情况，我们采用滑动窗口的形式来解决问题

AC solution

void solve()
{
    i64 n, k, l, r;
    cin >> n >> k >> l >> r;
    vint a(n);
    for (i64 i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 我们统计最多为k and k - 1 的区间然后相减
    // 做一次容斥差分
    auto f = [&](i64 x, i64 len) -> i64 {
        if (x < 0 || len <= 0) return 0;
        map<i64, i64> freq;
        i64 dis = 0;
        i64 res = 0;
        i64 L = 0;
        for (i64 R = 0; R < n; R++) {
            freq[a[R]]++;
            if (freq[a[R]] == 1) {
                dis++;
            }
            // 保证元素数小于k
            while (dis > x) {
                freq[a[L]]--;
                if (freq[a[L]] == 0) dis--;
                L++;
            }
            // 保证长度小于len
            while (R - L + 1 > len) {
                freq[a[L]]--;
                if (freq[a[L]] == 0) dis--;
                L++;
            }
            // 以R为右端点的合法区间数
            res += R - L + 1;
        }
        return res;
    };
 
    i64 ans = f(k, r) - f(k, l - 1) - f(k - 1, r) + f(k - 1, l - 1);
    cout << ans << endl;
}

Problem - 1095C - Codeforces

贪心 + 二进制拆分

这题思路想出来不难，但是对于代码力有一定要求

我们不难发现，对于这个k符合的条件应该是小于数 $n$ 且大于 $n$ 的二进制中1的数量

那我们就按照这个思路，记录有多少个1,并且拆分这些1,具体来说，对于一个二次幂数 $2^{p}$ ，我们可以拆成 $2 \cdot 2^{k - 1}$ 这样使用的1就增加了一个，我们的目标是使用 $k$ 个1

Ac solution

void solve()
{
    i64 n, k;
    cin >> n >> k;
    i64 p = __builtin_popcountll(n);
    if (k > n || k < p) {
        cout << "NO" << endl;
        return;
    }
    vint cnt(64, 0);
    for (i64 i = 0; i < 63; i++) {
        if ((n >> i) & 1) cnt[i]++;
    }
    i64 cur = p;
    while (cur < k) {
        i64 i = 62;
        for (; i >= 0; i--) {
            if (cnt[i] > 0) break;
        }
        cnt[i]--;
        cnt[i - 1] += 2;
        cur++;
    }
    vint ans;
    for (i64 i = 0; i < 63; i++) {
        while (cnt[i] > 0) {
            ans.emplace_back(1ll << i);
            cnt[i]--;
        }
    }
    cout << "YES" << endl;
    for (auto &&i : ans) {
        cout << i << " ";
    }
}

imicola's Blog

探索

题解I

Problem - 2144D - Codeforces

Problem - D - Codeforces

2139 C

Problem - 2149E - Codeforces

Problem - 1095C - Codeforces

关系图谱

目录