0

PKUSC2021题解

 1 month ago
source link: https://blog-e.tk/2022/05/16/PKUSC2021%E9%A2%98%E8%A7%A3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题意

k=0k=0k=0 不难,略。

一个显然的想法是枚举断掉的边,然后看每条边的贡献。

贡献分为两类,一类是新加的边的块间贡献:

6281dac60947543129099dfa.jpg

这个不难算,另外一类是原先的边的块内贡献。

6281daf809475431290a5279.jpg

不妨设虚线边断开,实线边把一个连通块分为大小为 a,ba,ba,b 的两块,则这条实线边的贡献是上面的式子。

于是在枚举了虚线边之后,分子树内,祖先,既非子树也非祖先三种情况讨论,不妨设 a 是虚线边较深的端点,b 是实线边较深的端点:

6281db9809475431290c57a7.jpg

可以发现,三个贡献的式子后两项都只和 a 有关,前两项都可以展开成和 b 有关的二次多项式,因此只需要维护下子树内,祖先上的 sz 的和,sz 的平方之和即可快速计算。

代金券题解

题面

与值域无关做法——贪心

做如下的一个转化,可以看成有三种操作:

  1. 支付 1 个代金券
  2. 支付 1 块钱
  3. 支付 c 块钱,并在吃下一道菜的时候获得一个代金券

用最少的钱等价于用最多的代金券,可见必然存在有如下特征的最优解:

  • 有代金券时不可能进行操作 2(代金券越靠前使用越好,否则后面可能没机会用了)
  • 3 操作必定越靠前越好(感性理解是提前获得了代金券,使用的机会更多了,还把使用代金券的空位向后移动了):
  • 如果 当前代金券的数量+c>剩下所要支付的钱数当前代金券的数量+c>剩下所要支付的钱数当前代金券的数量+c>剩下所要支付的钱数,则不会进行操作 3。不仅这次获得的代金券用不上,还浪费了一次用代金券的机会。

不妨设在第 iii 道菜上进行过操作 3,在第 j(j<i)j(j<i)j(j<i) 道菜上进行过 ≥c\ge c≥c 次 1,2 操作。 那么把这 ccc 次操作移到第 iii 道菜上进行,并把第 iii 道菜上进行的操作 3 换到第 jjj 道菜上进行,答案不变。

形象的来说,最优解中,存在一个 iii 使得编号小于 iii 的菜品是“尽可能进行 3,然后再尽可能用 1,最后再用 2”(后文称为 “贪心策略”),而编号大于 iii 的菜品都全用代金券支付。

现在的问题在于:

  • 如何找出 iii

iii 必然是第一个满足:<i的菜品剩下代金券+[Aic]≥∑j>iAj<i的菜品剩下代金券+[\frac{A_i}c]\ge \sum_{j>i}A_j<i的菜品剩下代金券+[cAi​​]≥∑j>i​Aj​ 的位置,不难看出,符合条件的位置是一个后缀,因此如果我们能查询到贪心完每个前缀剩下的代金券数,我们就能二分求出 iii 的位置,但是不太好维护,后面再说。

  • 第 iii 道菜的策略

首先,如果前面剩下的代金券还不够把后面的菜全卖掉,那么就必须先用若干次操作 3 补齐代金券。

然后,如果第 iii 道菜剩下的钱数还大于 c+1c+1c+1,则可以进行若干次操作 3,尽可能多的把从前面传过来的代金券截胡,然后用第 i 道菜产生的代金券去吃后面的菜。

具体不太好说,看代码吧。

贪心代码:

ll solve() {
    for (ll i = n; i; i--) sum[i] = sum[i + 1] + arr[i];
    ll ans = 0;
    for (ll i = 1, cur = 0; i <= n; i++) {
        if (cur + arr[i] / c >= sum[i + 1]) {
            /* cerr << i << " " << cur << nl; */
            ll _arr = arr[i];
            if (cur >= sum[i + 1]) {
                ans += cur;
                cur -= sum[i + 1];
                _arr -= cur;
                ans += min(_arr / (c + 1), sum[i + 1]);
            } else {
                //补齐代金券
                _arr -= c * (sum[i + 1] - cur);
                //尽可能多地截胡前面传过来的代金券
                ans += sum[i + 1] + min(_arr / (c + 1), cur);
            }
            return sum[1] - ans;
        }
        ans += min(cur, arr[i] % c);
        cur = cur - min(cur, arr[i] % c) + arr[i] / c;
    }
    return -1;
}

