P8866 [NOIP2022] 喵了个喵 Solution

更好的阅读体验戳此进入

题面

存在 $n$$n$ 个栈，给定 $m$$m$ 张卡牌，每张卡牌有图案 $a_i$$a_i$，给定 $k$$k$，有 $a_i\in [1,k]$$a_i \in [1, k]$。保证每种图案的卡牌数均为偶数。初始所有栈为空。

你可以进行两种操作：

• 将剩余卡牌中最先的一张插入某个栈，如果此时该栈最上方两张卡牌的图案相同则会被消除。
• 选定两个非空栈，如果这两个栈底卡牌图案相同则这两张卡牌会被消除。

输入保证有解，求一个合法操作方案。

Solution

这道题实际上是可以通过每个部分分来慢慢推出方案的。

首先第一档部分分，对于 $k=2n-2$$k = 2n - 2$，不难想到，我们将一个栈空出来作为备用栈，并保证其它栈里永远最多只有两个卡牌，也就是一个在栈顶一个在栈底，实现上可以把所有可以放卡牌的栈顶和栈底存下来并动态维护，注意要先用栈底再插栈顶。然后顺序遍历所有卡牌。如果当前所有栈中不存在这个颜色，那么找个栈内卡牌数不足 $2$$2$ 的丢进去。如果存在的话，考虑如果其在栈顶，那就把这个卡牌放在对应的栈顶来消除，然后重新将这个位置置为可以放置卡牌。如果在栈底那么将这张卡牌放在备用栈里，然后用操作二将这一对删除即可。

然后考虑后面的 $k=2n-1$$k = 2n - 1$ 的部分分。我们还是按照刚才的思路，保留一个备用栈，然后老样子处理卡牌。显然处理一段时间之后就会出现一个状态，即已经有 $2n-2$$2n - 2$ 个颜色的卡牌被放到了栈里，然后此时又多了个新的栈中不存在的颜色的卡牌。

这时不难想到有如下方案：我们先将这张卡牌搁置，令其颜色为 $a$$a$，然后继续向后遍历，如果再碰到了颜色为 $a$$a$ 的直接结束，这里还要注意如果循环结束之后 $a$$a$ 的两个位置的答案没有被更新，那么需要额外更新一下，即把两个 $a$$a$ 都塞进备用栈里消除一下。然后考虑过程中碰到的其它颜色的卡牌，显然第一次遇到的时候其一定是在前面的栈中存在的，因为颜色一共就有 $2n-1$$2n - 1$ 个。如果碰到在栈顶的颜色，那么直接将其消除，并且标记这个该颜色的位置为这个位置，如果本次遍历过程中再次碰到这个颜色还要再次把这个颜色放到这个位置上。如果碰到在栈底的颜色，那么这时候考虑当前其对应的栈顶是否已经在本次遍历过程中被删除。我们令这个栈底颜色为 $b$$b$，栈顶颜色为 $c$$c$。

如果 $c$$c$ 被删除的话，那么我们将 $a$$a$ 放在备用栈里，然后将新的 $b$$b$ 放到原来的 $b$$b$ 栈，将其消除，则此时备用栈的位置会多一个栈顶的空位，$b$$b$ 栈会变空，则我们这时直接将 $b$$b$ 栈作为新的备用栈即可让状态又变成原来的样子。

如果 $c$$c$ 依然存在，那么先将 $a$$a$ 放在 $b$$b$ 栈里，然后再将新的 $b$$b$ 放到备用栈里，这样可以将 $b$$b$ 栈和备用栈栈底的卡牌对应消除掉，此时则 $b$$b$ 栈又变回两个元素，备用栈又为空。

然后这个时候我们可能会发现一点问题，比如如果有一个实际的结果：$(2,1,3,1,1,1,1)$$(2, 1, 3, 1, 1, 1, 1)$（这里记左侧为栈底，右侧为栈顶），但是按照我们的写法实际是变成了 $(2,1,1,1,1,1,3)$$(2, 1, 1, 1, 1, 1, 3)$，表面上这些是不同的，但是结果上其都为 $(2,1,3)$$(2, 1, 3)$。对于剩下的 $1$$1$ 为奇数个的，写一下会发现也是等效的。

思路看起来还是比较简单容易想的，但是这东西实现起来就能感受到恶心了，这里为了方便理解，大概说明一下代码中的部分关键变量名的作用。

对于每个 pair 前者表示栈的索引，后者为栈顶或栈底，$1$$1$ 表示栈底，$0$$0$ 表示栈顶，ans 存的是答案，mp 指的是某个颜色对应的在栈中的位置，stk 存储的是对应位置中存的是什么颜色，mark 是指对应颜色被固定的位置（在遇到 $a$$a$ 之后遍历的时候使用），unfix 存储的是所有空着的可以使用的栈的位置。

写在后面

建议先做 T3 T4 再做这题

