喵了个喵 NOIP2022

[NOIP2022] 喵了个喵

zhennanxie

题目链接： [NOIP2022] 喵了个喵 。

题目描述：

有 nn 个栈，长度为 mm 的序列 aa ，满足 ai∈[1,k]a_i\in[1,k] 。

有两种操作：

  • 1 x 。取出序列第一个元素并置于栈 xx 的栈顶。若栈 xx 的栈顶拥有两个相同元素，则删去他们。
  • 2 x y 。若栈 xx 和 yy 的栈底元素一样，则删去他们。

请合理构造使得最终序列和所有栈均为空。

数据保证有解。

数据范围（多测）：

  • 1≤n≤3001\le n \le 300 。
  • k∈{2n−2,2n−1}k\in\{2n-2,2n-1\} 。
  • ∑m≤2×106\sum m \le 2\times10^6 。

Case #1: k=2n−2k=2n-2

置空一个栈，其余栈最多每个有 22 个元素。

容易发现极限情况是所有可使用的栈全部被沾满，此时由于我空出了一个栈，所以所有元素都可以被消去。

简单模拟就行。

Case #2: n=2n=2

注意到如下两个构造：

1
2
栈1 栈2
1   2
1
2
3
栈1 栈2
1
2

不妨将他们命名为 c1 和 c2 。

先考虑 c2 。

此时若下一个元素是 11 或 22 则是平凡的。

若下一个是 33 ，不妨设下下个为 xx 。

  • x=3:x=3: 平凡。
  • x=1:x=1: 将 33 置于栈 11 的栈顶，然后由于有了一个空栈，所以我们可以利用 xx 把栈底的 11 消掉。此时又变回了 c2 。
  • x=2:x=2: 将 33 置于栈 22 ，然后利用 xx 把栈 11 的栈顶的 22 消掉，这样就回到了 c1 。

再考虑 c1 。

依旧考虑下一个元素为 33 ，下下个为 xx 。

  • x=3:x=3: 平凡。
  • x=1:x=1: 将 33 置于栈 22 的栈顶，然后消掉 11 。此时回到 c2 。
  • x=2:x=2: 同理回到 c2 。

因此我们发现这两种情况总能互通，其余情况是平凡的。

于是我们解决了。

Case #3: nothing

此时我们考虑效仿 k=2n−2k=2n-2 和 n=2n=2 的构造，不难得出这样两个情况：

1
2
3
栈1 栈2 栈3 栈4 栈5 ...
1   2   3   4   5  ...
        6   7   8  ...
1
2
3
栈1 栈2 栈3 栈4 栈5 ...
    2   3   4   5  ...
    1   6   7   8  ...

仍然命名为 c1 和 c2 。

不难发现 c2 仍然可以转化为 c1 。

而 c1 ……并不能转回 c2 。

考虑这样的情况：

1
2
3
栈1 栈2 栈3
1   2   3
        4

然后我们发现，只要下一个元素是 33 我们就会炸掉。

因此我们不能让 c2 变为 c1 。

考虑什么情况下 c2 会变为 c1 。

由于 c2 覆盖了 2n−22n-2 个不同的元素，因此不妨把剩下的那个记为 yy 。序列的下一个元素为 yy ，下下个为 xx 。

不难发现，当且仅当 xx 为栈顶的时候， c2 会变为 c1 。

因此我们要避免这种情况。

注意到情况发生转换仅仅只是因为我把 yy 放到了那一个空着的栈上。所以我不能把 yy 放到空栈上。

又因为如果随便把 yy 放到某一个栈的栈顶，那么那一个栈将会有 33 个元素，中间的元素不好处理。

除非那一个栈的栈底被削掉了。

于是我们 All in all ，当 xx 为栈顶时，我们应该不断的将 xx 变为下一个序列的元素，直到 xx 变为某一个栈的栈底时结束，然后我们就可以把 yy 放到那个栈上，将途中所有的序列元素直接进行消除即可。

细节真多。

代码：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
const int N=630,M=2000010;
int n,m,k,a[M],up[N],dn[N],book[N],s[N],top,T,rt;
int tot,OPT[M<<1],K[M<<1],K2[M<<1];
void re(int opt,int x,int y=0){++tot,OPT[tot]=opt,K[tot]=x,K2[tot]=y;}
bool push(int i){
    if(book[a[i]]){
        int t=book[a[i]];
        if(up[t]==a[i])re(1,t),up[t]=0,book[a[i]]=0,s[++top]=t;
        else {
            re(1,rt),re(2,t,rt);
            if(up[t])s[++top]=t;
            dn[t]=up[t],up[t]=0;
            book[a[i]]=0;
        }
        return 1;
    }
    if(top){
        int t=s[top--];
        re(1,t);
        if(dn[t])up[t]=a[i];
        else dn[t]=a[i],s[++top]=t;
        book[a[i]]=t;
        return 1;
    }
    return 0;
}
void WZH(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)up[i]=dn[i]=0;
    for(int i=1;i<=k;i++)book[i]=0;
    top=0;tot=0;
    for(int i=1;i<n;i++)s[++top]=i;
    rt=n;
    for(int i=1;i<=m;i++){
        // cout<<"LUN: "<<i<<' '<<rt<<"\n";
        // for(int j=1;j<=top;j++)cout<<s[j]<<" ";cout<<"\n";
        if(push(i))continue;
        int t=i+1;
        while(t<=m&&book[a[t]]&&up[book[a[t]]]==a[t])t++;
        if(book[a[t]]){
            int flag=0;
            for(int j=i+1;j<t;j++)if(book[a[j]]==book[a[t]]){flag=a[j];break;}
            if(flag){
                re(1,rt);
                int cnt=0;
                for(int j=i+1;j<t;j++){
                    if(flag!=a[j])push(j);
                    else{
                        if(!cnt){
                            re(1,book[a[j]]);
                            up[book[a[j]]]=0;
                            book[a[j]]=0;
                        }
                        else re(1,rt);
                        cnt++;
                    }
                }
                re(1,book[a[t]]);
                dn[book[a[t]]]=0;
                dn[rt]=a[i];
                book[a[i]]=rt;
                s[++top]=rt;
                if(cnt&1^1){
                    up[rt]=flag;
                    book[flag]=rt;
                    --top;
                }
                rt=book[a[t]];
                book[a[t]]=0;
                i=t;
                continue;
            }
            re(1,book[a[t]]);
            for(int j=i+1;j<t;j++)push(j);
            re(1,rt),re(2,book[a[t]],rt);
            dn[book[a[t]]]=up[book[a[t]]],up[book[a[t]]]=a[i];
            book[a[i]]=book[a[t]],book[a[t]]=0;
            i=t;
            continue;
        }
        re(1,rt);
        for(int j=i+1;j<t;j++)push(j);
        re(1,rt);
        i=t;
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++){
        if(OPT[i]==1)printf("1 %d\n",K[i]);
        else printf("2 %d %d\n",K[i],K2[i]);
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
#endif
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}