USACO/cryptcow

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .3中的OI题目Cryptcowgraphy的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 问题分析

很考验人的一道搜索题。感觉比fence rails还要难……我的代码写了170多行。基本的思路很简单：按从小到大的顺序依次找出C,O,W，然后交换中间的两个串并将这三个字符删掉。如此往复直到没有成对的C,O,W，判断一下最后生成的字符串是否是题目所给的串。但是单纯的按上述算法只能通过20%的数据。我们需要进一步优化。 //我用朴素过了50%的数据——whx 这说明竞赛时骗分的正确性

[编辑] 优化技巧

由于添加的COW是一起的，因此给出的字符串的字符个数应该等于47（目标字符串的长度）+3*k。如果不满足就可直接判断无解。
除了COW三个字符外，其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。
搜索中间肯定会出现很多相同的情况，因此需要开一个hash来记录搜索到过哪些字符串，每搜索到一个字符串，就判重。如果重复直接剪枝。这里的字符串的hash函数可以采用ELFhash，但由于ELFhash的数值太大，所以用函数值对一个大质数（我用的是99991）取余，这样可以避免hash开得太大，同时又可以减少冲突。
对搜索到的字符串，设不包含COW的最长前缀为n前缀（同样也可以定义n后缀），那么如果n前缀不等于目标串的长度相同的前缀，那么当前字符串一定无解，剪枝。N后缀也可采取相同的判断方法。
一个有解的字符串中，COW三个字母最早出现的应该是C，最后出现的应该是W，如果不满足则剪枝。
当前字符串中任意两个相邻的COW字母中间所夹的字符串一定在目标串中出现过。如果不符合可立即剪枝。
需要优化搜索顺序。经过试验我们可以发现，O的位置对于整个COW至关重要。可以说，O的位置决定了整个串是否会有解。因此，我们在搜索时，应该先枚举O的位置，然后再枚举C和W的位置。其中W要倒序枚举。这样比依次枚举COW至少要快20~30倍。
在判断当前串的子串是否包含在目标串中的时候，可以先做一个预处理：记录每一个字母曾经出现过的位置，然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。

经过上述优化，程序对于极端数据也可以在1s以内出解。

其实只用3、4、6、7就可以进1s。

事实证明优化6相当重要！

-------------------------------------------------------------------------

by starwar

仅靠上面的优化似乎还不够？

看了本题用hash来写的代码，发现好多用了hash的代码都是没有处理冲突的，

因此貌似上面解法真正快的原因是hash数组的规模较小？

因为hash数组规模较小，又不处理冲突，所以很多不同字符串在搜索的时候被跳过了。

我自己用ELFHash时，用99991取余，确实最差的数据也能在0.5s左右过掉，

但改为1000003后，连第九个数据都很难过~直接TLE~

//顺便说一句：我卡在第8个点是因为先hash再进行普通剪枝，那些不可能的状态也会记为有用，很快就把hash数组填满了，程序就输出无解了。mhy

-------------------------------------------------------------------------

BY BSBandme 官网最新给出的超级剪枝！！！！！！！！！ms用了这就不用那个万恶的elfhash了....

而且这根本不叫剪枝了，不用搜索，直接就算出来了... /*

* How to solve this problem
* First you must notice the following, crucial fact. 
* Call the encrypted message Hmm, and the original message Moo.
* Call a maximal subsequence (possibly empty) of non-COW letters in Hmm
* a "segment."
* If encryption was applied N times, then
* there are 3N+1 segments.
* Suppose that the triples of C's, O's, and W's to which encryption was
* applied are (C_1, O_1, W_1) ... (C_N, O_N, W_N).
* Knowing only these triples -- without knowing
* the order in which the triples were applied -- one can
* determine what the original message must have been;
* the order that the segments originally appeared must have
* been as follows:
*  - the first segment in Moo is the first segment in Hmm
*  - if the kth segment in Moo is the segment of Hmm that ends at C_i, then
*    the (k+1)th segment in Moo is the segment in Hmm that starts with O_i,
*  - if the kth segment in Moo is the segment of Hmm that ends at O_i, then
*    the (k+1)th segment in Moo is the segment in Hmm that starts with W_i,
*  - if the kth segment in Moo is the segment of Hmm that ends at W_i, then
*    the (k+1)th segment in Moo is the segment in Hmm that starts with C_i,
* This is the crucial fact.
*/

大意大概是：C，O，W将新字符串分割为3k+1段。这3k+1段首先应能在原字符串里找到。然后

若原字符串第i段在新字符串中由C结尾，则原字符串第i + 1段必在新字符串里由O开头。

若原字符串第i段在新字符串中由O结尾，则原字符串第i + 1段必在新字符串里由W开头。

若原字符串第i段在新字符串中由W结尾，则原字符串第i + 1段必在新字符串里由C开头。

大家稍微试一下就明白为什么了...而且最关键的是: 根据原字符串第i段和第i + 1段可以相应的找出对应的C, 0, W，不用搜索了!!!!!!!!！！！！！！

例如

CBegin the EscCution at the BreOape execWak of OWDawn

原字符串分为

1：Begin the Esc 2：ape exec 3：ution at the Bre 4：ak of 5：Dawn, 另外6，7两段为空段。

新字符串简化为

C 1 C 3 o 2 W 4 o W 5（由于‘O'难分辨此处改为小写）

1由C结尾则2必由0开头，2由W结尾则3必由C开头.........

经检验没有问题。