复杂度 O(qn)O(qn)O(qn),拼几个特殊性质,就能喜提 50 左右的好成绩。

上数据结构

难点在于在修改过程中维护前缀贪心剩下的代金券数,当时考场上就是没想出来这个,就寄了。官方题解中的维护方法没太搞懂,网上找到一种硬维护的做法。

线段树节点上记三个数 div,mod,usediv,mod,usediv,mod,use 分别表示区间内所有数除 ccc 下取整之和(也就是能产生的代金券个数),模 ccc 之和(也就是最多能使用的代金券个数),以及在初始没有代金券的情况下用贪心策略,会用掉几个代金券。

然后你神奇的发现,这个东西是可以合并的:

node operator+(const node &x, const node &y) {
    return {x.div + y.div, x.mod + y.mod, x.use + y.use + min(y.mod - y.use, x.div - x.use)};
}

前两项显然,解释下第三项咋合并的,x.use + y.use 也是显然的,而 min(y.mod - y.use, x.div - x.use) 表示左边一半用剩下的代金券数量,和右边一半最多能使用的代金券个数取 min。

于是线段树二分即可。

这里有个细节,之前我们说的 iii 是满足 <i的菜品剩下代金券+[Aic]≥∑j>iAj<i的菜品剩下代金券+[\frac{A_i}c]\ge \sum_{j>i}A_j<i的菜品剩下代金券+[cAi​​]≥∑j>i​Aj​ 的第一个,但是如果线段树二分的时候这么写会非常麻烦。经过对拍验证,在上述对 iii 的构造方法下,把条件换成 ≤i的菜品剩下代金券≥∑j>iAj\le i的菜品剩下代金券\ge \sum_{j>i}A_j≤i的菜品剩下代金券≥∑j>i​Aj​ 也是正确的,虽说和原来的定义不太一样,有时候找到的 iii 和原来的 iii 不一样,但是最后构造的答案好像也对,手玩几个小样例似乎是可以互相调整的,但是不太会证明。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nl = '\n';
const ll MXN = 3e5 + 5;
ll n, m, c, tot, sum[MXN];

struct node {
    // /c之和,%c之和,如果在当前区间上模拟,会用掉多少代金券
    ll div, mod, use;
} t[MXN << 2];
node operator+(const node &x, const node &y) {
    return {x.div + y.div, x.mod + y.mod, x.use + y.use + min(y.mod - y.use, x.div - x.use)};
}
#define ls p << 1
#define rs p << 1 | 1
void mdf(ll mi, ll mv, ll p = 1, ll l = 1, ll r = n) {
    if (l == r) {
        tot = tot - (t[p].div * c + t[p].mod) + mv;
        t[p] = {mv / c, mv % c, 0};
        return;
    }
    ll mid = (l + r) >> 1;
    if (mi <= mid)
        mdf(mi, mv, ls, l, mid);
    else
        mdf(mi, mv, rs, mid + 1, r);
    t[p] = t[ls] + t[rs];
}
ll que(ll p = 1, ll l = 1, ll r = n, node lft = {0, 0, 0}, ll rht = 0) {
    if (l == r) {
        ll arr = t[p].div * c + t[p].mod, cur = lft.div - lft.use, ans = lft.use;
        if (cur >= rht) {
            ans += cur, cur -= rht, arr -= cur;
            ans += min(arr / (c + 1), rht);
        } else {
            arr -= c * (rht - cur);
            ans += rht + min(arr / (c + 1), cur);
        }
        return tot - ans;
    }
    ll mid = (l + r) >> 1;
    node _lft = lft + t[ls];
    ll _rht = rht + t[rs].div * c + t[rs].mod;
    if (_lft.div - _lft.use >= _rht)
        return que(ls, l, mid, lft, _rht);
    else
        return que(rs, mid + 1, r, _lft, rht);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> c;
    for (ll i = 1, x; i <= n; i++) {
        cin >> x;
        mdf(i, x);
    }
    cout << que() << nl;
    while (m--) {
        ll x, y;
        cin >> x >> y;
        mdf(x, y);
        cout << que() << nl;
    }
    return 0;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK