这个题，粗看之下还没怎么看懂，这个应该跟我英语水平有关系。然后再看输入输出，渐渐的才明白什么意思。原来是要把2*N张破纸组合
成N张一样的纸。我历来思维比较随便，不是很严谨的那种。然后，想了一下发现一定会有大于等于N张破纸片是符合前半部分模式的。
那么，可以建一个字典树，把所有的是前半张纸的找出来。然后根据这前半张纸，找出剩下的后半张纸（因为知道一整张纸的长度，所以知道
剩下的半张纸的长度）。但是写出来就发现这样不严谨，是不对的。因为单纯根据已经找出来的前半张纸，无法确定后半张纸（事实上，只能
确定其长度而已）。
那么只能找其它方法了，再检查了下数据范围，发现比较小，那么意味着可以暴力求解了。好吧，那就深搜吧。我把所有的破纸片按照它们
的长度分成一些集合，对于长度为len的纸片集合，只要与长度为nAnsLen - len的纸片集合进行搜索匹配，找出一个可行的解即可了。我又
想当然的认为只要匹配一对集合即可了，那么很显然又是错的了。好吧，我只能对所有集合进行匹配了。对每一对集合进行深搜回溯来匹配待
选的Ans，而这个Ans是从第一对集合中搜索出来的答案。
代码写得很冗长，很复杂，差不多200多行了。真的是水平有限，这种题很明显应该有更方便的解法的，而且我的代码应该不至于写得这么
乱的。
后面还是错了很多次，发现了很多bug，比如我如果搜索长度为nAnsLen/2的集合时就必须进行特殊处理。还有最后一个样例后面不能输
出’\n'，而且uvaoj不能对这个换行判PE，一直是WA，实在是让人崩溃。
#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;
}