P8866

dbxxx · 2022-12-04 13:35:50 · 题解

本篇题解将细致讲解本题的思路，并给出一种长度短而可读性高的解法。

您可在我的博客中查看本文，谢谢！

P8866 NOIP2022 喵了个喵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)。

本题解中我们将图案为 x 的卡牌看做数字 x，将本题对于卡牌的操作看做对数字的操作。

观察到数据范围，k \in \{2n - 2, 2n - 1\}，那么做法肯定跟 k 强相关。很难不联想 2018 年的旅行。但是那个 m = n - 1 给了 60 分，这个呢？

k = 2n - 2

首先发现 op 的限制其实是假的：我们一定恰好进行了 m 次操作 1，最多进行了 0.5m 次操作 2，所以 op 一定天然满足 m \le op \le 1.5m。

观察 k 和 n 的关系，发现是近似二倍，而且 k = 2(n - 1)，也就是我们如果把每两种数字考虑到一个栈，这样分配将恰好剩下一个空栈。

考虑将数字 2i - 1 和 2i 分配到第 i 个栈中，第 n 个栈就可以作为空辅助栈了。稍作思考可以给出以下的解法：

遇到一个数字 x，我们查看这个数字所分配到栈 s 的情况：

• 如果 s 为空，直接入栈；
• 如果 s 有 1 个元素，和 x 相同，将 x 入栈 s 并将这两个 x 消除；
• 如果 s 有 1 个元素，和 x 不同，将 x 入栈 s ；
• 如果 s 有 2 个元素，栈顶和 x 相同，将 x 入栈 s 并将这两个 x 消除；
• 如果 s 有 2 个元素，栈顶和 x 不同，那么栈底一定和 x 相同。将 x 入辅助栈 n，对栈 n 和栈 s 栈底相消。

容易看出，我们第偶数次遇到 x 的时候，总能立刻将它和上一个 x 抵消，所以一定能报告出解。

另外，可以注意到本题的操作只对栈顶和栈底有效，所以如果栈中某时元素很多就会造成大量的滞留，非常不优。这也和本做法中栈的大小始终不超过 2 有关系（达到 3 之后可以马上通过相消降为 2）。

这样 15 分就到手了。是 60 分的四分之一。

k = 2n - 1

一种比较显然的想法是，对于数字 x \le 2n - 2 我们暂时仍然考虑上面的处理方式，然后考虑如何处理 x = 2n - 1。发现遇到 x = 2n-1 的时候局面的结构比较参差不定，不好想（后来发现好像也不是不可以，读者可以自己试试？）。

我选择了另一种想法，那就是抛开栈 i 和数字 2i，2i - 1 的绑定关系，采用先来后到的思想，按照 k = 2n-2 的策略尽可能走下去。具体来说：

• 如果我们当前遇到的数 x 在所有栈中还没出现过，就把 x 射入一个还没满两个元素的栈，但如果已经有 n-1 个栈全都满了，说明我们按照 k= 2n-2 的策略已经走不下去了（我们必须留一个空栈作为辅助栈，用来栈底相消）。
• 如果 x 在某个栈中出现了，直接使用 k = 2n-2 的策略直接让当前的 x 和栈中出现的那个 x 消除。

当走不下去的时候，一定是局面上的 n-1 个栈全部被填满各两个元素，每种元素恰出现一次，且接下来要填的数还是一个没有在这 n-1 个栈中出现过的数 P。

提一嘴，我感觉在剩下的 85 分中，应该是有部分数据可以按照上述策略成功走完整个游戏的，毕竟随机数据下，出现走不下去的概率不是特别高（当然也不难构造）。所以也不失为一个骗分好办法。不过这题有多测，所以也有可能会卡。

更新：官方数据卡了这一点，只能拿到 15 pts。民间数据可以拿到 30 pts。

直接把 P 放到辅助栈显然是错的：假如 P 后面跟了一个被压在栈底的数字，那么这两个数字可能很难再抵消，很不优。

