USACO: Cryptcowgraphy

The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.

Specifically, if one cow has a message, say, "International Olympiad in Informatics", it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part of the message between C and O, and the part between O and W, and swap them. Here are two examples:

            International Olympiad in Informatics
                              -> 
            CnOIWternational Olympiad in Informatics
            
            International Olympiad in Informatics
                              -> 
            International Cin InformaticsOOlympiad W

To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John's cows receive such a multiply-encrypted message. Write a program to compute whether or not the non-encrypted original message could have been the string:

            Begin the Escape execution at the Break of Dawn

PROGRAM NAME: cryptcow

INPUT FORMAT

A single line (with both upper and lower case) with no more than 75 characters that represents the encrypted message.

SAMPLE INPUT (file cryptcow.in)

Begin the EscCution at the BreOape execWak of Dawn

OUTPUT FORMAT

Two integers on a single line. The first integer is 1 if the message decodes as an escape message; 0 otherwise. The second integer specifies the number of encryptions that were applied (or 0 if the first integer was 0).

SAMPLE OUTPUT (file cryptcow.out)

1 1

解体思路：

又一道变态搜索题，DFS剪枝（一下特殊字符指COW）：

1、比较原始串和加密串的字符，除了COW这三个字母以外，其它字符应该是一样多的

2、COW三个字符的个数应该是一样多的

3、如果没有字符O，直接strcmp判断

4、DFS函数中，检测三个特殊字符是否最左边是C，最右边是W

5、DFS函数中，检测每个最长的不含特殊字符的子串是否存在于原始串中

6、DFS函数中，检测整个字符串是否已经搜索过

关于压缩（168~197行）：这个是非必要的，我的解释是减少指针，这是因为我开始想用trie树来做标记处理上述剪枝的第6点，事实说明整个长串用trie来标记是不可行的，就算70+个指针压缩成24个指针都还是会爆内存的

trie树：trie树你懂的！我主要用来标记上述剪枝的第5点

到底怎么hash：

传说字符串用elf来哈希就可以过，不过我看了一下实现代码，太多冲突了，没处理好的话，这道题的终极数据还是要0.9XX过，我一直想弄一个没有冲突的hash出来。

想来想去hash不出来，用trie树试试吧，上面提到，trie准确率是高了，只是在第6还是哪一个数据开始爆内存了。

再想想，完全没有必要整串trie啊，因为里面那些“最长的不含特殊字符的子串”已经存在于trie树中了，我只处理特殊字符，然后把指针回指到root下。这一下内存问题解决了，但是又出一个问题，第9组数据wa了，分析一下，这个方法还是有漏洞的，不过挺难表达，自己理解吧。

还真多亏usaco的数据全面呐，不然全过了的话这个漏洞我就发现不了了。最后再加一点点easy Hash判断，easy Hash有trie的辅助确实很easy，每次判断完“最长的不含特殊字符的子串”，hashIdx += (dfsHlp->b * 100 + dfsHlp->e);问题果然就解决了，效率也比较满意了，哎~~~

