主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站(新前端)
系统公告
1
/
1
请查看完所有公告
P8866
最后更新于 2025-08-28 15:47:02
作者
dbxxx
分类
题解
题解
P8866
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
本篇题解将细致讲解本题的思路,并给出一种长度短而可读性高的解法。 [您可在我的博客中查看本文,谢谢!](https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p8866.html) [P8866 NOIP2022 喵了个喵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P8866)。 本题解中我们将图案为 $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)$。 ```cpp /* * @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 提交。而且,可读性非常好。 如果觉得这篇题解写得好,请不要忘记点赞,谢谢!
正在渲染内容...
点赞
183
收藏
1