#P15860. [Roi2026]括号与树

    ID: 15071 交互题 2000ms 1024MiB 尝试: 6 已通过: 1 难度: 10 上传者: 标签>算法基础构造字符串树论树哈希CF3000

[Roi2026]括号与树

题目类型

本题是双次运行交互题。每个测试点会启动你的程序两次,分别完成编码和解码。两次运行的内存和文件相互隔离,不能通过全局变量或文件传递信息。请提交带有 main 的完整程序,按下文协议从标准输入读取并向标准输出回答。

题目描述

本题讨论无序有根树:每棵树由根和若干棵子树组成,根的儿子之间没有顺序。仅仅改变儿子的排列顺序,不会改变这棵树。下文简称为“树”。

一棵树可以用正确括号序列编码:

  • 只有一个顶点的树编码为 ()。
  • 若删除根后得到子树 t1,…,tkt_1,\ldots,t_k,这些子树的编码分别为 s1,…,sks_1,\ldots,s_k,则对于任意排列 a1,…,aka_1,\ldots,a_k,原树可以编码为 ( sa1sa2⋯saks_{a_1}s_{a_2}\cdots s_{a_k} )。

每个编码表示恰好一棵树,不能是多棵树编码的直接拼接。例如,(()(())) 和 ((())()) 表示同一棵树:根有两个儿子,一个是叶子,另一个还有一个叶子儿子。

你需要把任意一列树 u1,…,unu_1,\ldots,u_n 编码成一棵树 ww,并能从 ww 恢复原来的有序树列。

**第一次运行:**给出 nn 棵树的括号编码,你需要输出一棵编码树 ww 的括号编码。不同子任务对输出长度有不同限制。

**第二次运行:**给出第一次运行产生的某棵编码树 ww 的括号编码。这个字符串可以与第一次输出不同,树中任意顶点的儿子都可能被重排。你需要恢复第一次输入的那列树,且树列顺序必须完全相同。每棵树的括号表示可以改变,只要树同构即可。

交互协议

每次运行开始,先读取一个整数 tt,其值为 1 或 2,表示当前是第几次运行。

第一次运行(t=1t=1)

需要依次处理多个数据集。每个数据集的第一行给出整数 nn,表示需要编码的树的数量。非结束数据集满足 1≤n≤5000001\le n\le500000,并受下文的总长度限制约束。

  • 若 n=0n=0,表示本次运行结束,你的程序应当退出。
  • 否则,接下来 nn 行各给出一个字符串 sis_i,保证它是某棵树的合法括号编码。

读入后,输出一行字符串,表示你构造的编码树 ww,然后换行并刷新输出缓冲区。

评测器是自适应的:它可以利用本次运行中你先前输出的编码树,构造后续数据集。因此,你必须回答并刷新输出后,才能读取下一个数据集。

第二次运行(t=2t=2)

每个数据集给出一个字符串 ss。

  • 若 ss 为 0,表示本次运行结束,你的程序应当退出。
  • 否则,ss 表示第一次运行产生的某棵编码树 ww,其儿子顺序可能已经改变。

对每个数据集,输出两行:

  1. 第一行输出恢复出的树的数量 nn。
  2. 第二行输出 nn 棵树的括号编码,树与树之间用字符 + 分隔,顺序必须与原输入树列一致。例如恢复 (())、(()()) 时,第二行应为 (())+(()())。

每次回答后都要换行并刷新输出缓冲区。第二次运行中的数据集顺序可能与第一次运行不同。

C++ 可以使用 cout << endl 或 cout.flush() 刷新输出;其他语言请使用对应的刷新方法。

数据范围与评分

设某个数据集的输入编码总长度为 s=∑i∣si∣s=\sum_i |s_i|,第一次运行对该数据集输出的编码长度为 mm。设第 ii 棵输入树有 tit_i 个顶点,则 ∣si∣=2ti|s_i|=2t_i。记一个测试点内所有数据集的 ss 之和为 SS。

每个测试点最多有 100 个数据集,且 S≤106S\le 10^6。必须正确恢复所有树,并满足对应子任务的输出长度限制。

树的数量 nn: 对每个非结束数据集,1≤n≤⌊s/2⌋≤5000001\le n\le\lfloor s/2\rfloor\le500000。这是因为每棵树至少有一个顶点,其括号编码长度至少为 22。一个测试点内所有数据集的树的数量之和也不超过 500000500000。在第1—4子任务中,由 S≤200000S\le200000 可进一步得到 n≤100000n\le100000;其他附加条件(例如第3子任务的 n=2n=2)仍须满足。n=0n=0 仅表示第一次运行结束,不是一个需要处理的数据集。

子任务 分值 输出长度上限 f(s)f(s) 附加限制 必要子任务
1 13 s+2000s+2000 S≤200000S\le 200000,第二次输入字符串与第一次输出完全相同 无
2 7 S≤200000, t1<t2<⋯<tnS\le 200000,\ t_1<t_2<\cdots<t_n
3 6 S≤200000, n=2S\le 200000,\ n=2
4 最高 34 4s+20004s+2000 S≤200000S\le 200000,按下文公式评分
5 最高 11 s+2000s+2000 t1=⋯=tn>1t_1=\cdots=t_n>1,按下文公式评分
6 最高 9 所有 ti>1t_i>1,按下文公式评分 5
7 最高 20 按下文公式评分 1—6

对于第 4 子任务,定义 k=max⁡(0,(m−2000)/s)k=\max(0,(m-2000)/s):

kk 数据集得分
k≤1.5k\le 1.5 34
k=2k=2 20
k=3k=3 10
k=4k=4 5
k>4k>4 0

相邻两行之间的得分用线性插值计算,并四舍五入到最近的整数。

对于第 5、6、7 子任务,定义 c=max⁡(0,m−s)c=\max(0,m-s):

cc 子任务 5 得分 子任务 6 得分 子任务 7 得分
c≤30c\le 30 11 9 20
c=100c=100 7 14
c=200c=200 4 8
c=2000c=2000 2 4
c>2000c>2000 0

相邻两行之间同样进行线性插值并四舍五入。一个测试点的得分取其所有数据集得分的最小值,一个子任务的得分取其所有测试点得分的最小值;必要子任务须全部通过。

交互示例

下面分别汇总两次运行的输入与输出。实际交互时,仍须在读入每个数据集后立即输出回答并刷新缓冲区,不能等待读完整个输入后再回答。

第一次运行

1
3
()
(())
(()())
1
((())())
0
((()(()())))
((((((((()))))))))

第二次运行

第二次可以按相反的数据集顺序询问,并改变编码树中儿子的排列顺序。恢复每棵输入树时,可以输出任意同构的括号表示。

2
((((((((()))))))))
(((()())()))
0
1
(()(()))
3
()+(())+(()())

示例只展示协议和树的等价表示,不规定具体编码算法。

本地交互测试工具及说明