NOIP2022 喵了个喵
小 E 喜欢上了一款叫做《喵了个喵》的游戏。
这个游戏有一个牌堆和 nn 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。
开始时牌堆中有 mm 张卡牌，从上到下的图案分别是 a1,a2,⋅⋅⋅,ama1,a2,···,am。
所有的卡牌一共有 kk 种图案，从 11 到 kk 编号。
牌堆中每一种图案的卡牌都有偶数张。
开始时所有的栈都是空的。
这个游戏有两种操作：
- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
- 选择两个不同的栈，如果这两个栈栈底的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。否则，则什么也不会做。
这个游戏一共有 TT 关，小 E 一直无法通关。
请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。
输入格式
第一行包含一个正整数 TT，表示数据组数。
接下来一共 TT 组数据，在每组数据中：
第一行包含三个正整数 n,m,kn,m,k，分别表示栈的个数、卡牌的个数、卡牌上图案的种类。
第二行包含 mm 个正整数，分别表示 a1,a2,⋅⋅⋅,ama1,a2,···,am，分别从上到下表示牌堆中卡牌的图案。
输入数据保证有解。
输出格式
对于每一组数据，输出若干行。
其中第一行包含一个正整数 opop，表示操作的次数。你需要保证 m≤op≤2×mm≤op≤2×m。
接下来 opop 行，每行包含两个或三个正整数，整数之间用一个空格隔开。
若为两个整数 1 s，则进行一次第一个操作并选择栈 ss。
若为三个整数 2 s1 s2，则进行一次第二个操作并选择栈 s1s1 和 s2s2。
你需要保证 1≤s,s1,s2≤n1≤s,s1,s2≤n，且 s1≠s2s1≠s2。
你的输出不需要与样例输出一致，输出任意一个合法解即可得分。
数据范围
设 SS 为所有 TT 组数据中 mm 的总和。
对于所有数据，保证 S≤2×106S≤2×106，1≤n≤3001≤n≤300，1≤ai≤k1≤ai≤k。
输入样例：
1
2 4 2
1 2 1 2
输出样例：
5
1 1
1 1
1 2
2 1 2
1 1
题意
(=￣ω￣=)喵了个咪
初始给定 nn 个空栈，每个栈记作 p1,p2,…,pnp1,p2,…,pn。
一个牌堆，可以将其看做一个长度为 mm 的数组，数组中的元素为 a1,a2,…,ama1,a2,…,am，且 1≤ai≤k1≤ai≤k。
对于每一次操作：
取 aiai 放入任意 pj(1≤j≤n)pj(1≤j≤n) 顶部。记该操作为操作 11。
如果这么操作后，pjpj 最上方的两个元素的值相同，则会自动将这两个元素消去。
该操作在进行操作 11 后将自动判断并操作。
如果操作 11 进行后，可以找到两个不同的栈 pkpk 和 plpl，如果 pkpk 和 plpl 栈底的元素相同，则可以将这两个元素消去，原来在栈底上方的元素会成为新的栈底。如果不同，则什么也不会做。
记该操作为操作 22。
要求输出一种具体的操作方案使得在数组清空后每个栈仍然是空的。
输入数据保证有解。
(思维+模拟) O(m)O(m)
首先观察数据范围，发现卡牌种类数 k∈{2n−2,2n−1}k∈{2n−2,2n−1}，说明 kk 与栈数量 nn 之间有种神秘的关系。
先看 k=2n−2k=2n−2 时的情形，发现 2n−2=2(n−1)2n−2=2(n−1)，即每个栈分配两个不同的数，仍能留下一个空栈，把这个空栈记为 spsp。
我们还注意到如果多于两个牌存在于一个栈中，中间的元素会比较尴尬，不好消掉，经常会造成无解情况。
于是有一种思路便呼之欲出了：
每次从牌堆处理一张牌时，如果这张牌的图案在某个栈的顶部出现，那么对该栈进行操作 11 并消掉两张牌；
如果这张牌的图案在某个栈 pipi 的底部出现，那么对 spsp 栈进行操作 11，再对 pipi 和 spsp 进行操作 22，消掉两张牌；
否则对任意一个非 spsp 的栈进行操作 11 即可。
由于只有 2n−22n−2 种图案，这样的方法可以保证得出结果。可以骗到前 1515 分
15 pts代码在后面。
再看 k=2n−1k=2n−1 时的情形，这时上面的策略就不好用了，因为无法保证让 spsp 一直为空且让所有其他栈内不超过三张牌。
这里我会给出一个样例来总结可能出现的各种情况。
1
4 32 7
1 2 3 4 5 6 7 7 7 5 5 4 7 4 7 1 1 5 4 5 3 4 3 7 5 7 6 2 3 1 7 4
初始状态：
用之前的操作进行到下图状况，牌堆顶新出来一个 7，这时除了 spsp 栈其他的栈都被填满了：
我们发现下一个正好是 7，把他们都放入 spsp 里消掉：
可是不是每次都有这样的运气，下一个如果和牌堆顶的牌不一样怎么办？
如果下一张牌的同类牌出现在栈底（设对应栈编号为 PP），那么可以将牌堆顶的牌放到栈 PP 上，然后将下一张牌放到栈 spsp 里，最后对栈 PP 和 spsp 执行一次操作 22 就行。
如果下一张牌的同类牌出现在栈顶就不太好办了，这时候改把牌堆顶的牌放在哪呢？好像哪里都不妥。
我们可以往后看有没有位于底部的牌（设对应栈编号为 PP），然后将牌堆顶的牌放到对应栈顶试试。
操作非常顺利！
我们再试一次：
还是有点问题。牌堆顶的牌挡住了原栈顶的牌，后面出现的和原栈顶的牌相同的牌不能消除。
不过如果把牌堆顶放入 spsp，反而能把 PP 清空，让 PP 成为新的 spsp：
这两种情况的区别是什么？
前一种情况里 PP 的栈顶牌没有被消去，后一种情况里被消去了。
那到底什么时候 PP 的栈顶牌会被消去呢？
如果牌堆顶的牌和其后第一张位于栈底的牌（设对应栈编号为 PP）之间，与 PP 的栈顶牌同类的牌出现了奇数次，那么 PP 的栈顶牌会被消去，否则则不会。
知道了这一点，剩下的部分就简单啦~
剩下这些肯定都会做了哈
完结散花~~
总结
总结
任意时刻，设牌堆顶的牌为 uu。保留一个栈为空，记其为 spsp。
策略 1：
条件：存在 spsp，且 uu 的同类牌在场上存在 或 非 spsp 栈中存在至少一个栈大小不超过 11
除了 spsp 外，其他的栈都至多放 22 个元素。每次处理一张牌时，如果 uu 在某个栈 PP 的顶部出现过，那么把 uu 放入 PP；如果 uu 在某个栈 PP 的底部出现过，那么把 uu 放入 spsp，对 PP 和 spsp 进行操作 22；否则把 uu 放入某个未满的非 spsp 栈里。
策略 2：
条件：存在 spsp，且 uu 的同类牌在场上不存在 且 非 spsp 栈中没有栈大小不超过 11
记当前所有在栈顶的 n−1n−1 个元素构成集合 SS。我们不断扫描之后的图案，直到遇到第一个不在 SS 中的图案为止。
如果这个图案就是 uu：把牌堆顶的 uu 和现在的 uu 都放入 spsp，消掉它们。因为中间的所有元素都是栈顶，可以直接放入和它们对应的栈上。
如果这个图案不是 uu：那么这个图案 vv 是某个栈 PP 的栈底。记 PP 的栈顶为 ww，讨论 ww 在刚刚扫描过的所有图案中出现次数的奇偶性：
奇数次：把 uu 放入 spsp，所有的 ww 放入 PP。这样 vv 再次出现的时候，PP 上面的 ww 被清空了，此时可以直接把 vv 消掉，PP 变成新的 spsp。
这个过程中，其他栈顶元素放入对应栈顶即可。
偶数次：把 uu 放入 PP，所有的 ww 放入 spsp（这里放到 PP 里也行）。这样 vv 再次出现的时候，PP 中自顶到底分别是 u,w,vu,w,v 三个元素。把 vv 放入 spsp，再消掉 PP 和 spsp 的栈底，这样 PP 中仍然只有两个元素。
这个过程中，其他栈顶元素放入对应栈顶即可。
嗯？有操作次数的限制？（m≤op≤2×mm≤op≤2×m）其实这个限制根本不用管，因为操作 11 只会 mm 次，而操作 22 的有效操作最多 m2m2 次。
时间复杂度
如果维护的信息恰当，每个元素只需要检查一次，单个数据组复杂度为 O(m)O(m)。
设 SS 为所有 TT 组数据中 mm 的总和，总时间复杂度为 O(S)O(S)。
因为题目保证 S≤2×106S≤2×106，时间完全够用。
空间复杂度
有点玄学，不过维护的各种信息占用的空间很小，差不多 O(m)O(m)。
（够用就行了）
无注释 15pts C++ 代码（想要注释可以看满分代码里的注释）
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
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));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N];
int id[K];
int spt;
queue<int> q;
vector<PII> ans;
inline void oper_1(int s, int x){
if(!st[s].empty() && st[s].back() == x) st[s].pop_back();
else st[s].push_back(x);
ans.emplace_back(s, -1);
}
inline void oper_2(int s1, int s2){
st[s1].pop_front();
st[s2].pop_front();
ans.emplace_back(s1, s2);
}
inline void simple(int x){
int &s = id[x];
if(!s){
if(q.empty()){
printf("完蛋了只能搞15pts了QwQ");
exit(0);
}
s = q.front(); q.pop();
oper_1(s, x);
}else{
q.push(s);
if(x == st[s].back()){
oper_1(s, x);
}else{
oper_1(spt, x);
oper_2(spt, s);
}
s = 0;
}
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
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++)
simple(a[i]);
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
带注释满分 C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
inline int read(){ // 快读，能提升 1300 多 ms
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));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N]; // 维护每个栈的栈底和栈顶的元素
int id[K]; // 维护所在栈的编号，若局面未出现则为 0
int spt; // 辅助栈的编号
queue<int> q; // 用于维护哪些栈可以弹入元素。初始时除了辅助栈，每个栈可以弹入 2 次
vector<PII> ans; // 保存答案
inline void oper_1(int s, int x){ // 操作 1，向 s 中插入 x
if(!st[s].empty() && st[s].back() == x)
st[s].pop_back(); // 若顶部两个元素相同则弹出
else st[s].push_back(x); // 否则弹入
ans.emplace_back(s, -1); // 添加入答案
}
inline void oper_2(int s1, int s2){ // 操作 2，消除 s1 和 s2 的栈底
st[s1].pop_front(); // 弹出栈底
st[s2].pop_front(); // 弹出栈底
ans.emplace_back(s1, s2); // 添加入答案
}
inline bool simple(int x){ // 新出来一个数 x，尝试简单相消
int &s = id[x];
if(!s){ // 若 x 未出现过
if(q.empty()) return false; // 没有可弹入的栈，return false
s = q.front(); q.pop();
oper_1(s, x); // 否则弹入下一个可弹入的栈
}else{
q.push(s); // 若 x 出现过，一定能够消除，把原先 x 所在的位置弹入 q
if(x == st[s].back()){ // 在栈顶
oper_1(s, x);
}else{ // 在栈底
oper_1(spt, x);
oper_2(spt, s);
}
s = 0; // 然后改为局面未出现
}
return true;
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
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 u = a[i]; // 记录当前数值
int r = i + 1, v = a[r];
while(r <= m && v != u && st[id[v]].back() == v)
v = a[++r]; // 寻找下一个不在栈顶的数
// 此时，r 是 i 后第一个不在栈顶的下标，v 是 a[r]
if(v == u){ // 如果 v 正好和 u 一样
oper_1(spt, u);
for(int j = i + 1; j < r; j++)
simple(a[j]);
oper_1(spt, v); // 把他们在辅助栈消除
}else{ // 否则 v 是某个栈 P 的栈底
int p = id[v], w = st[p].back(); // 记 P 的栈顶为 w
bool is_even = true; // 查看 w 出现次数奇偶性
for(int j = i + 1; j < r; j++)
if(a[j] == w)
is_even = !is_even;
if(is_even){ // w 出现次数为偶数
oper_1(p, u); // u 放入 P
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(spt, w); // 这里 w 进 P 和 sp 都行
else simple(a[j]); // 注意这里用 simple 而不是
// oper_1，因为要自动更新 q
}
oper_1(spt, v);
oper_2(spt, p); // 消除两个栈底的 v
id[v] = 0;
id[u] = p;
}else{ // w 出现次数为奇数
oper_1(spt, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(p, w); // 这里注意：
// 不能直接 simple，
// 因为 P 即将变成 sp，
// 所以暂时不能让 P 弹入 q
else simple(a[j]);
}
oper_1(p, v);
id[v] = id[w] = 0; // P 原先元素为 v，w，现在清空
id[u] = spt; // 原先 sp 此时存在一个元素 u
q.push(spt); // 更新 q
spt = p; // P 成为新的 sp
}
}
i = r;
}
// 简单输出
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
无注释满分 C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
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));
}
typedef pair<int, int> PII;
const int N = 310;
const int M = 2000010;
const int K = N << 1;
int T;
int n, m, k;
int a[M];
deque<int> st[N];
int id[K];
int spt;
queue<int> q;
vector<PII> ans;
inline void oper_1(int s, int x){
if(!st[s].empty() && st[s].back() == x) st[s].pop_back();
else st[s].push_back(x);
ans.emplace_back(s, -1);
}
inline void oper_2(int s1, int s2){
st[s1].pop_front();
st[s2].pop_front();
ans.emplace_back(s1, s2);
}
inline bool simple(int x){
int &s = id[x];
if(!s){
if(q.empty()) return false;
s = q.front(); q.pop();
oper_1(s, x);
}else{
q.push(s);
if(x == st[s].back()){
oper_1(s, x);
}else{
oper_1(spt, x);
oper_2(spt, s);
}
s = 0;
}
return true;
}
int main(){
T = read();
while(T--){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
a[i] = read();
ans.clear();
memset(id, 0, sizeof(id));
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 u = a[i];
int r = i + 1, v = a[r];
while(r <= m && v != u && st[id[v]].back() == v)
v = a[++r];
if(v == u){
oper_1(spt, u);
for(int j = i + 1; j < r; j++)
simple(a[j]);
oper_1(spt, v);
}else{
int p = id[v], w = st[p].back();
bool is_even = true;
for(int j = i + 1; j < r; j++)
if(a[j] == w)
is_even = !is_even;
if(is_even){
oper_1(p, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(spt, w);
else simple(a[j]);
}
oper_1(spt, v);
oper_2(spt, p);
id[v] = 0;
id[u] = p;
}else{
oper_1(spt, u);
for(int j = i + 1; j < r; j++){
if(a[j] == w) oper_1(p, w);
else simple(a[j]);
}
oper_1(p, v);
id[v] = id[w] = 0;
id[u] = spt;
q.push(spt);
spt = p;
}
}
i = r;
}
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
if(ans[i].second == -1) printf("1 %d\n", ans[i].first);
else printf("2 %d %d\n", ans[i].first, ans[i].second);
}
}
return 0;
}
作者：太雪菜
链接：https://www.acwing.com/solution/content/136942/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。