Educational Codeforces Round 164 (Rated for Div. 2)

by JiuQiin Codeforces, 题解on Posted on
“YE Irish lords, ye knights an’ squires, Wha represent our brughs an’ shires, An’ doucely manage our affairs In parliament,”
— Robert Burns · 88. The Author’s Earnest Cry and Prayer
首页 » 题解 » Codeforces » Educational Codeforces Round 164 (Rated for Div. 2)

一些废话

对于前三道没什么好说的，只是那个 BB 卡的实在太久，在赛时的时候，直到最后也没想通哪儿有问题，后来补题才发现，就一个地方，钻进牛角尖了，愣是没想到，太狭隘了，我只想到删除开头的部分或者末尾部分，而忘记了中间随机删除一部分都行。而这个 DD ，我也是懒得喷，凌晨三点写下的文字（卡常实在太恶心了）

我其实没打算补 EE，但是补 DD 的时候顺势瞄到了 EE，代码量少的令人兴奋。果不其然，大意了，没想象中简单，但也学到了一点东西

Contents hide
1 一些废话
2 A. Painting the Ribbon
2.1 题意
2.2 思路
2.3 代码
3 B. Make It Ugly
3.1 题意
3.2 思路
3.3 代码
4 C. Long Multiplication
4.1 题意
4.2 思路
4.3 代码
4.4 官方思路
4.5 官方代码
5 D. Colored Balls
5.1 题意
5.2 思路
5.3 代码
6 E. Chain Reaction
6.1 题意
6.2 思路
6.3 代码

A. Painting the Ribbon

题意

有一个大小为 nn 的数组，有 mm 种数字，每种数字无数多个，AliceAlice 可将这 mm 种数字填入到数组中，BobBob 最多可修改 kk 次，若 BobBob 最后能将该数组统一为一种数字，则 AliceAlice 失败，输出 NONO，否则，输出 YESYES

思路

对于 AliceAlice 来说，最优的填法是 1 2 3 4 . . . (m – 2) (m – 1) m 1 2 3 4 . . . (m – 2) (m – 1) m 1 2 3 . . . 直到填满 nn 个数，同一种数字最多出现 cnt=⌈nm⌉cnt = \left \lceil \frac{n}{m} \right \rceil 次，则 Bob Bob 至少要修改 （n−cnt）（n – cnt）次，该值与 kk 做个比较即可

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    int p = (n + m -1) / m;
    p = n - p;
    if (k >= p) {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Make It Ugly

题意

可以通过以下操作使其所有元素相同，则将该数组成为美丽数组：

  • 若 ai−1=ai+1a_{i – 1} = a_{i +1}，则删除掉 aia_i

给出一个美丽数组，问最少删除多少个元素，使得该数组不为美丽数组，若无法做到，则输出 −1-1

思路

  • 若给出的美丽数组只有一种元素，则直接输出 −1-1
  • a1=ana_1 = a_n 且最后若是所有元素相同，一定是等于 a1a_1 的

若 a1≠ana_1 \neq a_n ，若最后相同的元素不是 a1a_1，那 a1a_1 则永远无法消掉，因为我们只能左右两边相等，消去掉中间的，a1a_1 左边没有数字，所以 a1a_1 是消不掉的，ana_n 的处境与 a1a_1 同理。所以如果他们两不相等，那最后始终有一方是消不掉的，无法成为美丽数组，不，从一开始就不是美丽数组，与题干给出的条件，说一开始一定是美丽的相矛盾。后半部分也顺势证明了，因为 a1a_1 始终消不掉，所以若是美丽数组，则最后相同的元素一定是 a1a_1

  • 而中间（除开 a1,ana_1, a_n ）若是有不等于 a1a_1 的数字出现，一定是单个独立出现的

反证法，中间若是有不等于 a1a_1 的数字有两个及两个以上连续出现，那么他首先会被消掉剩余连续的两个，而这两个无论如何都无法被旁边等于 a[1] 的数字消掉，所以不是美丽的，与题干给出的一开始就是美丽的数组相矛盾

  • 所以，给出的美丽数组的形式大致是 x x x y x x z x x x x x y x y x x x z x x

只要选取连续 xx 的最短区间长度即可，因为只要删除一段 xx ，若删除的是中间某段，左右两端点不等于 xx 的数就会相邻，回到刚刚讨论的第三点，成为不美丽数组；若删除的第一段或最后一段，则回到讨论的第二点，成为不美丽数组

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n+ 1, 0);
    int lst = 0;
    int ans = n + 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] != a[1]) {
            ans = min(ans, i - lst - 1);
            lst = i;
        }
    }

    ans = min(ans, n + 1 - lst - 1);

    cout << (ans == n ? -1 : ans) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Long Multiplication