我们考虑离线：也就是说，我们开始预知这个数后面都是什么数。依据后面数的情况，我们考虑 P 放在哪里。

考虑紧跟在 P 后方最长的一串数，满足这些数都在栈顶。如果不考虑当前 P 的去向，那么直接将这些数放到对应的栈，和栈顶相消即可，如果再来就仍然放置原来的栈顶。比如 5 是某个栈的栈顶，如果 P 后面来了个 5 就让它和 5 相消，如果再来一个 5 就放在原来的栈顶，如果再来就继续相消。因此我们发现，这些数还是相当自由的，我暂且称之为自由相消。

因此发现，如果 P 后面第一个不在栈顶上的数是 P，那么我们就把当前的 P 放入辅助栈，然后接下来的数自由相消，最后在第二个 P 来时，将它也放入辅助栈，栈顶相消即可。这种情况比较简单。

现在讨论 P 后面第一个不在栈顶上的数是一个栈底 X 的情况。我们记其对应栈为 S。此时未来的数列是 (P, \cdots, X)，其中 \cdots 都是某个栈的栈顶。我们讨论 S 当前的栈顶 Y。

• 如果未来数列的 P 和 X 之间，Y 出现了奇数次：把 P 放入辅助栈，接下来一直自由相消，直到将处理 X 为止。由于 Y 的数量是奇数，加上一开始的一个 Y，此时 Y 一定被消除光，现在 S 的栈顶变成 X，将 X 放入 S 栈顶相消，S 变成了空栈。
• 如果 Y 出现了偶数次：把 P 放入 S，未来所有不为 Y 的栈顶自由相消，对于 Y，我们将其全部放入辅助栈相消，直到将处理 X 为止。由于 Y 的数量是偶数，这些 Y 一定都被消除光，辅助栈仍为空，我们将 X 放入辅助栈，和 S 栈底相消，辅助栈仍为空。

经过上述操作后，局面总会保持：

• 存在一个空栈；
• 所有数都在栈中最多出现一次；
• 所有栈最多只有两个元素。

直接让新的空栈作为辅助栈即可。

如何证明这种做法一定可以报告出解？其实很简单：在最后，每种元素在所有栈中最多只能出现一次；每种数字数量均为偶数，相消永远是同种元素两两相消，所以到最后，某种数出现奇数次是不可能的。综合来看，每种元素到最后只能出现零次，也就是必定不会出现。

一个实现问题：怎么找当前还没满两个元素的栈？我们维护一个队列，存储栈的编号，使得始终满足：

• 如果一个栈当前存满两个元素，队列中不存在当前栈的编号；
• 如果一个栈当前只存了一个元素，让队列中该栈的编号出现一次；
• 如果一个栈当前为空，让队列中该栈的编号出现两次。
• 辅助栈的编号在队列中不能出现。

一开始，我们直接让 1 \sim n - 1 都推入队列各两次，n 作为初始辅助栈不推入队列。

假如我们当前遇到了一个数 x，这个 x 没还没出现在栈中，我们要给 x 找一个没满的栈时，直接取队列的队头作为 x 选择的栈编号，队列弹出队头即可。特别地，如果此时队列为空，证明除了辅助栈所有栈都满了，证明我们按照 k = 2n-2 的策略走不下去，要开始特别处理了；

而当一个元素被弹出栈后，让元素所对应的栈的编号入队。

容易发现，这样就维护好了上面队列应该满足的四条性质。不过，辅助栈的编号可能会变动，要始终保证好它不出现在队列中是有些细节的。

时间复杂度 \Theta(m)。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-12-04 01:03:11 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-12-04 13:35:14
 */
