ABC337

基本情况

ABC 秒了，D 数组在空间复杂度上面第一次疯狂吃亏，吃了两次罚时过。

赛后看官方题解，发现C做法薄纱我。

C - Lining Up 2

https://atcoder.jp/contests/abc337/tasks/abc337\_c

这题一眼链表，我用双向链表实现，代码石山。

官方题解就题论题，更本质。

其实这题并没必要开双向链表，因为实际上只有一种位置关系，左到右。

直接维护一个类似单链表的数据结构就行了。

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
#include <iostream>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;

    vector<unsigned> B(N + 1, N + 1); // B[i] 存储下标对应的人的右边的人
    unsigned front;// 队头

    for(unsigned i = 1; i <= N; ++i){
        int A;
        cin >> A; 
        if(A < 0)
            front = i;//维护队头
        else
            B[A] = i; //更新A右边的人
    }

    while(front <= N){ // 就类似邻接表遍历，从队头开始
        cout << front << " ";
        front = B[front];
    }
    cout << endl;
    return 0;
}

E - Bad Juice

https://atcoder.jp/contests/abc337/tasks/abc337\_e

看似是交互，实则是结合bitmask的构造题。

因为每个人是否拉肚子就 (0,1) 两种情况，所以可以按位构造。

对于第 (i) 个人，让他喝完编号第 (i) 为 (1) 的所有果汁。

如果第 (i) 个人中毒了，那么第 (i) 位为 (1) 的果汁肯定有问题，这里每个 (i) 中毒所表示的信息是不互相冲突的，可以叠加的：

如果第 (3,4,6,7) 个人中毒了，那么就说明有问题的果汁其 (3,4,6,7) 位都为 (1)

这样只要最多拉 (m,(n \leq 2^m)) 个人就能涵盖所有状况，可以证明拉的人最少。

把所有 (i) 中毒的位全部或上去，答案就是中毒的果汁。

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
signed main() {

    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;

    int m = 0;
    while ((1 << m) < n) {m += 1;}
    std::cout << m << std::endl;

    for (int i = 0; i < m; i++) {//选n个人品尝
        std::vector<int> res;
        for (int j = 0; j < n; j++) if (j & (1 << i)) {//如果j果汁第i位是1，就让i品尝
            res.push_back(j + 1);
        }
        std::cout << sz(res) << ' ';
        for (auto& x : res) {std::cout << x << ' ';}
        std::cout << std::endl;
    }

    std::string s;
    std::cin >> s;

    int ans = 0;

    for (int i = 0; i < m; i++) if (s[i] == '1') {
        ans |= (1 << i);//有毒的果汁第i位肯定为1
    }

    std::cout << (ans + 1) << std::endl;

    return 0;
}

F - Usual Color Ball Problems

https://atcoder.jp/contests/abc337/tasks/abc337\_f

超级恶心的滑动窗口。

为了方便起见，我们考虑序列

[C’ = (C’_1, C’_2, \ldots, C’_{2N}) \coloneqq (C_1, C_2, \ldots, C_{N}, C_1, C_2, \ldots, C_{N}),
]

这个序列是通过连接两个给定序列的副本得到的，并且将此问题看作是要找到针对 (C’) 的段 ([l, l+N-1]) 的操作中盒子中的球的总数，对于每个 (l = 1, 2, \ldots, N)。令 (f(c, l, r)) 表示段 ([l, r]) 中颜色为 (c) 的球的数量，(g©) 表示整个原始序列 (C) 中颜色为 (c) 的球的数量。

首先，我们考虑如何找到固定段 ([l, l+N-1]) 的答案。作为针对段 ([l, l+N-1]) 的操作的结果，如果用于存储颜色为 (c) 的球的箱子数量为 (b(c, l))，那么结果中颜色为 (c) 的球的数量是 (\min\lbrace b(c, l) \times K, g©\rbrace)，因此答案是

[\mathrm{ans}_l = \sum_{c = 1}^N \min\lbrace b(c, l) \times K, g©\rbrace.
]

