這個題，粗看之下還沒怎么看懂，這個應(yīng)該跟我英語水平有關(guān)系。然后再看輸入輸出，漸漸的才明白什么意思。原來是要把2*N張破紙組合
成N張一樣的紙。我歷來思維比較隨便，不是很嚴(yán)謹(jǐn)?shù)哪欠N。然后，想了一下發(fā)現(xiàn)一定會有大于等于N張破紙片是符合前半部分模式的。
那么，可以建一個字典樹，把所有的是前半張紙的找出來。然后根據(jù)這前半張紙，找出剩下的后半張紙（因?yàn)橹酪徽麖埣埖拈L度，所以知道
剩下的半張紙的長度）。但是寫出來就發(fā)現(xiàn)這樣不嚴(yán)謹(jǐn)，是不對的。因?yàn)閱渭兏鶕?jù)已經(jīng)找出來的前半張紙，無法確定后半張紙（事實(shí)上，只能
確定其長度而已）。
那么只能找其它方法了，再檢查了下數(shù)據(jù)范圍，發(fā)現(xiàn)比較小，那么意味著可以暴力求解了。好吧，那就深搜吧。我把所有的破紙片按照它們
的長度分成一些集合，對于長度為len的紙片集合，只要與長度為nAnsLen - len的紙片集合進(jìn)行搜索匹配，找出一個可行的解即可了。我又
想當(dāng)然的認(rèn)為只要匹配一對集合即可了，那么很顯然又是錯的了。好吧，我只能對所有集合進(jìn)行匹配了。對每一對集合進(jìn)行深搜回溯來匹配待
選的Ans，而這個Ans是從第一對集合中搜索出來的答案。
代碼寫得很冗長，很復(fù)雜，差不多200多行了。真的是水平有限，這種題很明顯應(yīng)該有更方便的解法的，而且我的代碼應(yīng)該不至于寫得這么
亂的。
后面還是錯了很多次，發(fā)現(xiàn)了很多bug，比如我如果搜索長度為nAnsLen/2的集合時就必須進(jìn)行特殊處理。還有最后一個樣例后面不能輸
出’\n'，而且uvaoj不能對這個換行判PE，一直是WA，實(shí)在是讓人崩潰。
#include <stdio.h>
#include <string.h>
#define MAX (256 + 10)
#define MAX_NUM (150)
char szLines[MAX_NUM][MAX];
char szAns[MAX];
struct SET
{
int nNum;
char szLines[MAX_NUM][MAX];
bool bUsed[MAX];
};
SET sets[MAX];
char szTmpOne[MAX];
char szTmpTwo[MAX];
int nAnsLen;
bool bFind;
void dfs(int nI, int nNum)
{
if (nNum == 0)
{
bFind = true;
}
else
{
for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
{
for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
{
if (nI == nAnsLen - nI && i == j)
{
continue;
}
if (!sets[nI].bUsed[i] && !sets[nAnsLen - nI].bUsed[j])
{
strcpy(szTmpOne, sets[nI].szLines[i]);
strcat(szTmpOne, sets[nAnsLen - nI].szLines[j]);
strcpy(szTmpTwo, sets[nAnsLen - nI].szLines[j]);
strcat(szTmpTwo, sets[nI].szLines[i]);
//printf("%s\n", szAns);
if (strcmp(szTmpOne, szAns) == 0 || strcmp(szTmpTwo, szAns) == 0)
{
sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = true;
if (!bFind)
{
if (nI == nAnsLen - nI)
{
dfs(nI, nNum - 2);
}
else
{
dfs(nI, nNum - 1);
}
}
sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = false;
}
}
}
}
}
}
bool Find(int nI)
{
bFind = false;
for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
{
for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
{
if (nI == nAnsLen - nI && i == j)
{
continue;
}
sets[nI].bUsed[i] = true;
sets[nAnsLen - nI].bUsed[j] = true;
strcpy(szAns, sets[nI].szLines[i]);
strcat(szAns, sets[nAnsLen - nI].szLines[j]);
if (nI == nAnsLen - nI)
{
dfs(nI, sets[nI].nNum - 2);
}
else
{
dfs(nI, sets[nI].nNum - 1);
}
if (bFind)
{
for (int k = nI + 1; k <= nAnsLen / 2; ++k)
{
bFind = false;
dfs(k, sets[k].nNum);
if (!bFind)
{
break;
}
}
if (bFind)
{
return true;
}
}
strcpy(szAns, sets[nAnsLen - nI].szLines[j]);
strcat(szAns, sets[nI].szLines[i]);
if (nI == nAnsLen - nI)
{
dfs(nI, sets[nI].nNum - 2);
}
else
{
dfs(nI, sets[nI].nNum - 1);
}
if (bFind)
{
for (int k = nI + 1; k <= nAnsLen / 2; ++k)
{
bFind = false;
dfs(k, sets[k].nNum);
if (!bFind)
{
break;
}
}
if (bFind)
{
return true;
}
}
sets[nI].bUsed[i] = false;
sets[nAnsLen - nI].bUsed[j] = false;
}
}
return false;
}
void Search()
{
for (int i = 0; i <= nAnsLen; ++i)
{
if (sets[i].nNum)
{
Find(i);
break;
}
}
}
int main()
{
int nCases;
#ifdef CSU_YX
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
scanf("%d\n", &nCases);
int nNum = 0;
int nTotalLen = 0;
while (gets(szLines[nNum]), nCases)
{
if (szLines[nNum][0] == '\0' && nNum != 0)
{
nAnsLen = nTotalLen * 2 / nNum;
memset(szAns, 0, sizeof(szAns));
Search();
printf("%s\n\n", szAns);
memset(sets, 0, sizeof(sets));
memset(szLines, 0, sizeof(szLines));
nNum = 0;
nTotalLen = 0;
--nCases;
}
else if (szLines[nNum][0] != '\0')
{
int nLen = strlen(szLines[nNum]);
nTotalLen += nLen;
strcpy(sets[nLen].szLines[sets[nLen].nNum], szLines[nNum]);
++sets[nLen].nNum;
++nNum;
}
}
return 0;
}