#P15860. [Roi2026]括号与树
[Roi2026]括号与树
题目类型
本题是双次运行交互题。每个测试点会启动你的程序两次,分别完成编码和解码。两次运行的内存和文件相互隔离,不能通过全局变量或文件传递信息。请提交带有 main 的完整程序,按下文协议从标准输入读取并向标准输出回答。
题目描述
本题讨论无序有根树:每棵树由根和若干棵子树组成,根的儿子之间没有顺序。仅仅改变儿子的排列顺序,不会改变这棵树。下文简称为“树”。
一棵树可以用正确括号序列编码:
- 只有一个顶点的树编码为
()。 - 若删除根后得到子树 ,这些子树的编码分别为 ,则对于任意排列 ,原树可以编码为
()。
每个编码表示恰好一棵树,不能是多棵树编码的直接拼接。例如,(()(())) 和 ((())()) 表示同一棵树:根有两个儿子,一个是叶子,另一个还有一个叶子儿子。
你需要把任意一列树 编码成一棵树 ,并能从 恢复原来的有序树列。
**第一次运行:**给出 棵树的括号编码,你需要输出一棵编码树 的括号编码。不同子任务对输出长度有不同限制。
**第二次运行:**给出第一次运行产生的某棵编码树 的括号编码。这个字符串可以与第一次输出不同,树中任意顶点的儿子都可能被重排。你需要恢复第一次输入的那列树,且树列顺序必须完全相同。每棵树的括号表示可以改变,只要树同构即可。
交互协议
每次运行开始,先读取一个整数 ,其值为 1 或 2,表示当前是第几次运行。
第一次运行()
需要依次处理多个数据集。每个数据集的第一行给出整数 ,表示需要编码的树的数量。非结束数据集满足 ,并受下文的总长度限制约束。
- 若 ,表示本次运行结束,你的程序应当退出。
- 否则,接下来 行各给出一个字符串 ,保证它是某棵树的合法括号编码。
读入后,输出一行字符串,表示你构造的编码树 ,然后换行并刷新输出缓冲区。
评测器是自适应的:它可以利用本次运行中你先前输出的编码树,构造后续数据集。因此,你必须回答并刷新输出后,才能读取下一个数据集。
第二次运行()
每个数据集给出一个字符串 。
- 若 为
0,表示本次运行结束,你的程序应当退出。 - 否则, 表示第一次运行产生的某棵编码树 ,其儿子顺序可能已经改变。
对每个数据集,输出两行:
- 第一行输出恢复出的树的数量 。
- 第二行输出 棵树的括号编码,树与树之间用字符
+分隔,顺序必须与原输入树列一致。例如恢复(())、(()())时,第二行应为(())+(()())。
每次回答后都要换行并刷新输出缓冲区。第二次运行中的数据集顺序可能与第一次运行不同。
C++ 可以使用 cout << endl 或 cout.flush() 刷新输出;其他语言请使用对应的刷新方法。
数据范围与评分
设某个数据集的输入编码总长度为 ,第一次运行对该数据集输出的编码长度为 。设第 棵输入树有 个顶点,则 。记一个测试点内所有数据集的 之和为 。
每个测试点最多有 100 个数据集,且 。必须正确恢复所有树,并满足对应子任务的输出长度限制。
树的数量 : 对每个非结束数据集,。这是因为每棵树至少有一个顶点,其括号编码长度至少为 。一个测试点内所有数据集的树的数量之和也不超过 。在第1—4子任务中,由 可进一步得到 ;其他附加条件(例如第3子任务的 )仍须满足。 仅表示第一次运行结束,不是一个需要处理的数据集。
| 子任务 | 分值 | 输出长度上限 | 附加限制 | 必要子任务 |
|---|---|---|---|---|
| 1 | 13 | ,第二次输入字符串与第一次输出完全相同 | 无 | |
| 2 | 7 | |||
| 3 | 6 | |||
| 4 | 最高 34 | ,按下文公式评分 | ||
| 5 | 最高 11 | ,按下文公式评分 | ||
| 6 | 最高 9 | 所有 ,按下文公式评分 | 5 | |
| 7 | 最高 20 | 按下文公式评分 | 1—6 |
对于第 4 子任务,定义 :
| 数据集得分 | |
|---|---|
| 34 | |
| 20 | |
| 10 | |
| 5 | |
| 0 |
相邻两行之间的得分用线性插值计算,并四舍五入到最近的整数。
对于第 5、6、7 子任务,定义 :
| 子任务 5 得分 | 子任务 6 得分 | 子任务 7 得分 | |
|---|---|---|---|
| 11 | 9 | 20 | |
| 7 | 14 | ||
| 4 | 8 | ||
| 2 | 4 | ||
| 0 | |||
相邻两行之间同样进行线性插值并四舍五入。一个测试点的得分取其所有数据集得分的最小值,一个子任务的得分取其所有测试点得分的最小值;必要子任务须全部通过。
交互示例
下面分别汇总两次运行的输入与输出。实际交互时,仍须在读入每个数据集后立即输出回答并刷新缓冲区,不能等待读完整个输入后再回答。
第一次运行
1
3
()
(())
(()())
1
((())())
0
((()(()())))
((((((((()))))))))
第二次运行
第二次可以按相反的数据集顺序询问,并改变编码树中儿子的排列顺序。恢复每棵输入树时,可以输出任意同构的括号表示。
2
((((((((()))))))))
(((()())()))
0
1
(()(()))
3
()+(())+(()())
示例只展示协议和树的等价表示,不规定具体编码算法。