UVAOJ10001

Written by    21:20 March 17, 2015 

UVAOJ10001

Great thanks to:

孟海

难点不在算法，在题意。

题目给一个字符串，然后求是否有一个字符串能够通过题目所给的自动机规则变换过来，如果存在，则输出REACHABLE，否则输出GARDEN OF EDEN，就是寓意始祖，即这个字符串无法通过所给的自动及变换规则变换过来。

Left Cell Right New State Weight
[i − 1] [i] [i + 1]
0 0 0 0 0 * 2^0
0 0 1 1 1 * 2^1
0 1 0 0 0 * 2^2
0 1 1 1 1 * 2^3
1 0 0 1 1 * 2^4
1 0 1 0 0 * 2^5
1 1 0 1 1 * 2^6
1 1 1 0 0 * 2^7
90

这里给的自动机规则就是当字符串中的一个字符左边右边以及它自身都满足自动机规则中的left，cell以及right的时候它自己就可以变成new state的值，然后值得注意的是，每一次父串推子串的时候都是一次性把所有推完，而不是从左往右一个一个推推一个产生一个新的字符串再继续往下推，我一开始就这么理解的所以以为题目就是问给一个串能不能推到一个和自己一样的字符串，后来经过海神指导，才明白这个题目得用子串逆推父串。下面给个具体的逆推过程：

如样例输入的第二个
204 5 10101

其自动机规则如下：

Left Cell Right New State Weight
[i − 1] [i] [i + 1]
0 0 0 0 0 * 2^0
0 0 1 0 0 * 2^1
0 1 0 1 1 * 2^2
0 1 1 1 1 * 2^3
1 0 0 0 0 * 2^4
1 0 1 0 0 * 2^5
1 1 0 1 1 * 2^6
1 1 1 1 1 * 2^7
204

给出的子串是10101，第一个字符是1，由规则可知，1可以由111，110，011或者001产生：

假设是由110产生，那么所求父串的前两个和最后一个就先假设分别1，0和1

The actual arrangement of the cells will be along a circumference, so that the last cell is next to
the first.
意思是第一个字符的左边是最后一个，最后一个的右边是第一个。

接下来子传第二个字符是0，已知的子串第一个第二个分别是1和0，又由规则可得第三个字符可以为1也可以为0（100->0，101->0）。。。

就这样一个一个推下去，会推出父串最后一个字符，然后这个时候父串的字符长度实际上是n+2，因为有一个最后一个字符被复制到最前端去了，这里正好给了一个机会来验证所求父串的合法性，即只要array[0] == array[n]，array[1] == array[n+1]就可以说明所求父串是存在的，也就是REACHABLE，否则就是GARDEN OF EDEN，剩下来的就是简单的回溯了。

P.S：期间因为有一个for循环的8写成了7直接导致我兽性大发神志不清地暴力提交了N次也是醉的不行。

 

Category : acm

Tags : • • •