/* ID: geterns1 PROG: cryptcow LANG: C++ */ #include <iostream> #include <fstream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; char eMess[80]; char mess[] = "Begin the Escape execution at the Break of Dawn"; //a trie tree for the message string struct trie{ trie *nxt[24]; int b, e; }; // int used = 0; trie list[10000]; //free node list trie *root; //DFS trie *dfsHlp, *chkHlp; bool found = false; bool easyHash[100000]; int depth = 0; void DFS(char str[]){ //check state if (found) return; //check the string int oCnt = 0, oIdx[30]; for (int i = 0; str[i] != '/0'; i ++){ if (str[i] == '5') oIdx[oCnt ++] = i; } //no any deeper search if (oCnt == 0){ //march the initial message if (strcmp(str, mess) == 0) found = true; return; } //should have a leftmost 'C' and a rightmost 'W' bool check = false; for (int i = 0; i < oIdx[0]; i ++){ if (str[i] == '2' || str[i] == '5' || str[i] == '6'){ if (str[i] == '2') check = true; break; } } if (!check) return; check = false; for (int i = strlen(str) - 1; i > oIdx[oCnt - 1]; i --){ if (str[i] == '2' || str[i] == '5' || str[i] == '6'){ if (str[i] == '6') check = true; break; } } if (!check) return; //before a deeper search, check: int sCnt = 0, sIdx[30]; sIdx[sCnt ++] = -1; for (int i = 0; str[i] != '/0'; i ++){ if (str[i] == '2' || str[i] == '5' || str[i] == '6') sIdx[sCnt ++] = i; } sIdx[sCnt ++] = strlen(str); // int hashIdx = 0; check = true; chkHlp = root; for (int i = 1; i < sCnt; i ++){ //check a continuous segment without 'C', 'O', and 'W' dfsHlp = root; for (int j = sIdx[i - 1] + 1; j < sIdx[i]; j ++){ if (dfsHlp->nxt[str[j] - '0'] == NULL) return; dfsHlp = dfsHlp->nxt[str[j] - '0']; } hashIdx += (dfsHlp->b * 100 + dfsHlp->e); //check the connection 'C', 'O', and 'W' if (i < sCnt - 1){ if (dfsHlp != root) chkHlp = dfsHlp; if (chkHlp->nxt[str[sIdx[i]] - '0'] == NULL){ chkHlp->nxt[str[sIdx[i]] - '0'] = list + used ++; check = false; } chkHlp = chkHlp->nxt[str[sIdx[i]] - '0']; if (sIdx[i] + 1 < sIdx[i + 1]){ if (chkHlp->nxt[str[sIdx[i] + 1] - '0'] == NULL){ chkHlp->nxt[str[sIdx[i] + 1] - '0'] = root->nxt[str[sIdx[i] + 1] - '0']; check = false; } } } } if (check && easyHash[hashIdx]) return; easyHash[hashIdx] = true; //now begin depth ++; int lenHlp; char nStr[80]; for (int i = 0; i < oCnt; i ++){ for (int j = 0; j < oIdx[i]; j ++){ if (str[j] == '2'){ for (int k = strlen(str) - 1; k > oIdx[i]; k --){ if (str[k] == '6'){ // lenHlp = 0; for (int l = 0; l < j; l ++) nStr[lenHlp ++] = str[l]; for (int l = oIdx[i] + 1; l < k; l ++) nStr[lenHlp ++] = str[l]; for (int l = j + 1; l < oIdx[i]; l ++) nStr[lenHlp ++] = str[l]; for (int l = k + 1; str[l] != '/0'; l ++) nStr[lenHlp ++] = str[l]; nStr[lenHlp] = '/0'; DFS(nStr); } } } } } if (!found) depth --; } int main(){ freopen("cryptcow.in", "r", stdin); freopen("cryptcow.out", "w", stdout); // gets(eMess); //count and compare the characters int cnt[100], eCnt[100]; memset(cnt, 0, sizeof(cnt)); memset(eCnt, 0, sizeof(eCnt)); for (int i = 0; mess[i] != '/0'; i ++) cnt[mess[i] - ' '] ++; for (int i = 0; eMess[i] != '/0'; i ++) eCnt[eMess[i] - ' '] ++; // if (eCnt['C' - ' '] != eCnt['O' - ' '] || eCnt['O' - ' '] != eCnt['W' - ' ']){ printf("0 0/n"); goto EXT; } //sepcial case if (eCnt['O' - ' '] == 0){ if (strcmp(mess, eMess) == 0) printf("1 0/n"); else printf("0 0/n"); goto EXT; } // eCnt['C' - ' '] = eCnt['O' - ' '] = eCnt['W' - ' '] = 0; for (char c = ' '; c <= 'z'; c ++){ if (cnt[c - ' '] != eCnt[c - ' ']){ printf("0 0/n"); goto EXT; } } //compress and reset all the characters we need, to reduce the pointers char *map[200]; int mapSize; mapSize = 0; for (int i = 0; mess[i] != '/0'; i ++) map[mapSize ++] = mess + i; for (int i = 0; eMess[i] != '/0'; i ++) map[mapSize ++] = eMess + i; int minIdx; for (int i = 0; i < mapSize; i ++){ minIdx = i; for (int j = i + 1; j < mapSize; j ++){ if (*map[minIdx] > *map[j]) minIdx = j; } if (i ^ minIdx){ map[mapSize] = map[i]; map[i] = map[minIdx]; map[minIdx] = map[mapSize]; } } char reCode; int b, e; reCode = '0'; e = -1; while (e != mapSize - 1){ //than 'C' 'O' 'W' become '2' '5' '6' b = ++ e; while (e + 1 < mapSize && *map[e] == *map[e + 1]) e ++; for (int i = b; i <=e; i ++) *map[i] = reCode; reCode ++; } //set flags in the trie tree for strings which are "possible" trie *hlp; memset(list, 0, sizeof(list)); root = list + used ++; for (int i = 0; mess[i] != '/0'; i ++){ hlp = root; for (int j = i; mess[j] != '/0'; j ++){ if (hlp->nxt[mess[j] - '0'] == NULL) hlp->nxt[mess[j] - '0'] = list + used ++; hlp = hlp->nxt[mess[j] - '0']; //begin and end index hlp->b = i; hlp->e = j; } } // memset(easyHash, 0, sizeof(easyHash)); DFS(eMess); if (found) printf("1 %d/n", depth); else printf("0 0/n"); EXT: fclose(stdin); fclose(stdout); return 0; }

