#2119. 字典树
字典树
字典树
题目描述
IOI 2018 中国国家队选拔赛暨精英赛 第二试字典树(trie) 字典树(trie) 【题目描述】 Access Globe 有若干个.递.增的正整数序列。他把这些正整数序列中的每个正整数 的十进制表示(无前导零)依次写了下来,相邻两个整数之间用逗号, 隔开。Access Globe 把这个序列视为一个由0 −9 的数字和逗号, 组成的字符串,然后用一棵Trie 树存储这些字符串。你并不需要知道Trie 树究竟是什么,你只需要知道,Access Globe 得到的Trie 是一棵以0 号节点为根的有根树,每条边上都有一个字符,并且从根到每 个.叶.节.点的路径上的边上的字符顺次拼接构成的字符串是一个他写下的一个递增的正 整数序列。 可爱的小Tommy 决定篡改这棵Trie 树。他先将Trie 上的一些边上的字符删去, 然后填上另一些字符。为了不被发现,Tommy 必须保证修改后的Trie 仍然满足上述性 质,即从根到每个叶节点的路径上的边上的字符顺次拼接构成的字符串是一个递增的 正整数序列,且每个正整数.无.前.导.零。 现在Tommy 已经删去了一些边上的字符,请你帮他完成‘‘填上字符’’ 的操作。如 果有多解,请输出字典序最小的解。 【输入格式】 从文件trie.in 中读入数据。 输入文件包含多组数据,整个文件的第一行是一个整数T,表示数据组数。对于每 一组数据: 第一行包含一个长度为n 的、仅包含0 到9、, 和? 的字符串,第i 个整数表示 连接节点i 的父亲和节点i 的边上的字符,? 表示这条边上的字符已经被删去; 第二行包含n 个整数,第i 个整数表示节点i 的父亲节点fi,保证0 ≤fi < i。 【输出格式】 输出到文件trie.out 中。 输出T 行。对于每组数据,输出一个长度为n 的字符串,表示字典序最小的填写 问号的方式中每个点的字符,第i 个整数表示节点i 的字符。 如果不存在任何合法的填写方式,请输出failed。 【样例1 输入】 1 2,?3,2?71?4420?2641? 0 1 2 3 4 5 6 7 8 6 10 7 4 4 14 3 2 1 1 0 第4 页 共8 页 IOI 2018 中国国家队选拔赛暨精英赛 第二试字典树(trie) 【样例1 输出】 2,13,207104420026411 【样例1 解释】 Tommy 填写的Trie 如下图,红色的节点为所有叶子节点,注意,根节点在左下方。 【样例2】 见选手目录下的trie/trie2.in 与trie/trie2.ans。 【子任务】 对于20% 的数据,T ≤10,对于每组数据n ≤80 ,? 个数不超过8; 对于另外10% 的数据,T ≤20 ,对于每组数据n ≤80, fi = i −1; 对于另外20% 的数据,fi = i −1; 对于另外10% 的数据,n ≤80; 对于所有数据,T ≤100 对于每组数据n ≤200。 【提示】 , 的ascii 码为44 ,比所有的数字都要小。 第5 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
2,?3,2?71?4420?2641?
0 1 2 3 4 5 6 7 8 6 10 7 4 4 14 3 2 1 1 0
2,13,207104420026411