题意

给出两个长度相同的整数 x,yx, y，可任意交换 xi,yix_i, y_i，使得最后 x×yx \times y 的结果最大，输出 x,yx, y

思路

贪心{\color{Yellow}贪心}

列个竖式：

7331 73219  \begin{align*} 73 \\ 31\\ \hline \: \ 73 \\ 219 \: \:\ \:\ \end{align*}

7133213213  \begin{align*} 71 \\ 33\\ \hline 213 \\ 213 \:\ \:\ \: \end{align*}

对于第 ii 位可以试探性的交换一下，看交换前与交换后哪个与高位的乘积更大

比如，样例一，7373 和 3131，看个位是否交换，看第一个竖式，对于 3131 的 11 来说，他的贡献其实是 70×1+3×1270 \times 1 + \frac{3 \times 1}{2} ，对于 7373 的 33 来说，他的贡献是 30×1+1×3230 \times 1 + \frac{1 \times 3}{2}，交不交换对于个位来说都是相同的贡献，所以可以不用看，只用看高位即可，所以，对于第一个竖式，个位的贡献是 70+30=10070 + 30 = 100。看第二个竖式，对于 3333 的个位的 33 来说，其贡献是 70×370 \times 3，对于 7171 的 11 来说，其贡献是 30×130 \times 1 ，所以该组合个位的贡献是 210+30=240>100210 + 30 = 240 > 100，所以，个位交换更好

这是仅针对于个位来说，讨论第 ii 位是否交换，设最高位为 nn ，则从 nn 到 i+1i + 1 位去试探，看交换前后哪个乘积之和更大，只要不相等就立马判断是否交换，然后退出，判断下一位。时间复杂度是 O(n2)O(n^2)，n=100,t=1000n = 100, t = 1000，最后大约是 1e71e7 级别

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size();

    for (int i = 0; i < n; ++i) {
        if (s[i] == t[i]) {
            continue;
        }
        int x = s[i] - '0';
        int y = t[i] - '0';
        for (int j = 0; j < i; ++j) {
            int a = s[j] - '0';
            int b = t[j] - '0';
            int c = x * b + y * a;
            int d = x * a + y * b;
            if (c != d) {
                if (c < d)
                    swap(s[i], t[i]);
                break;
            }
        }
    }

    cout << s << endl;
    cout << t << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

官方思路

我们知道，对于两个和一定的数来说，他们的差值越小，乘积越大，证明：

x+y=s,x=s2−a,y=s2+a⇒x×y=(s2)2−a2x + y = s, \quad x = \frac{s}{2} -a, \quad y = \frac{s}{2} +a \\\Rightarrow x \times y = (\frac{s}{2})^2 – a^2

我们让 x>yx > y，在第一次 xi≠yix_i \neq y_i 时，保证 xi>yix_i > y_i，之后的所有都让 xi<yix_i < y_i 即可

官方代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    string x, y;
    cin >> x >> y;
    int n = x.size(), f = 0;

    for (int i = 0; i < n; ++i) {
        if ((x[i] > y[i]) == f) {
            swap(x[i], y[i]);
        }
        f |= (x[i] != y[i]);
    }

    cout << x << '\n'
         << y << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. Colored Balls

题意

有 nn 个颜色的球，每种球有 aia_i 个，各种球之间可以相互组合，共有 2n2^n 种组合，每个组最多有两个球，同一种颜色的球不能在同一组，每种组合的组数定义为最小的满足要求的组数，问， 2n2^n 种组合的组数之和为多少，对 998244353998244353 取余

思路

动态规划{\color{Yellow}动态规划}

抛开其他的，单纯的从题干入手。对于 aia_i 来说，在包含他的组合里面如何计算一种组数和？

若其余颜色的个数之和都小于等于 aia_i，则答案为 aia_i; 若其余颜色的个数之和大于 aia_i，则答案为其余颜色的个数之和加上 aia_i 再除以 22，对吗？不对，前半部分没问题，但是后半部分，若在其余颜色的个数中有大于 aia_i 的存在呢，也就是说，若所选球类的最大值不是 aia_i 呢？而这个最大值刚好大于其余颜色的球的个数之和，则答案为这个最大值，所以，一切都是在 aia_i 为所选球类的最大值的基础上进行的。而怎么确保 aia_i 为选择的最大值，将数组 aa 从小到大排序，当讨论到 aia_i 的时候，一定是所选球类的最大值

