#P1249. 2023.05.06-春招-第一题-移动01字符串

2023.05.06-春招-第一题-移动01字符串

题目内容

塔子哥突然收到一封信,里面有一个一个十六进制数,信里提到,这个十六进制数表示一个长度为 nn0101 字符串。

信中写道,你能否通过左右移动一个和该0101字符串相同的字符串,来用11覆盖掉原字符串中的0000 并不会覆盖 11),使得原字符串变成一个长度为 nn 的全 11 字符串。如果可以请将方案写出,如果同时存在多个方案,请写下移动次数最少的方案。

塔子哥一直在思考这个问题该如何解决,你能帮助塔子哥解决这个问题吗?

输入描述

输入第一行为 0101 字符串的长度 nn 。( 10n102410\le n\le 1024

输入第二行为 nn 个bit的序列,用双字节十六进制数表示,如果 nn 超过 1616 ,则用多个双字节十六进制表示,它们之间用空格分割。

有效bit从第一个十六进制的最高位开始计算,序列尾部如果有无效bit则用 11 填充。

输出描述

输出第一行为可以变化为全 11 字符串的方案个数,同一个方向只需要给出移位最少的方案。如果无法变为全 11 字符串,则输出 00

输出从第二行开始,每两行为一组。

第一行为平移方向和平移的次数,用 +X 表示向右为 + ,向左为 - ;

第二行为一个长度为 nn0101 字符串,表示移动后字符串中哪些位置的 11 将覆盖原始位置的 00

如果存在多个方案,先输出向右移动的方案

样例

样例一

输入

13
0xEEEE

输出

2
+1
0010001000100
-1
0000100010001

样例解释

输入的十六进制数为:0xEEEE , 二进制为1110111011101110 , 截取n=13n=13 得到1110111011101

肉眼观察可以发现有两种方案,分别是右移 11 个位置和左移 11 个位置。对应的 0101 连续字符序列表示移动后字符串中哪些位置的 11 将覆盖原始位置的 00

样例二

输入

20
0xEEEF 0x3FFF

输出

2
+2
01000100010000110000
-2
00000100010001000011

样例解释

输入的十六进制数 0xEEEF 0x3FFF,截取前n=20n=20位,转换为二进制序列为 11101110111011110011

肉眼观察可以发现有两种方案,左移 22 个位置 和 右移两个位置 。 对应的 0101 连续字符序列表示移动后字符串中哪些位置的 11 将覆盖原始位置的 00