P9463 [EGOI2023] Inflation / 通货膨胀 题解

Eason_cyx · 2023-10-03 15:35:13 · 题解

出了这题的数据，就来写篇题解。

不算太难。

直接模拟，没什么好说的。

时间复杂度 O(qn)，可以通过前两个 \text{Subtask}。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[300005];
signed main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
    int n,Q; cin >> n;
    long long sum = 0;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    cin >> Q;
    while(Q--) {
        string opt; cin >> opt;
        if(opt == "INFLATION") {
            int x; cin >> x;
            int ans = 0;
            for(int i = 1;i <= n;i++) {
                a[i] += x;
                ans += a[i];
            }
            cout << ans << endl;
        }
        else {
            int x,y; cin >> x >> y;
            int ans = 0;
            for(int i = 1;i <= n;i++) {
                if(a[i] == x) a[i] = y;
                ans += a[i];
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Record

本部分讲解如何通过子任务 3。

可以发现，要求输出的只是所有价格的总和，而且 x 是一个固定的值。

每一个元素增加 x，那么 n 个元素不就增加了 n \times x 吗？

再加上初始的元素和，可以做到 INFLATION 操作时间复杂度 O(1)。

于是总时间复杂度降至 O(q)，可以通过。

可以尝试将操作离线下来，和前面的 42 分结合，得到 61 分，但是比较麻烦。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[300005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,Q; cin >> n;
    long long sum = 0;
    for(int i = 1;i <= n;i++) {
        cin >> a[i]; sum += a[i];
    }
    cin >> Q;
    while(Q--) {
        string opt; cin >> opt;
        int x; cin >> x;
        sum += n * x;
        cout << sum << endl;
    }
    return 0;
}

Record

我们现在已经知道了怎么快速完成 INFLATION 操作，那 SET 呢？

其实一样啊！把 x 变成了 y，不就增加了 y-x 吗？

那怎么统计有多少个值为 x 的呢？

我们用一个桶来存储就可以了。

最后，在加完以后，记得将桶更新，原来所有的 x 都变成了 y。

注意 x=y 的特殊情况！

至此，本题就完成了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<long long,long long> mp;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,Q; cin >> n;
    long long sum = 0,add = 0;
    for(int i = 1;i <= n;i++) {
        long long x; cin >> x; mp[x]++;
        sum += x;
    }
    cin >> Q;
    while(Q--) {
        string opt; cin >> opt;
        if(opt == "INFLATION") {
            int x; cin >> x;
            add += x;
            sum += 1ll * n * x;
            cout << sum << endl;
        }
        else {
            int x,y; cin >> x >> y;
            x -= add; y -= add;
            int cha = y - x;
            sum += 1ll * mp[x] * cha;
            if(x != y) {
                mp[y] += mp[x];
                mp[x] = 0;
            }
            cout << sum << endl;
        }
    }
    return 0;
}

AC Record

总结：这题考察的是桶的思想，以及一点点贡献法，有一定的思维难度，建议评黄。