而现在就分为两部分，一部分为剩余个数小于等于 aia_i 的方案数，对答案的贡献 = 方案数 × ai\times \ a_i，另一部分为剩余个数大于 aia_i 的球数和，即选择 aia_i 的总球数和，对答案的贡献 =⌈总球数和2⌉ \left \lceil \frac{总球数和}{2}\right \rceil，两部分的侧重点不一样，但是都要获取到，我们知道，方案数是可达到 2n2^n ，所以不可能将其设为状态，只能设置为结果，状态自然而然就出来了

  • 状态

dp[i][j][k]dp[i][j][k] ：轮到第 ii 种球，选择了 jj 个，（k=0k = 0 为不选第 ii 种球，反之则选）的方案数

  • 转移

若不选第 ii 种球：

dp[i][j][0]→dp[i−1][j][0]+dp[i−1][j][1]dp[i][j][0] \to dp[i – 1][j][0] + dp[i – 1][j][1]

若选第 ii 种球：

  • 若其余球数小于等于 ai⇔ai≤j≤2 ˙aia_i \Leftrightarrow a_i \leq j \leq 2 \.\ a_i:

dp[i][j][1]+=dp[i−1][j−a[i]][0]+dp[i−1][j−a[i]][1]dp[i][j][1] += dp[i – 1][j – a[i]][0] + dp[i – 1][j – a[i]][1]

ans+=dp[i][j][1]×a[i]ans += dp[i][j][1] \times a[i]

  • 若其余球数大于 ai⇔2 ˙ai<j≤5000a_i \Leftrightarrow 2 \.\ a_i < j \leq 5000

dp[i][j][1]+=dp[i−1][j−a[i][0]+dp[i−1][j−a[i]][1]dp[i][j][1] += dp[i – 1][j – a[i][0] + dp[i – 1][j – a[i]][1]

ans+=(j+1)/2ans += (j+1) / 2

对了，我写的时候省去了一维，我用两个滚动数组代替

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

int dp[5005][2], ndp[5005][2];

int add(int x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
    return x;
}

int mul(int x, int y) {
    return x * 1LL * y % MOD;
}

void solve() {
    int n;
    cin >> n;

    vector<int> a(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    sort(a.begin() + 1, a.end());

    int ans = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        memset(ndp, 0, sizeof(ndp));
        for (int j = 0; j <= 5000; ++j) {
            ndp[j][0] = add(dp[j][0], dp[j][1]);
        }
        for (int j = a[i]; j <= min(2 * a[i], 5000); ++j)
        {
            ndp[j][1] = add(ndp[j][1], dp[j - a[i]][0]);
            ndp[j][1] = add(ndp[j][1], dp[j - a[i]][1]);
            ans = add(ans, mul(ndp[j][1], a[i]));
        }
        for (int j = min(a[i] * 2, 5000) + 1; j <= 5000; ++j) {
            ndp[j][1] = add(ndp[j][1], dp[j - a[i]][0]);
            ndp[j][1] = add(ndp[j][1], dp[j - a[i]][1]);
            ans = add(ans, mul(ndp[j][1], ((j + 1) / 2)));
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E. Chain Reaction

题意

有 n 个怪物排成一排，第 i 个怪物的生命值为 a_i，你可以任意对活着的怪物产生攻击，攻击范围为从该怪物起向左右分别扩展，直到遇到死去的怪物或者 a_1, a_n 就停止，该范围内的怪物都减少 k 的生命值，该攻击花费一秒。问，k 从 1 到 max(a_1, a_2, . .. a_n) 的每个 k，杀死所有怪物的最少秒数

思路

我先说，我是怀着及其虔诚的态度写下以下文字的，我尽量阐述清楚，但只能是尽量。因为我刚刚录了个视频讲解，我发现，很难讲清楚，我不知道换个形式会不会好一点

讨论当 k = 1 时，此时攻击任何一个怪兽都是等价的，所有怪兽都会减少 1 生命值，若没有怪兽死去，你仍可以攻击任意一个怪兽，持续此操作，直到有怪兽死亡，而死亡的怪兽会将整个区间划分为更小的，全是活着的怪兽区间，对于一个活着的独立区间，攻击该区间任意一个怪兽都是等价的，都会使该区间的怪兽减小 1 生命值，同样，持续此操作，直到出现新的怪兽死去。通过此操作，发现，攻击怪兽的顺序并不重要，你攻击任意一个区间中的任意一个，对于这个区间来说都是等价的，你先攻击哪个区间，对于最后的答案来说也是没有影响的

既然攻击怪兽的顺序对答案没有影响，那么我们就按从左到右一依次攻击。先攻击第一个怪兽，花费 a_i 秒。攻击第二个怪兽，若第二个怪兽的生命值小于等于第一个，那他就免费了，无需花费额外的秒数，若第二个怪兽的生命值大于第一个，则花费 a_2 – a_1 秒。攻击第三个怪兽，若第三个怪兽的生命值小于等于第二个，那他也免费了，若是大于的话，则会额外花费 a_3 – a_2 的秒数，无论第一个怪兽的生命值是多少：若是第一种情况，则在第二个怪兽死去的时候就停止向右传播了，第三个怪兽只能免费 a_2 秒；若是第二种情况，则在第一个怪兽死去的时候，第三个怪兽会免费 a_1 秒，在第二个怪兽死去的时候，第三个怪兽又会免费 a_2 – a_1 秒，整体看来，在第二个怪兽死去后，对于第三个怪兽来说，都会免费 a_2 秒，则额外花费 a_3 – a_2 秒，那第三个怪兽的处境等同于刚刚第二个怪兽的处境，归纳得出：ans=∑i=1nmax(0,ai−ai−1)ans =\sum_{i =1}^n max(0, a_i – a_{i-1})

以上是针对于 k = 1 的情况，而 k 等于其余数也是类似，当 a_{i-1} < a_i 时，对于 a_{i-1} 来说，要让他死亡需花费 ⌈ai−1k⌉\left \lceil \frac{a_{i-1}}{k} \right \rceil 秒，而要让 a_i 死亡，需花费 ⌈aik⌉\left \lceil \frac{a_i}{k}\right \rceil 秒，a_{i-1} 可以让 a_i 免费 ⌈ai−1k⌉\left \lceil \frac{a_{i-1}}{k} \right \rceil 秒，所以，对于 a_i 来说，他的花费是 ⌈aik⌉−⌈ai−1k⌉\left \lceil \frac{a_i}{k}\right \rceil – \left \lceil \frac{a_{i-1}}{k} \right \rceil 秒。而当 a_{i-1} \geq a_i 时，a_i 仍是可以免费的，所以，对于 k 更一般的情况：ans=∑i=1nmax(0,⌈aik⌉−⌈ai−1k⌉)ans = \sum_{i = 1}^n max(0, \left \lceil \frac{a_i}{k}\right \rceil – \left \lceil \frac{a_{i-1}}{k} \right \rceil)

现在的问题是，若我们固定 kk ，去扫描一遍数组 aa，时间复杂度是 O(n)O(n)，而 k∈[1,mx]k \in [1, mx] ，整体时间复杂度就是 O(n2)O(n^2)。若我们固定 aia_i ，先获取到他的系数 cic_i ，时间复杂度是 O(n)O(n)，然后去遍历 kk ，将 kk 加上其对应的 ci ˙⌈aik⌉c_i \.\ \left \lceil \frac{a_i}{k} \right \rceil，时间复杂度是 O(n)O(n)，而 aa 的范围是 [1,n][1, n] ，时间复杂度也是 O(n2)O(n^2)。

整除分块{\color{Yellow}整除分块}

我不希望你把它看成是一种算法，这更像是一种通过找规律总结出来的解题技巧

举个栗子：⌈ak⌉=x, a=20 \left \lceil \frac{a}{k} \right \rceil = x, \ a = 20

这里的 “/” 都指的是向上取整
k = 1, 20 / 1 = 20

k = 2, 20 / 2 = 10

k = 3, 20 / 3 = 7

k = 4, 20 / 4 = 5

k = 5, 20 / 5 = 4
k = 6, 20 / 6 = 4

k = 7, 20 / 7 = 3
k = 8, 20 / 8 = 3
k = 9, 20 / 9 = 3

k = 10, 20 / 10 = 2
k = 11, 20 / 11 = 2
k = 12, 20 / 12 = 2
k = 13, 20 / 13 = 2
k = 14, 20 / 14 = 2
k = 15, 20 / 15 = 2
k = 16, 20 / 16 = 2
k = 17, 20 / 17 = 2
k = 18, 20 / 18 = 2
k = 19, 20 / 19 = 2

k = 20, 20 / 20 = 1
k = 21, 20 / 21 = 1
k = 22, 20 / 22 = 1
......
k = mx, 20 / mx = 1

我们发现一个规律：

k∈[⌈ax⌉, ⌈ax−1⌉) k \in [ \left \lceil \frac{a}{x}\right \rceil , \ \left \lceil \frac{a}{x-1}\right \rceil )

确定 a,xa, x, 可推出 kk 的范围，用差分将该范围整体加上 xx，最后做一个前缀和即为答案

首先，令 r=mxr = mx,

r=mx→x=⌈20mx⌉=1,l=⌈201⌉=20→[20,mx]+1r = mx \to x = \left \lceil \frac{20}{mx} \right \rceil = 1, l = \left \lceil \frac{20}{1}\right \rceil = 20 \to [20,mx] +1

r=l−1=19→x=⌈2019⌉=2,l=⌈202⌉=10→[10,19]+2r = l – 1 = 19 \to x = \left \lceil \frac{20}{19} \right \rceil = 2, l = \left \lceil \frac{20}{2}\right \rceil = 10 \to [10, 19] +2

r=l−1=9→x=⌈209⌉=3,l=⌈203⌉=7→[7,9]+3r = l – 1 = 9 \to x = \left \lceil \frac{20}{9} \right \rceil = 3, l = \left \lceil \frac{20}{3}\right \rceil = 7 \to [7,9] + 3

r=l−1=6→x=⌈206⌉=4,l=⌈204⌉=5→[5,6]+4r = l – 1 = 6 \to x = \left \lceil \frac{20}{6} \right \rceil = 4, l = \left \lceil \frac{20}{4}\right \rceil = 5 \to [5,6] + 4

r=l−1=4→x=⌈204⌉=5,l=⌈205⌉=4→[4,4]+5r = l – 1 = 4 \to x = \left \lceil \frac{20}{4} \right \rceil = 5, l = \left \lceil \frac{20}{5}\right \rceil = 4 \to [4, 4] +5

r=l−1=3→x=⌈203⌉=7,l=⌈207⌉=3,→[3,3]+7r = l – 1 = 3 \to x = \left \lceil \frac{20}{3} \right \rceil = 7, l = \left \lceil \frac{20}{7}\right \rceil = 3 , \to [3, 3] +7

r=l−1=2→x=⌈202⌉=10,l=⌈2010⌉=2,→[2,2]+10r = l – 1 = 2 \to x = \left \lceil \frac{20}{2} \right \rceil = 10, l = \left \lceil \frac{20}{10}\right \rceil = 2 , \to [2,2] +10

r=l−1=1→x=⌈201⌉=20,l=⌈2020⌉=1,→[1,1]+20r = l – 1 = 1 \to x = \left \lceil \frac{20}{1} \right \rceil = 20, l = \left \lceil \frac{20}{20}\right \rceil = 1 , \to [1,1] +20

t=l−1=0,ENDt = l – 1 = 0, \\ END

总结归纳：

r=l−1→x=⌈ar⌉=x,l=⌈ax⌉,→[l,r]+xr = l – 1 \to x = \left \lceil \frac{a}{r} \right \rceil = x, l = \left \lceil \frac{a}{x}\right \rceil , \to [l,r] +x

为什么？

我那有限的数学功底不允许我来解释为什么，我只能通过找规律找出该结论。所以时间复杂度我也不大会算，但是你如果想知道的话，去找整除分块的时间复杂度的算法，这个和那个是等价的，其实这个你也可以看成是当 k≤ak \leq \sqrt a 计算的次数取决于 kk，当 k>a, x ˙k=a, x<ak > \sqrt a , \:\ x\.\ k = a, \;\ x < \sqrt a，计算的次数取决于 xx，所以，整体的时间复杂度是 O(2a)O(2 \sqrt a)，算一次 aia_i 是这么多， nn 个 aia_i 的时间复杂度是 O(nA)O(n \sqrt A)。呃，我怎么说完了，好吧好吧，我还是建议你去搜一下

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e5 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n;
    cin >> n;

    vector<LL> a(n + 1, 0);

    LL mx = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    vector<LL> ans(MAX, 0);

    auto divup = [](LL x, LL y)
    {
        return (x + y - 1) / y;
    };

    auto work = [&](LL a, LL coef)
    {
        LL r = a;
        ans[r] += coef;
        --r;
        while (r > 0) {
            LL val = divup(a, r);
            LL l = divup(a, val);
            ans[l] += coef * val;
            ans[r + 1] -= coef * val;
            r = l - 1;
        }
    };

    for (LL i = 1; i <= n; ++i) {
        if (a[i] <= a[i - 1])
            continue;
        LL v = a[i - 1];
        LL u = a[i];
        work(v, -1);
        work(u, 1);
    }

    ans[0] = 0;
    for (LL i = 1; i  <= mx; ++i) {
        ans[i] += ans[i - 1];
        cout << ans[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注