一旦我们找到每种颜色 (c) 的 (b(c, l))，我们也可以找到 (\mathrm{ans}_l)，因此我们接下来考虑如何找到它。

如果一个球被放入一个空箱子中（这增加了用于该颜色的箱子的数量），如果这个球是要处理的颜色的第 (1) 个、((K+1)) 个、((2K+1)) 个、((3K+1)) 个等球，则会消耗一个空箱子。因此，让我们称每种颜色的第 (1) 个、((K+1)) 个、((2K+1)) 个、((3K+1)) 个等球为机会球。

每次处理一个机会球（任何颜色的）时，都会消耗一个空箱子，因此 (b(c, l)) 等于前 (M) 个要处理的机会球中颜色为 (c) 的球的数量。因此，要处理的第 (M) 个机会球的位置是什么？

当从位置 (l) 开始操作时，段 ([l, r]) 中颜色为 (c) 的机会球的数量是 (\left\lceil f(c, l, r) / K \right\rceil)，因此段 ([l, r]) 中的机会球（任何颜色的）的数量是

[S(l, r) \coloneqq \sum_{c = 1}^N \left\lceil \frac{f(c, l, r)}{K} \right\rceil.
]

因此，要处理的第 (M) 个机会球的位置是使得 (S(l, r) \geq M) 的最小 (r)。记为 (r_l)，则有 (b(c, l) = \left\lceil f(c, l, r_l) / K \right\rceil)，因此所求的答案表示为

[ \mathrm{ans}_l = \sum_{c = 1}^N \min\left\lbrace \left\lceil \frac{f(c, l, r_l)}{K} \right\rceil \times K, g© \right\rbrace. \tag{1}
]

（如果没有 (r \leq l+N-1) 满足 (S(l, r) \geq M)，则为了方便起见，我们让 (r_l \coloneqq l+N-1)。）因此，为了找到 (\mathrm{ans}_l)，只需要为固定的 (l) 找到 (r_l)，并评估上述式子 (1)。然而，简单地对所有 (l = 1, 2, \ldots, N) 进行计算是不可能在执行时间限制内完成的。

相反，注意到根据上面的讨论，(r_1 \leq r_2 \leq \cdots \leq r_N)。为了按顺序评估 (l = 1, 2, \ldots, N) 的答案，(r_l) 可以以滑动窗口的方式高效地找到，而滑动窗口时，还要保持对当前段 ([l’, r’]) 对应的值 (1)，并且每次 (l’) 或 (r’) 增加一个时应用增量更新，以便以总共 (O(N)) 的时间找到 (\mathrm{ans}_l)。

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
signed main() {

    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> c(n * 2);
    for (int i = 0; i < n; i++) {std::cin >> c[i]; --c[i]; c[i + n] = c[i];}//破环成链
    std::vector<int> all(n);//维护该颜色在1~n的出现次数
    for (int i = 0; i < n; i++) {all[c[i]] += 1;}
    std::vector<int> f(n);//即f(c, l, r),[l, r]区间内颜色为c的球的出现数量
    std::vector<int> box(n);//box[c]表示颜色为c的盒子的数量

    i64 ans = 0, totBox = 0;

    auto add = [&](int color, int x) {
        //消除没加之前的改颜色球对答案的影响
        ans -= std::min(box[color] * k, all[color]);
        totBox -= box[color];
        box[color] -= (f[color] + k - 1) / k;
        f[color] += x;//[l, r]区间该颜色球的数量+1
        //处理加之后的影响
        box[color] += (f[color] + k - 1) / k;//用的盒子是总数 / k向上取整
        totBox += box[color];//盒子数量加上去
        ans += std::min(box[color] * k, all[color]);//更新答案
    };

    for (int l = 0, r = 0; l < n; l++) {
        while (r < l + n and totBox < m) {add(c[r], 1); r++;}//如果盒子还没用完并且右端点也还没到头
        std::cout << ans << '\n';
        add(c[l], -1);//剪掉开头
    }

    return 0;
}