#include <bits/stdc++.h>
inline int read() {
    int x = 0;
    bool f = true;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = false;
    for (; isdigit(ch); ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f ? x : (~(x - 1));
}

const int maxn = 305;
const int maxm = (int)2e6 + 5;

int a[maxm];
std :: deque <int> st[maxn];
int id[maxn * 2]; // 维护所在栈编号，局面未出现则为 0

typedef std :: pair <int, int> pii;
std :: vector <pii> ans;

inline void pu(int s) {
    ans.emplace_back(s, 0);
}

inline void de(int s, int t) {
    ans.emplace_back(s, t);
}

int spt; // 辅助栈编号
std :: queue <int> q; // 维护空栈

inline bool simple(int x) { // 尝试简单相消
    int s = id[x];
    if (!s) {
        if (q.empty())
            return false;
        id[x] = s = q.front();
        q.pop();
        pu(s);
        st[s].push_back(x);
    } else {
        id[x] = 0;
        q.push(s);
        if (x == st[s].back()) {
            pu(s);
            st[s].pop_back();
        } else {
            pu(spt);
            de(spt, s);
            st[s].pop_front();
        }
    }
    return true;
}

int main() {
    for (int T = read(); T; --T) {
        int n = read(), m = read(); read();
        for (int i = 1; i <= m; ++i)
            a[i] = read();
        std :: memset(id, 0, sizeof(id));
        ans.clear();
        spt = n;

        while (!q.empty())
            q.pop();
        for (int i = 1; i < n; ++i) {
            q.push(i);
            q.push(i);
        }

        for (int i = 1; i <= m; ++i) if (!simple(a[i])) {
            int p = a[i];
            int r = i + 1, x = a[r];
            for (; r <= m && x != p && st[id[x]].back() == x; ++r, x = a[r]);
            // 此时 r 是 i 后第一个不在栈顶上的下标，x 是 a[r]

            if (x == p) {
                pu(spt);
                for (int j = i + 1; j < r; ++j)
                    simple(a[j]);
                pu(spt);
            } else {
                int s = id[x], y = st[s].back();
                bool evn = true; // 中间栈顶中，y 的数量是否为偶数
                for (int j = i + 1; j < r; ++j)
                    if (a[j] == y)
                        evn = !evn;
                if (evn) {
                    pu(s);
                    st[s].push_back(p);
                    for (int j = i + 1; j < r; ++j) {
                        if (a[j] == y)
                            pu(spt);
                        else
                            simple(a[j]);
                    }
                    pu(spt);
                    de(spt, s);
                    st[s].pop_front();
                    // st[s] 从栈底到栈顶，原先为 x, y，现在为 y, p
                    // 依此更新 id
                    id[x] = 0;
                    id[p] = s;
                } else {
                    pu(spt);
                    st[spt].push_back(p);
                    for (int j = i + 1; j < r; ++j) {
                        if (a[j] == y)
                            pu(s); // 注意这里不要直接 simple(a[j])
                        // 原因是 s 即将变成 spt，所以暂时不能让 s 弹入 q
                        // 特判让 simple 函数此时不把 s 不弹入 q 也不行
                        // 假如 3 1 2 1 1 1 ....
                        // 如果直接不弹入 q，会造成后面的一串 1 1 1 无法正确弹入 s
                        // 最后暴力扫队列把 s 删除复杂度也不对
                        // 所以正确的做法就是不用 simple 函数
                        else
                            simple(a[j]);
                    }
                    pu(s);
                    st[s].clear();
                    // 原先辅助栈 spt 此时存在一个元素 p
                    // s 原先栈底到栈顶为 x，y， 现在为空
                    // s 作为新的 spt
                    // 依此更新 id 和 q
                    id[x] = id[y] = 0;
                    id[p] = spt;
                    q.push(spt);
                    spt = s;
                }
            }

            i = r; // 注意循环会自带 ++i，下一次循环 i = r + 1
        }

        printf("%d\n", (int)ans.size());
        for (pii p : ans) {
            if (p.second)
                printf("2 %d %d\n", p.first, p.second);
            else
                printf("1 %d\n", p.first);
        }
    }
}

删除注释和不必要的空格，并且仍然保持很高的可读性后，代码长度是不足 2K 的，几乎优于所有 AC 提交。而且，可读性非常好。

如果觉得这篇题解写得好，请不要忘记点赞，谢谢！