这道题启示我们 Trie 树是可以支持全局下标加 \(1\) 的。
首先把 \(3^n\) 个人从低位到高位建到三进制 Trie 树上。类似二叉树的左右儿子,我们称由 \(0,1,2\) 边连接的儿子为 \(0,1,2\) 儿子。
分析两种操作意味着什么:
- Salasa 舞:交换每一个节点的 \(1\) 儿子和 \(2\) 儿子,打懒标记即可。
- Rumba 舞:这个比较复杂。从最低位开始分析,最低位的变化是 \(+1\pmod{3}\),容易想到轮换一下 \(0,1,2\) 儿子。但是我们还需要处理进位。发现新的 \(1,2\) 儿子轮换后不会有进位,因此不需要管,只有新的 \(0\) 儿子会进位。进位后相当于在新的 \(0\) 儿子的子树内部进行一个 Rumba 舞的操作,沿着 \(0\) 儿子这条链递归下去即可。
于是我们可以 \(\mathcal O(n)\) 地进行单次操作。
统计答案类似于建树,dfs 时根据路径上的数计算位置即可。
时间复杂度 \(\mathcal O(3^n+|T|\cdot n)\)。
// Problem: AT_agc044_c [AGC044C] Strange Dance
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc044_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int K = 13, N = 3e6+5;
int k, n, m, bas[K], ans[N];
char s[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Trie {
int son[N][3], val[N], tag[N], sz;
void build(int u, int d, int now) {
if(d == k) {
val[u] = now;
return;
}
rep(i, 0, 2) {
son[u][i] = ++sz;
build(son[u][i], d+1, now+i*bas[d]);
}
}
void pushdown(int u) {
if(!tag[u]) return;
swap(son[u][1], son[u][2]);
rep(i, 0, 2) tag[son[u][i]] ^= 1;
tag[u] = 0;
}
void add(int u) {
if(!son[u][0]) return;
pushdown(u);
int qwq = son[u][0];
son[u][0] = son[u][2];
son[u][2] = son[u][1];
son[u][1] = qwq;
add(son[u][0]);
}
void dfs(int u, int d, int now) {
if(d == k) {
ans[val[u]] = now;
return;
}
pushdown(u);
rep(i, 0, 2) dfs(son[u][i], d+1, now+i*bas[d]);
}
}trie;
int main() {
scanf("%d", &k);
bas[0] = 1;
rep(i, 1, k) bas[i] = bas[i-1] * 3;
n = bas[k];
trie.build(0, 0, 0);
scanf("%s", s+1);
m = strlen(s+1);
rep(i, 1, m) {
if(s[i] == 'S') trie.tag[0] ^= 1;
else trie.add(0);
}
trie.dfs(0, 0, 0);
rep(i, 0, n-1) printf("%d%c", ans[i], " \n"[i==n]);
return 0;
}
标签:bas,Dance,题解,rep,son,int,AGC044C,now,void
From: https://www.cnblogs.com/ruierqwq/p/agc044c.html