然后1结尾的C必和2开头的0是同一次操作的C，O，W。而2结尾的W必和3开头的C是同一次操作。而三开头的C又是1结尾的C。所以可以判断1结尾的C，2开头的0(3结尾的0），2结尾的W为一次操作....

由此可以找出所有操作对应的C,0,W。ms各个操作之间顺序对结果没有影响...

至此，所有对应的C，0，W均找出。

要注意的是会有空段和重复段。所谓重复段就是有两段或以上是相同的，这就要多算几次....

ps: 上文中 #define ms 貌似; ....

另外想尝试的童鞋注意了，给出的标程有465lines....

by w405229619

对于上面的方法不是很明白，我理解下来是先把输入化简成C 1 C 3 o 2 W 4 o W 5这样子的一

个字符串，然后不需要搜索只需要遍历一遍，如果出现了3种情况的反例，就输出0 0。但我在第

7个测试用例的时候就发现存在一个字符串

“1 C 8 W C W 15 o 13 C 3 o W 12 C 9 o 5 o 14 o 2 W 6 C 11 o o C 10 W 7 W 4 C W 16”

应该是可以有解的，但6是由C结尾，而7是由W开头。无奈最后还是在这个生成这个字符串的基础

上用了搜索，加上下列的判断之后最后一个数据在0.5s过了

1跟上面说的一样，先枚举o在倒叙枚举W，这个效率确实提升很多。

2每次删除一组COW，交换之前先判断衔接起来的两个数字是否差为1，如果不相邻的两个数字被连接到了一起，之后是不可能出答案的。

3COW最早出现的不是C或者最后出现的不是W的，剪枝。

[编辑] 侥幸而科学的过法

哈希开小能过完全可以理解，因为最后几组的大数据都是无解的，你哈希开得越小（而且没判重），只要能侥幸的过了前几个小数据，后面的大数据，你不小心把几个可能是解的情况剪掉了，不仅仅加快了运算速度，又不会影响结果（反正没解）。实际上对于无解的情况，你在怎么掉换搜索顺序都是没有用的（整棵树都必须搜索的，决定性搜索顺序只对估价函数的效率有影响），而有些人通过这种方法过，只不过是充分利用了哈希冲突（把可能解剪了，这种致命的错误在却这里恰到好处)。所以说这里有一些侥幸。

但是，它让那么多人过了，也有它的科学性。而对于哈希冲突，我们可以发觉，往往在搜索树很大的情况下（特别是无解），它会越发密集，把它搜完却会耗费很多功夫，那不如牺牲解的一点正确性来换取时间（否则，我们也不指望在规定的时间算出解了），即把它设计成状态密集时，就自动剪掉一些可能解。而且，可以理解的是，这种方式在无解的情况下效果越发明显（可行解迟迟未出），而恰恰在这种情况下，我们更应该舍弃无谓的解。所以，这种方法也有它的科学性。

jzoi

如果要确保正确性，需要加上冲突判断。但此时貌似还要加上标程的第四点优化才不致超时。

“Fourth, undoing the encryption can be done more quickly by basically storing the sequence as a linked list. For each letter location, store the index into the original message the corresponds to the next letter in the current message (and also maintain the index of the first letter). Thus, undoing an encryption corresponds to taking the link from the letter before the C and pointing it to the letter after the O, taking the link from the letter before the W and pointing it to the letter after the C, and taking the pointing from the letter before the O and pointing it to the letter after the W.”

这样效率就很高~

-------------------------------------------------------------------------

by talenth1 /

我做的很郁闷。
我的程序不知怎么，有时候剪枝以后还慢些，剪枝应该以什么方式实现代价小？？？
还有，实在剪了枝也过不了的可以把搜索数量限制在几万。
另外，发现adventop的c++代码有点不对。他没处理hash的冲突，不剪枝反而错。

//-------------------------------------------------------------------------

这个题确实很讨厌，裸着的算法是不可能出解的，第6个点我等了20多秒都没跑完。我没用hash，主要利用上面老兄提到的第六个剪枝，写Trie判是否存在，成功让9.10都在4秒内出解，然后卡一下时900000就好。

-------------------------------------------------------------------------

我是正着搜索的，没有倒推，在对c o w的枚举中分别应用优化6，不满足直接break这层循环，因为此次不满足优化6那么再往下的一定不满足优化6，这样会节约大量时间,即

 for i:=1 to l do
     if s[i]='C' then
       s1:=copy(s,1,i-1);
       if cut2(s1)<>-1 then
       break;
       for j:=i to l do
         if s[j]='O' then
           s1:=copy(s,i,j-i-1);
           if cut2(s1)<>-1 then
           break;
           for k:=j+1 to l do
             if s[k]='W' then
               begin
                 if cut2(s1)<>-1 then break;
               end;

----------------------------------------------------------------------------------------

得分技巧：对于读入的字符串，判断任意C与O或O与W之间字符串（且不含两边及中间的C,W,O才符合)是否在目标字符串中出现过，如没有直接输出无解，不然计算有多少个‘COW’，输出结果，可以过1-8,10,9个点，只有唯一一个点过不去，应该是其给出字符串构成不符合以上关系（即COW成对出现，或其长度不满足47+k*3）。
附：这题搜索能把人搜死，对于时间就是金钱的oier来说，不要在一题上花费过多的时间，那样不值得。

----------------------------------------------------------------------------------------

虽然这道题比较麻烦，但是如果能够将每一个剪枝都弄懂，能够对你的编程能力有很大的提高。——TCtower

[编辑] 投机取巧

SDBMHASH+卡时可以过9个点。

[编辑] 范例程序