题解：AT_abc366_c [ABC366C] Balls and Bag Query

Posted on Edited on In , ,

题解：AT_abc366_c [ABC366C]

前言

题目已经翻译好了，故不提供翻译解释。

正解

需注意：编号为 \(x\) 的球可以有很多个，赛场上因此痛吃罚时。

考虑到 \(x\in [1,10^6]\)，数据范围较小，故开一个桶：\(s_x\) 记录 \(x\) 出现的次数。

同时维护一个集合，记录目前还存在的球种类。考虑到我们只关心球种类的数量，故可将集合变为一个计数器。

代码很容易写出来。

时间复杂度 \(O(Q)\)，空间复杂度 \(O(\max x)\)。

加强版

但是如果 \(1\leq x \leq 10^{18}\)，那 \(x\) 肯定无法用桶去装了。这是因为数组一定是连续的，而事实证明根本不需要连续，因为很多数是没有出现过的。

但是 C++ 中的 STL 恰恰有这么一个非连续的数据结构 map。其使用方法与数组类似。

注意：map 在没有修改的键值对应值默认是 0，这里只举整数类型为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)

using namespace std;
typedef long long ll;
typedef double db;

int Q,cnt=0;
map<ll,ll> s;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>Q;
    while(Q--)
    {
        int o;ll x;
        cin>>o;
        if(o==1)
        {
            cin>>x;
            if(s[x]==0) cnt++;
            s[x]++;
        }
        if(o==2)
        {
            cin>>x;
            s[x]--;
            if(s[x]==0) cnt--;
        }
        if(o==3)
            cout<<cnt<<endl;
    }
}

时间复杂度为 \(O(Q\log Q)\)。因为 map 一次查询的复杂度是 \(O(Q\log Q)\) 的，且最多有 \(Q\) 个球会加入袋子。

空间复杂度 \(O(Q)\)，理由同上。

总结

这道题作为 C 还是很水的，而且不必用 STL。

AC：https://atcoder.jp/contests/abc366/submissions/56635007

广告

安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。