3697: 第 K 排列(第五轮03)
题目描述
牛牛有一个长度大小为N 的字符串， 字符串中的字符仅包括′N′,′O′,′I′,′P′四种。现 在牛牛把这个字符串中的某些字符隐藏掉，用?字符代替。
例如原本的字符串是"PPPOPPOPO"，牛牛将其隐藏一些字符后一种可能的情况 就是字符串变为"???OP???O"
牛牛想让牛妹猜出这个字符串原来是什么。当然直接去猜的话牛妹肯定过一万年 也猜不出来这个字符串是什么。
所以他告诉牛妹，这个字符串是所有可能的字符串中权值大于等于x， 字典序降 序排列的第k个解。
所谓字典序，是指按照查字典的顺序对字符串进行排序，例如"aac"的字典序就小 于"aba"。
现在牛牛给出了这样一种计算字符串权值的方式，首先牛牛给牛妹一张表格。
表格中右下的 4*4 部分表示字符串中每出现一次行标字母出现在左侧，且列标字 母出现在右侧的情况，整个字符串的权值就要加上对应的数值。
例如：如果字符串中出现了"NN"相连，就要加上a，如果字符串中出现了"IO"相 连，就要加上j，如果出现了"OI"相连，就要加上g。
计算整个字符串的权值就是出现的所有情况权值之和，例如字符串"NNOI"的权 值就为 a+b+g。
请你帮助牛妹找到原来的字符串，如果权值大于等于x可能的字符串数目不够k个， 则直接输出一行"-1"表示无解。
输入
第一行输入三个正整数N, x, k，表示字符串长度，牛牛的字符串是权值大于等于 x，字典序降序排列的第k个解。
接下来一行输入一个长度大小为 N 的字符串，字符串仅包括 ′N′,′O′,′I′,′P′,′?′。 接下来输入一个 4*4 的矩阵表示表格的右下部分，表格的说明见题目描述。
输出
如果存在权值大于等于x的第k个解，则输出这个字符串，否则直接输出一行"-1" 表示无解。
样例输入 复制
4 3 108
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0样例输出 复制
ININ提示
【样例 1 输入】
4 3 108 ????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
【样例 1 输出】
ININ
【样例 2 输入】
4 3 109
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
【样例 2 输出】
-1
【样例 3 输入】
2 10 6
??
0 0 10 0
10 10 0 0
10 0 10 10
0 10 10 0
【样例 3 输出】
IP
【样例 4 输入】
999 69270 1000
??OO?????OIP????OO??P?OINP??PNNIINNN??I????P??OPP?NN???O????IPI?POP
I????NII?P?I??P?IP?NP?PP??PO?IP?NP?O?NONIO???OI?PI??IP?I??IOI?????OP???N
NN??O?????P???O?OI?I?IN?P?IP????ON?N???O???P?POI??II???I?IOPN??NNP???
O???NO????NPP?????P?NI??IN??NI??PI??P??IPII?POP??IN?N??P???O??INP?P???O
???I???O???O?N?NNOPO?IOO??N??????P??N?P?NNNN?O?I?IO??N??N??PNINI??
PIPPPON????I?N???P???OI???NPOI??I?IN???????I???O???PINN??I??I?OIIIO?P?O?P
?O?O?N??ONONIN???I???I?N?I??N?P??OP??ONN??O?ON???????PON???O?PI???
O?O?NOPIIP??N??PNN??????IP??OIO???OO???PN?I??OON??????NNI???NPI??I?P
O?P?PO?IPP?NIINI?I?O??N?PP?O??II?IP?NOOP???IPI?OPN?OIPNONIPI?PPI?NPO
?PPPIPPI???I???I?????IOPPONOIOI?PNPN?N?OO??O?NNIPI???I??N?N???IIN??I?? P??IN???P?????????P???ONN???N?I?NPO??P??INPP??P??P???O??N?NNOO???PN ?O??P???N??P?I??O?OI?????N?PPI?IN?POP???PI????N?NNP???IN?IO?ONP???IO?
?O?N?O?PPNNOOOP??IPNPI?N??N??O?ON?????I?????NO???O?????IP????O?N?
O??IOO?I???IN???P?NOO?PI??NI??II??O?????P?I?N?O??IIIIO??N??N?NOI????I??P
??N?ONN?P??I??IP???O??????OI?N????OO
2 1 99 90
47 65 60 92
43 59 57 28
77 15 46 36
【样例 4 输出】
PPOOPPPPPOIPNPNIOOPNPOOINPNIPNNIINNNPNIOOPNPNIOPPPNNPNIOPN
PNIPIOPOPIOPNPNIIOPNIOOPNIPPNPNPPNIPONIPPNPIOPNONIOPNIOIOPION
IPNIONIOIOPNIOOPNIONNNIOOOPNPNPNIOOOOINININIPNIPNPNIONPNPNI
OOPNPNPOIONIIOPNINIOPNIONNPNIOOPNPNOOPNPNPPNPNPNPPNIONINI
ONIOOPIOOPNIIPIIOPOPNIINPNPNPNIOOPNINPNPNIOOOPNINIOOPNIOPNP
NNOPONIOOOPNPNPNPNPNPNIPPNNNNIONINIOOPNIONPNPNINIOOPIPPP
ONPNPNIONIOOPNIOOIOOPNPOIONININIOOPNPNINIOOOPNPINNPNIONIO
OIIIOOPIOOPIOOOPNIOONONINPNIIOPNIONIIOPNIPNIOPNIONNIOOOONPNI
OOPNPONPNIOOPINIOOOOPNOPIIPNPNPNPNNPNPNPNIPNIOIOPNIOOOPN
PNIINIOONIOOPNPNNIOOPNPIONIOPOOPNPONIPPPNIININIOOOPNIPPIOPNII
NIPPNOOPNPNIPIOOPNIOIPNONIPIOPPIONPOOPPPIPPIOPNIOPNIOPNPNIOP
PONOIOIOPNPNPNIOONIOPNNIPIOPNIOPNPNPNIIINPNIOOPNIINIOOPNPNP
NPNPNPNIOONNPNPNIIONPOPNPNIINPPPNPNIPNIOOOPNPNNOOOPNPNIO
PNPNIONPNPNINIOOOIOOPNPNIPPININIPOPNPNPIOPNPNPNNPNPNINIIOOO
NPNPNIONIOPNIOOPPNNOOOPNIIPNPIONIONIOOOONIOOPNIOOPNPNOPN
IOOPNPNIPNPNIOPNIOPNIOONIOPNINIOOPPNOOOPIOPNIONIINIOOPNPNP
NIONIOPNIIIIOOPNIONPNOIOOPNIOOPNPNIONNIPNIIONIPNIOOOPNPNIOIO
NPNIOOO
【样例 4 说明】
大样例
【数据范围】
对于前 10%的测试数据，保证N ≤ 10, k = 1。
对于前 30%的测试数据，保证N ≤ 10。
对于另 10%的测试数据，保证N ≤ 1000, x = 0。
对于另 10%的测试数据，保证N ≤ 1000, k = 1。
对于另 100% 的测试 数据， 保 证 2 ≤ N ≤ 1000,1 ≤ k ≤ 1000,0 ≤ x ≤ 109, 0 ≤ a, b, c, d, . . . , o, p ≤ 10^4 。