当前位置:首页 > 查找 > 正文
洛谷P1942词编码[NOI导刊]
96+

题目大意:一个长度为n的01串,1的位置适合是n+1的倍数,但现在要么其中一个0被1取代,要么删除了一位,要么多了一位,请问原串是什么?

题目描述

一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。在其尽头的接收机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最初长度都为n(4<=n<=1000)。当穿过隧道之后单词可能发生以下几种情况之一:

1. 任意(一个)0被1取代
2. 任意(一个)符号被删除
3. 一个符号(0或1)被插入到任何位置
4. 不改变

我们知道最初的单词都具有以下性质:有1的位置号的总和是n+1的倍数,或者是0.

输入输出格式

输入格式

n和转换后的单词,每个单词占一行。单词数不大于2001,不会有其他任何东西,除了一些空格和空行。

输出格式

你的程序应该打印输出原始序列的词,注意换行。

若有多解,操作4优先,不行则按操作1,2,3优先。同一操作,按操作位置最优的优先(从左到右数起1,2,3……n),还有操作2时,被删数列,先在被删数列添0,不行再添1。

如果没答案输出-1。

输入输出样例

输入样例 #1

4
0000
011
1011
11011

输出样例 #1

0000
0110
1001
1111

解题思路

分类讨论,先考虑操作4,如果位置之和符合要求就是4;长度为n考虑操作1,如果从前往后尝试把其中一个1换成0满足要求,即找到答案;长度为n-1考虑操作2,如果从前往后尝试插入0或1满足条件,即找到答案;长度为n+1考虑操作3,如果从前往后删除某一位满足条件,即找到答案。其他情况都是无解。删除、插入一位,对后面的影响,就是后面的1的位置全部减1和加1,可以用后缀和优化。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P1942词编码[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter