首页 > 其他分享 >题解 [AGC044C] Strange Dance

题解 [AGC044C] Strange Dance

时间:2022-11-06 15:33:17浏览次数:47  
标签:bas Dance 题解 rep son int AGC044C now void

这道题启示我们 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

相关文章

  • KMP 自动机,孤独的自动机(同时也是CF1721E的题解)
    给定字符串\(s\),以及\(q\)个串\(t_i\),求将\(s\)分别与每个\(t_i\)拼接起来后,最靠右的\(|t_i|\)个前缀的border长度。询问间相互独立。\(|s|\leq10^6,q......
  • 【题解】洛谷P2725 [USACO3.1]邮票 Stamps
    从n种邮票中选出不超过k张邮票,使选出来的邮票可以表示1~m之间(含)的所有数。每张邮票在不超过k的前提下,都可以使用无数次,因此可以将问题看成一个完全背包问题。n种邮票就是n......
  • [ARC069F]Flags 题解
    因为一个小错误整整调了一天qwq除去2-SAT部分没学过去学了一下,其它部分都想出来了,四舍五入我自己写了一道Cu,好欸(虽然这Cu好像非常水QAQ)。F-Flags一条数轴上有......
  • P8813(CSP-J2022T1)题解
    题意:算a ^ b,如果结果超出1e9就输出-1,反之输出结果。思路:边算边判加特判。代码:#include<cstdio>#definelllonglong#definemx1e9//边界usingnamespacestd;i......
  • P8814(CSP-J2022T2)题解
    题意:给定一个正整数 k,有k 次询问,每次给定三个正整数 n, e, d,求两个正整数 p, q,使 n = p × q且e × d =(p −1)×(q −1)+1。思路:通过题意可以发......
  • AtCoder Beginner Contest 276 A~G 题解
    今天凌晨CFD题差一句判断AC,晚上ABCG题把插板法和快速幂搞混差点AC。事不过三,再这样一次我直接紫砂。太简单的题就不放翻译和代码了。(事实上这场A-E都是大水题......
  • 个人比赛实况和题解
    CodeforcesCF1740:实况:https://pan.baidu.com/s/1BYjUp2Atvqkpqe3jVogPTQ(提取码:1104);题解:https://www.cnblogs.com/lucius7/p/16861747.html。AtCoderabc275:实况:https://p......
  • 洛谷P8757 [蓝桥杯 2021 省 A2] 完美序列 题解
    思路为使描述方便,先令题目描述中的“完美序列”反转(即序列单调递增且每一个数都是上一个数的倍数)。原“完美序列”与反转后的本质相同。先考虑最大长度。显然,当完美序列......
  • 洛谷P8775 [蓝桥杯 2022 省 A] 青蛙过河 题解 贪心+二分答案
    题目链接​​https://www.luogu.com.cn/problem/P8775​​题目大意小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条......
  • 洛谷-P8814 题解
    前言蒟蒻感叹!许多大佬的思路真的很复杂,于是为了部分没学过的人写了这篇题解(其实就是为了咕值),值得一看!正文♦算法:式子推导从题中可得\(\begin{cases}n_i=p_i\times......