社区讨论

人工翻译。

P3494[POI 2009] KOD-The Code参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo7jrdar
此快照首次捕获于
2023/10/27 02:57
2 年前
此快照最后确认于
2023/10/27 02:57
2 年前
查看原帖
有若干个字符,对于每一个,用一个 0101 串编码它。所有的 0101 串由一棵完全的 trie (每个点有两个儿子)给出(具体方式见输入格式),保证有且仅有每个叶子对应一个字符。
定义对一个 0101 串进行解码的过程是,每次找到一个前缀,满足它对应一个字符,容易知道这样的前缀是唯一的。将这个字符加入答案,将这个前缀从原串中删掉。记 ss 解码的结果是 decode(s)\mathrm{decode}(s)
设一个字符编码为 aa,定义它是好的,当且仅当对于任意两个 0101s,ts,t,有 decode(s+a+t)=decode(s+a)+decode(t)\mathrm{decode}(s+a+t)=\mathrm{decode}(s+a)+\mathrm{decode}(t)。求哪些字符是好的。

输入格式

第一行一个数 nn,表示操作次数。接下来一行一个长 nn 的字符串,其中 0/1 表示在当前结点添加一个儿子,边权为 0/1,并移动过去;B表示添加一个父亲;X表示当前结点是一个字符的编码。保证输入是描述这棵 trie 的最短的可能输入。n3×106n\leq 3\times 10^6 ,所有字符编码的总长 108\leq 10^8

输出格式

一行一个数,表示好的字符的数量。
接下来若干行,从小到大输出每个好的字符是第几个X生成的。

回复

6 条回复,欢迎继续交流。

正在加载回复...