#P5523. [BJOI2019]奥术神杖

    ID: 4526 传统题 2000ms 512MiB 尝试: 38 已通过: 4 难度: 7 上传者: 标签>动态规划字符串CF2300AC自动机二分DAG-DP杂项分数规划

[BJOI2019]奥术神杖

[BJOI2019] 奥术神杖

题目描述

Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段,世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器,试图借助神器的神秘力量帮助她们战胜地灾军团。

在付出了惨痛的代价后,精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后,神杖上镶嵌的奥术宝石已经残缺,神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石,并重金悬赏天下能工巧匠修复这件神杖。

你作为神术一脉第五百零一位传人,接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 nn 颗奥术宝石,奥术宝石一共有 1010 种,用数字 "0123456789" 表示。有些位置的宝石已经残缺,用 "." 表示,你需要用完好的奥术宝石填补每一处残缺的部分(每种奥术宝石个数不限,且不能够更换未残缺的宝石)。古老的魔法书上记载了 mm 种咒语 (Si,Vi)(S_i,V_i) ,其中 SiS_i 是一个非空数字串,ViV_i 是这种组合能够激发的神力。

神杖的初始神力值 Magic=1Magic = 1,每当神杖中出现了连续一段宝石与 SiS_i 相等时,神力值 MagicMagic 就会乘以 ViV_i。但神杖如果包含了太多咒语就不再纯净导致神力降低:设 cc 为神杖包含的咒语个数(不同咒语分别计数,同一咒语出现在不同位置也分别计数,匹配区间可以重叠),神杖最终的神力值为 Magicc \sqrt[c]{Magic}。(若 c=0c = 0 则神杖最终神力值为 11 )

例如有两种咒语 (01,3)(01,3) 、(10,4)(10,4) ,那么神杖 “0101” 的神力值为 3×4×33\sqrt[3]{ 3 \times 4 \times 3}

你需要使修复好的神杖的最终的神力值最大,输出任何一个解即可。

输入格式

第一行两个正整数 nn 、mm ,表示宝石数和咒语数。

第二行为一个长度为 nn 的字符串 TT ,表示初始的神杖。

接下来 mm 行每行一个非空数字串 SiS_i 和一个正整数 ViV_i ,表示每种咒语。

输出格式

输出一行长度为 nn 的数字串,表示修复后的神杖。保留所有未残缺位置上的数字。若有多种最优修复方案,输出任意一种。

样例 1

4 3
....
1 2
2 2
3 1
2019

样例 2

5 4
..0..
0 2
00 2
01 4
10 3
11012

样例 3

18 6
...2.1.0.1..1.0..1
011 6
111 4
010 12
121 7
101 5
10 3
121211203112120121

提示

样例 1 :法杖最终神力值为 22 。

样例 2 :法杖最终神力值为 2×3×43\sqrt[3]{2 \times 3 \times 4}

设 s=∑i=1m∣Si∣s = \sum_{i=1}^{m} |S_i| ,即所有咒语的串长之和。 | 测试点 | nn | ss | 特殊性质 | | --- | --- | --- | --- | | 1–3 | 1≤n≤61\le n\le6 | 1≤s≤201\le s\le20 | 无 | | 4–5 | 1≤n≤5011\le n\le501 | 1≤s≤51\le s\le5 | 无 | | 6 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | 所有 ViV_i 相同 | | 7 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | ViV_i 最多有两种不同取值 | | 8 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | ViV_i 最多有三种不同取值 | | 9–11 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | TT 全由句点组成 | | 12–13 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | TT 最多有三个位置是句点 | | 14–16 | 1≤n≤5011\le n\le501 | 1≤s≤5011\le s\le501 | 无 | | 17–20 | 1≤n≤15011\le n\le1501 | 1≤s≤15011\le s\le1501 | 无 |

对于所有数据,1≤m≤15011\le m\le1501,1≤Vi≤1091\le V_i\le10^9,所有 SiS_i 互不相同。