Liveddd's Blog

愛にできることはまだあるかい

[AGC044C] Strange Dance

发表于 更新于 分类于
本文字数： 1.7k 阅读时长 ≈ 4 分钟

Trie 树的 全局 +1 操作 trick。

比较经典的 trick。我们容易发现按照 Trie 常规建法从高位向低位建不好进行该操作。于是从低位向高位建 Trie。而我们现在只需要直接交换当前节点的儿子即可。如何考虑进位呢？进位只会发生在交换后的该位为 $0$ 的儿子上。于是我们直接不停地交换儿子，再沿着 $0$ 链走。P6623 [省选联考 2020 A 卷] 树 就可以利用这个 trick 比较简单地解决。

Code
 
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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e6+10,M=2e5+10,K=12,C=3;

int n,m;
char s[M];
int pw[K],ans[N];
int tot=1,ch[N][3],tag[N],val[N];
void build(int d,int x,int now)
{
    if(d>=n)return val[x]=now,void();
    for(int i=0;i<C;i++)
    {
        ch[x][i]=++tot;
        build(d+1,ch[x][i],now+i*pw[d]);
    }
}
inline void pushdown(int x)
{
    if(!tag[x])return ;
    swap(ch[x][1],ch[x][2]);
    for(int i=0;i<C;i++)tag[ch[x][i]]^=1;
    tag[x]=0;
}
void modify(int d,int x)
{
    if(d>=n)return ;
    pushdown(x);
    int tmp=ch[x][2];
    ch[x][2]=ch[x][1];
    ch[x][1]=ch[x][0];
    ch[x][0]=tmp;
    modify(d+1,ch[x][0]);
}
void get(int d,int x,int now)
{
    if(d>=n)return ans[val[x]]=now,void();
    pushdown(x);
    for(int i=0;i<C;i++)get(d+1,ch[x][i],now+i*pw[d]);
}

int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    scanf("%d %s",&n,s+1);
    m=strlen(s+1);
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*C;
    build(0,1,0);
    for(int i=1;i<=m;i++)
    {
        if(s[i]=='S')tag[1]^=1;
        else modify(0,1);
    }
    get(0,1,0);
    for(int i=0;i<pw[n];i++)printf("%d ",ans[i]);
    return 0;
}