Uva 10132 - File Fragmentation

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#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;
}