这个应该算是我写过最恶心的题之一了，调代码已经人调麻了。如果是在考场上我绝对部分分一拿就跑路。最开始有个思路然后写了一百多行写完了，调试的过程中发现假掉了。。。然后是参考的 @sssmzy 的思路，上面说的也是这个做法，然后做完就开始阴间调试的过程。最后本地对拍全过然后交上去就 WA，各种找样例各种手动模拟，不知道调了多久才找到问题：备用栈切换的时候 unfix 中可能有剩余的新栈中的空位，需要删除。

然后改来改去的代码可能变得很难看，敬请谅解，并且我的实现也可能不够精细，或许会有更简便的方法和更简便的实现，这里只是提供一个思路。还有个问题就是这个 erase 理论上最坏可能是 $O(n)$$O(n)$ 的，理论上似乎最坏情况下 $O(S)$$O(S)$ 次，$O(nS)$$O(nS)$ 似乎理论上能被卡，但是这也是理论上，实际上完全卡不满，基本上是无法被卡掉的，并且本身 $O(nS)$$O(nS)$ 也超的不多，再加上 O2 那基本上就是稳稳过。

Code

xxxxxxxxxx
232
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M, K;
26
int a[2100000];
27

28
namespace Sub1{
29
    struct Ans{int flag; int a, b;};
30
    pair < int, bool > mp[610];
31
    int stk[310][2];
32
    basic_string < pair < int, bool > > unfix;
33
    basic_string < Ans > ans[2100000];
34
    void Make(void){
35
        memset(mp, 0, sizeof mp);
36
        memset(stk, 0, sizeof stk);
37
        for(int i = 1; i <= M; ++i)ans[i].clear(), ans[i].shrink_to_fit();
38
        unfix.clear();
39
        for(int i = N - 1; i >= 1; --i)unfix += {{i, 0}, {i, 1}};
40
        for(int i = 1; i <= M; ++i){
41
            int col(a[i]), cur(N);
42
            if(mp[col].first){
43
                if(mp[col].second){
44
                    ans[i] += {Ans{1, cur}, Ans{2, mp[col].first, cur}};
45
                    if(stk[mp[col].first][0])
46
                        unfix += {mp[col].first, 0},
47
                        mp[stk[mp[col].first][0]].second = 1;
48
                    else
49
                        unfix += {mp[col].first, 1};
50
                    stk[mp[col].first][1] = stk[mp[col].first][0];
51
                    stk[mp[col].first][0] = 0;
52
                    mp[col] = {0, 0};
53
                }
54
                else{
55
                    ans[i] += {Ans{1, mp[col].first}};
56
                    unfix += mp[col];
57
                    stk[mp[col].first][mp[col].second] = 0;
58
                    mp[col] = {0, 0};
59
                }
60
            }else{
61
                if(!unfix.empty()){
62
                    ans[i] += Ans{1, unfix.back().first};
63
                    mp[a[i]] = unfix.back();
64
                    stk[mp[col].first][mp[col].second] = col;
65
                    unfix.pop_back();
66
                }else{
67
                    printf("Error!\n"), exit(1);
68
                }
69
            }
70
            // printf("Finish %d\n", i);
71
            // printf("unfix: ");
72
            // for(auto tmpp : unfix)printf("(%d, %d) ", tmpp.first, tmpp.second ? 1 : 0);
73
            // printf("\n");
74
            // for(int i = 1; i <= 4; ++i)
75
            //     printf("mp[%d] = %d, %d\n", i, mp[i].first, mp[i].second ? 1 : 0);
76
        }
77
        ll tot(0);
78
        for(int i = 1; i <= M; ++i)tot += ans[i].size();
79
        printf("%lld\n", tot);
80
        for(int i = 1; i <= M; ++i)
81
            for(auto opt : ans[i])
82
                if(opt.flag == 1)printf("1 %d\n", opt.a);
83
                else printf("2 %d %d\n", opt.a, opt.b);
84
    }
85
}
86
namespace Sub2{//1 - down, 0 - up
87
    struct Ans{int flag; int a, b;};
88
    basic_string < Ans > ans[2100000];
89
    pair < int, bool > mp[610];
90
    int cur(N);
91
    basic_string < pair < int, bool > > unfix;
92
    int stk[310][2];
93
    pair < int, bool > mark[610];
94
    void Make(void){
95
        for(int i = 1; i <= M; ++i)ans[i].clear(), ans[i].shrink_to_fit();
96
        memset(mp, 0, sizeof mp);
97
        memset(mark, 0, sizeof mark);
98
        memset(stk, 0, sizeof stk);
99
        cur = N, unfix.clear();
100
        for(int i = N - 1; i >= 1; --i)unfix += {{i, 0}, {i, 1}};
101
        for(int i = 1; i <= M; ++i){
102
            int col = a[i];
103
            if(mp[col].first){
104
                if(mp[col].second){
105
                    ans[i] += {Ans{1, cur}, Ans{2, mp[col].first, cur}};
106
                    if(stk[mp[col].first][0])
107
                        unfix += {mp[col].first, 0},
108
                        mp[stk[mp[col].first][0]].second = 1;
109
                    else
110
                        unfix += {mp[col].first, 1};
111
                    stk[mp[col].first][1] = stk[mp[col].first][0];
112
                    stk[mp[col].first][0] = 0;
113
                    mp[col] = {0, 0};
114
                }
115
                else{
116
                    ans[i] += {Ans{1, mp[col].first}};
117
                    unfix += mp[col];
118
                    stk[mp[col].first][mp[col].second] = 0;
119
                    mp[col] = {0, 0};
120
                }
121
            }else{
122
                if(!unfix.empty()){
123
                    ans[i] += Ans{1, unfix.back().first};
124
                    mp[col] = unfix.back();
125
                    stk[mp[col].first][mp[col].second] = col;
126
                    unfix.pop_back();
127
                }else{
128
                    int nxt;
129
                    for(nxt = i + 1; nxt <= M; ++nxt){
130
                        if(a[nxt] == col)break;
131
                        // if(!ans[nxt].empty())continue;
132
                        int ccol(a[nxt]);
133
                        if(!mp[ccol].first){
134
                            ans[nxt] += Ans{1, mark[ccol].first};
135
                            unfix.erase(find(unfix.begin(), unfix.end(), mark[ccol]));
136
                            mp[ccol] = mark[ccol];
137
                            stk[mp[ccol].first][mp[ccol].second] = ccol;
138
                            mark[ccol] = {0, 0};
139
                            // if(!unfix.empty()){
140
                            //     ans[nxt] += Ans{1, unfix.back().first};
141
                            //     mp[ccol] = unfix.back();
142
                            //     stk[mp[ccol].first][mp[ccol].second] = ccol;
143
                            //     unfix.pop_back();
144
                            // }else{
145
                            //     printf("Error\n"), exit(0);
146
                            // }
147
                        }else{
148
                            if(!mp[ccol].second){
149
                                mark[ccol] = mp[ccol];
150
                                ans[nxt] += Ans{1, mp[ccol].first};
151
                                unfix += mp[ccol];
152
                                stk[mp[ccol].first][mp[ccol].second] = 0;
153
                                mp[ccol] = {0, 0};
154
                            }else{
155
                                if(stk[mp[ccol].first][0]){
156
                                    ans[i] += Ans{1, mp[ccol].first};
157
                                    ans[nxt] += {Ans{1, cur}, Ans{2, mp[ccol].first, cur}};
158
                                    int stkpos = mp[ccol].first;
159
                                    mp[stk[mp[ccol].first][0]].second = 1;
160
                                    mp[col] = {mp[ccol].first, 0};
161
                                    mp[ccol] = {0, 0};
162
                                    stk[stkpos][1] = stk[stkpos][0];
163
                                    stk[stkpos][0] = col;
164
                                    break;
165
                                }else{
166
                                    stk[mp[ccol].first][0] = 0;
167
                                    ans[i] += Ans{1, cur};
168
                                    ans[nxt] += Ans{1, mp[ccol].first};
169
                                    mp[col] = {cur, 1};
170
                                    unfix += {cur, 0};
171
                                    cur = mp[ccol].first;
172
                                    for(auto it = unfix.begin(); it != unfix.end();)
173
                                        if(it->first == cur)it = unfix.erase(it);
174
                                        else advance(it, 1);
175
                                    stk[mp[ccol].first][1] = 0;
176
                                    mp[ccol] = {0, 0};
177
                                    break;
178
                                }
179
                            }
180
                        }
181
                    }
182
                    if(ans[i].empty()){
183
                        ans[i] += Ans{1, cur};
184
                        ans[nxt] += Ans{1, cur};
185
                    }i = nxt;
186
                }
187
            }
188
            // printf("Finish %d\n", i);
189
            // printf("unfix: ");
190
            // for(auto tmpp : unfix)printf("(%d, %d) ", tmpp.first, tmpp.second ? 1 : 0);
191
            // printf("\n");
192
            // for(int i = 1; i <= 3; ++i)
193
            //     printf("mp[%d] = %d, %d\n", i, mp[i].first, mp[i].second ? 1 : 0);
194
        }
195
        ll tot(0);
196
        for(int i = 1; i <= M; ++i)tot += ans[i].size();
197
        printf("%lld\n", tot);
198
        for(int i = 1; i <= M; ++i)
199
            for(auto opt : ans[i])
200
                if(opt.flag == 1)printf("1 %d\n", opt.a);
201
                else printf("2 %d %d\n", opt.a, opt.b);
202
    }
203
}
204

205
int main(){
206
    int T = read();
207
    while(T--){
208
        N = read(), M = read(), K = read();
209
        for(int i = 1; i <= M; ++i)a[i] = read();
210
        if(K == N * 2 - 2)Sub1::Make();
211
        else Sub2::Make();
212
    }
213

214
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
215
    return 0;
216
}
217

218
template < typename T >
219
inline T read(void){
220
    T ret(0);
221
    int flag(1);
222
    char c = getchar();
223
    while(c != '-' && !isdigit(c))c = getchar();
224
    if(c == '-')flag = -1, c = getchar();
225
    while(isdigit(c)){
226
        ret *= 10;
227
        ret += int(c - '0');
228
        c = getchar();
229
    }
230
    ret *= flag;
231
    return ret;
232
}

UPD

update-2022_12_01 初稿