搞了好久，必须臭美一下贴贴成绩O(∩_∩)O哈哈~

USER: Geterns Liu [geterns1] TASK: cryptcow LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.011 secs, 3992 KB] Test 2: TEST OK [0.011 secs, 3992 KB] Test 3: TEST OK [0.011 secs, 3992 KB] Test 4: TEST OK [0.000 secs, 3992 KB] Test 5: TEST OK [0.011 secs, 3992 KB] Test 6: TEST OK [0.022 secs, 3992 KB] Test 7: TEST OK [0.011 secs, 3992 KB] Test 8: TEST OK [0.011 secs, 3992 KB] Test 9: TEST OK [0.011 secs, 3992 KB] Test 10: TEST OK [0.023 secs, 3992 KB] All tests OK. Your program ('cryptcow') produced all correct answers! This is your submission #24 for this problem. Congratulations! Here are the test data inputs: ------- test 1 ------- Begin the Escape execution at the Break of Dawn ------- test 2 ------- CBegin the EscCution at the BreOape execWak of OWDawn ------- test 3 ------- Begin the EscCutino at the BreOape execWak of Dawn ------- test 4 ------- Begin the EscCCCCCCution at the BreOOOOOOape execWWWWWWak of Dawn ------- test 5 ------- CaOBegin the EscWpe CnCak OexeOt the BWcutioWofO aCreW Dawn ------- test 6 ------- BCC execuO the EsCinCaWCCreaOpWtiOn at OCDOcOWaOegCeWtheOW BWoWk of Wwn ------- test 7 ------- BegiCoWCWDOk oCthe EscOWaCn Oe Of On WexecutChe BreOOCat tWiWapCWawn ------- test 8 ------- BeCOgC CC execuOf DOBCiCCrWaOOt theCOCeak oWWin Oon aWtheOOW EscapeWtWWWwn ------- test 9 ------- CChCC Oe BWOWEscapCreOeOegin tWOe WatWaOe OBCexCOhWC of O tCWcutionWkWDawn ------- test 10 ------- CCC COhe BWOWEscapCreOeOegin tWOe WatWaOe OBCexCOhWC of O tCWcutionWkWDawn Keep up the good work! Thanks for your submission!