题解I

Problem - 2144D - Codeforces

Background

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

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

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

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

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

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

这个算法复杂度为$O\left(\lceil \frac{n}{x}\rceil \right)$

那对于这一题我们就可以枚举分母$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\cdots 910111213\cdots$中求出第$k$个下标前所有数的总和

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

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

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

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

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

计算数位之和不能使用常规思路,否则会超时,这里介绍一种计算$\sum _{i=1}^{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 << " ";
    }
}

1057-D

这是一道DP，我们的目标是将所有的元素在环形数组中左右至少有一个元素与其相邻，我们每次的操作可以将任意一个元素+1 or -1

我们注意两种可行的操作

• 将元素$a_i,a_{i+1}$变为一致的
• 将元素$a_i,a_{i+1},a_{i+2}$变为一致的

我们设计这样一个dp，其中dp[i]表示复原前i个所需要的最小代价

那么根据我们上面的可行操作设计两种状态转移

• dp[i + 2] = min(dp[i + 2],dp[i] + cost)
• dp[i + 3] = min(dp[i + 3],dp[i] + cost)
• 其中cost是上面两种操作所花费的cost 同时我们需要注意由于是环状数组，所以我们需要向后偏移三次实现最后面和开始的计数

现在我们来论证为什么是这两个操作

• 对于操作1,实际上是将数组分为2个2个的块，保证每个块都是相等的
• 对于操作2,实际上保证的3个的块是相等的
  • 对于更多的如(4个，5个)，都可以通过操作2和操作3叠加而来

AC Solution

void solve()
{
    i64 n;
    cin >> n;
    vint a(2 * n + 2);
    for (i64 i = 1; i <= n; i++) {
        i64 num;
        cin >> num;
        a[i] = num, a[n + i] = num;
    }
    i64 ans = 1e18;
    auto clac = [](i64 a, i64 b, i64 c) { return max({a, b, c}) - min({a, b, c}); };
    for (i64 l = 1; l <= 3; l++) {
        vint dp(n + 1, 1e18);
        dp[0] = 0;
        for (i64 i = 0; i < n; i++) {
            if (i + 2 <= n) {
                i64 cost = abs(a[i + l] - a[i + 1 + l]);
                dp[i + 2] = min(dp[i + 2], dp[i] + cost);
            }
            if (i + 3 <= n) {
                i64 cost = clac(a[l + i], a[l + i + 1], a[l + i + 2]);
                dp[i + 3] = min(dp[i + 3], dp[i] + cost);
            }
        }
        ans = min(ans, dp[n]);  
    }
    cout << ans << endl;
}

1043-E

神秘题目:

给定一个数组，问你删去$0\sim k$ 个数情况下MEX的可能的值有多少种

我们考虑MEX(v) = $m$ 时候的情况，即 $0\sim m-1$至少出现一次，同时 $m$ 必须不存在

接着我们考虑删除 $k$ 个数的影响

我们删除$k$个数后，可能的MEX取决于

• 我们不能清空某个值出现的情况
• 可以保留某一个区间的完整性

我们利用差分数组来计算答案，从删去freq[i]开始，MEX = $i+1$ 的情况，由于删除的元素最多为$n$个，所以区间的右端为n - i + 1

特别的，当出现freq[i] == 0时候，表示MEX最多到i，之后不会继续

$ans$数组是diff数组的前缀

AC solution

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
using i64 = long long;
using i128 = __int128;
using vint = vector<i64>;
using vvint = vector<vint>;
using vstr = vector<string>;
using pii = pair<i64, i64>;
using vpii = vector<pii>;
template <typename T>
using vec = vector<T>;
const constexpr i64 MOD = 998244353;
 
void solve()
{
    i64 n;
    cin >> n;
    vint v(n);
    map<i64, i64> freq;
    for (i64 i = 0; i < n; i++) {
        cin >> v[i];
        freq[v[i]]++;
    }
    vint diff(n + 2);
    for (i64 i = 0; i <= n; i++) {
        diff[freq[i]]++;
        diff[n - i + 1]--;
        if (!freq[i]) break;
    }
    vint ans(n + 2, 0);
    for (i64 i = 0; i <= n; i++) {
        ans[i] = diff[i];
        if (i != 0) {
            ans[i] += ans[i - 1];
        }
    }
    for (i64 i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
 
    cout << endl;
}
 
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(2);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}