【背景（神犇不要鄙視）】
本沙茶在搜索題目的調(diào)試上已經(jīng)掛過兩次了（NOI2011的game用了2h+木有調(diào)出來，還耽誤了繼續(xù)想show的時間，結(jié)果被擋在了集訓(xùn)隊門外；NOIP2011的mayan，用暴搜都調(diào)了2h+，木有調(diào)出來，結(jié)果慘掛，全國第200名，如果這題AC了就是全國前50名……），為了防止在接下來的比賽中再在這里掛掉，本沙茶決定好好搞一下這個。
【DFS的調(diào)試技巧】
如果決定一道題用DFS捉，那么：
（1）如果能套經(jīng)典模型（當(dāng)然本沙茶目前只會一個經(jīng)典模型：DLX），就寫經(jīng)典模型（DLX應(yīng)該不會寫疵的，即使疵了，也很容易調(diào)試的囧）
（2）如果不能，上來先寫暴搜，并命名為0號版本；
（3）i號版本調(diào)試正確之后，再去加剪枝，每次只加一個剪枝（如果時間來不及了，就按照由強到弱或者由好寫到難寫的順序來），調(diào)對了再加下一個，每加一個都開一個新的版本；
（4）調(diào)試時，如果出現(xiàn)的是RE或者死循環(huán)，就在出錯的狀態(tài)處停止，并檢查其所有的祖先狀態(tài)（顯然這需要記下每次的決策），看看這些決策是否合法；
（5）如果程序正常結(jié)束，但結(jié)果錯誤，又分為以下3種情況：
<1>明明有解，輸出無解：可以把正解的各個決策一步一步代入，看看程序里面是在哪一步出了問題（明明合法的決策它木有作出），從而方便檢查；
<2>輸出不合法的解：可以把形成這個不合法解的決策一步一步代入，看看是哪一步出了問題；
<3>輸出合法但非最優(yōu)的解：必然是某些最優(yōu)性剪枝錯誤或者最優(yōu)性判斷出了問題，可以直接到這些地方去檢查，實在不行也可以把最優(yōu)解代入檢查；
（6）當(dāng)然，在動態(tài)查錯之前，要認真地讀一遍代碼；
（7）有時也可以用分段檢查的方法，即把代碼中的各個過程或者片段截取下來，將幾組小的輸入代入，看看執(zhí)行之后，所有在該片段里改變了值的全局變量是否正確，進而發(fā)現(xiàn)這里的錯誤；
（8）千萬不要一下子輸出全部的狀態(tài)！本沙茶在比賽中用的就是這種辦法，結(jié)果不僅木有查出來，還把自己繞暈掉了，最后時間到了連刪printf的時間都木有……事實上，只有在狀態(tài)總數(shù)不太多，且相對關(guān)系明了、順序整齊的時候（比如一般的DP等），可以一下子輸出全部狀態(tài)來檢查，否則就不能這么搞；【BFS的調(diào)試技巧】
BFS其實是比DFS要好調(diào)得多，因為所有的狀態(tài)都儲存在隊列里，因此，可以在狀態(tài)結(jié)點中記下每個點的FA（前趨狀態(tài)），然后，哪里出了問題，就把前趨狀態(tài)全部搞出來即可，另外，BFS一般木有“剪枝”這一說（除了判重），且決策過程一般是比較整齊的，因此好調(diào)；
【例題】
（1）NOIP2011 mayan（無比痛苦的回憶啊啊……）
不用信WJMZBMR的題解（什么“最小表示法”……），這題其實不用加過多剪枝，只需要加以下2個剪枝即可：
<1>如果某種顏色只剩下1或2個，剪枝；
<2>（這個其實不是剪枝）在決策的時候，對于兩個相鄰的方塊，把左邊的往右移與把右邊的往左移是等價的，又因為往右移優(yōu)先，所以在枚舉決策的時候，除非某方塊左邊是空格，否則不要把它往左移；
本題主要是在移動后的消去處理過程（sol0）中比較容易出問題，因此對于這里重點查一下即可，此外，字典序是按照先列后行再移動方向的順序進行的，不要搞疵；
代碼（RQNOJ實測結(jié)果：最慢的點1.2s左右）：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int n = 7, m = 5, MAXC = 11, MAXP = 5, INF = ~0U >> 2;
int P, A[n][m], s[MAXP][3], res[MAXP][3], T[n], sum[MAXC];
bool B[n][m], res_ex = 0;
void init()
{
freopen("mayan.in", "r", stdin);
scanf("%d", &P); int x, len;
re(i, m) {len = 0; while (1) {scanf("%d", &x); if (x) A[len++][i] = x; else break;}}
fclose(stdin);
}
bool sol0()
{
re(i, n) re(j, m) B[i][j] = 0;
int x, len;
re(i, n) re2(j, 2, m) if (A[i][j] && A[i][j] == A[i][j - 1] && A[i][j] == A[i][j - 2]) {
B[i][j] = B[i][j - 1] = B[i][j - 2] = 1; x = j - 3;
while (x >= 0 && A[i][j] == A[i][x]) x--;
re2(k, x+1, j-2) B[i][k] = 1;
}
re(j, m) re2(i, 2, n) if (A[i][j] && A[i][j] == A[i - 1][j] && A[i][j] == A[i - 2][j]) {
B[i][j] = B[i - 1][j] = B[i - 2][j] = 1; x = i - 3;
while (x >= 0 && A[i][j] == A[x][j]) x--;
re2(k, x+1, i-2) B[k][j] = 1;
}
bool FF = 0; re(i, n) re(j, m) if (B[i][j]) {FF = 1; A[i][j] = 0;}
if (FF) {
re(j, m) {
len = 0; re(i, n) if (A[i][j]) {T[len++] = A[i][j]; A[i][j] = 0;}
re(i, len) A[i][j] = T[i];
}
}
return FF;
}
void solve(int v)
{
if (v == P) {
re(i, m) if (A[0][i]) return;
res_ex = 1; re(i, P) re(j, 3) res[i][j] = s[i][j];
} else {
re(i, MAXC) sum[i] = 0;
re(i, n) re(j, m) sum[A[i][j]]++;
re2(i, 1, MAXC) if (sum[i] == 1 || sum[i] == 2) return;
int tmp, len, A0[n][m];
re(i, n) re(j, m) A0[i][j] = A[i][j];
re(j, m) re(i, n) if (A[i][j]) {
if (j < m - 1) {
tmp = A[i][j]; A[i][j] = A[i][j + 1]; A[i][j + 1] = tmp;
re(j0, m) {
len = 0; re(i0, n) if (A[i0][j0]) {T[len++] = A[i0][j0]; A[i0][j0] = 0;}
re(i0, len) A[i0][j0] = T[i0];
}
while (sol0()) ;
s[v][0] = j; s[v][1] = i; s[v][2] = 1;
solve(v + 1); if (res_ex) return;
re(i0, n) re(j0, m) A[i0][j0] = A0[i0][j0];
}
if (j && !A[i][j - 1]) {
tmp = A[i][j]; A[i][j] = A[i][j - 1]; A[i][j - 1] = tmp;
re(j0, m) {
len = 0; re(i0, n) if (A[i0][j0]) {T[len++] = A[i0][j0]; A[i0][j0] = 0;}
re(i0, len) A[i0][j0] = T[i0];
}
while (sol0()) ;
s[v][0] = j; s[v][1] = i; s[v][2] = -1;
solve(v + 1); if (res_ex) return;
re(i0, n) re(j0, m) A[i0][j0] = A0[i0][j0];
}
}
}
}
void pri()
{
freopen("mayan.out", "w", stdout);
if (res_ex) re(i, P) printf("%d %d %d\n", res[i][0], res[i][1], res[i][2]); else printf("%d\n", -1);
fclose(stdout);
}
int main()
{
init();
solve(0);
pri();
return 0;
}
（2）
小木棍（整數(shù)分組模型）經(jīng)典的DFS剪枝題。需要很多很強的剪枝：
<1>枚舉最后形成木棍（以下簡稱大木棍）的長度P的時候有限制，這個就不說了；
<2>所有相同長度的木棍都要合并，最終所有木棍按照長度遞減存在數(shù)組里面，在枚舉的時候只需枚舉這個木棍使用的個數(shù)，且從大到小枚舉；
<3>為了減少枚舉量，要用Dancing Link優(yōu)化；
<4>很顯然，枚舉每根大木棍的時候，目前剩下的最長的木棍肯定要至少使用一次，且如果該長度的木棍使用了K次，則以后的所有大木棍都最多只能使用K次（除非該長度的木棍被用完了），這是用字典序保證不重復(fù)枚舉；
<5>要加上一個強剪枝：如果目前加上一個（只能一個）長度為L的木棍以后，恰好拼成一個完整的大木棍，但是之后失敗了，此時就不用再枚舉接下來更短的木棍了，因為如果用它們得到了解，則把它們與一個長度L的木棍交換也是可行解；
<6>只要倒數(shù)第2根大木棍拼成了，就找到了解，因為剩下的肯定能拼成最后一根；
由于這題的剪枝很多，很繁瑣，極易出錯，因此寫的時候要非常小心，查錯也很麻煩囧……
代碼（PKU上0ms，UVA上144ms）：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int n = 50, INF = ~0U >> 2;
int P, P0, A[n + 1], L[n + 1], R[n + 1];
bool res_ex;
void prepare()
{
L[0] = R[0] = 0; re1(i, n) if (A[i]) {L[i] = L[0]; R[i] = 0; L[0] = i; R[L[i]] = i;}
}
void solve(int dep, int len, int K, int x1)
{
if (dep == P0) res_ex = 1; else {
int len0, s0;
if (len == P) {
int maxv = L[0];
s0 = len / maxv <= A[maxv] ? len / maxv : A[maxv]; if (s0 > x1) s0 = x1;
len0 = len - (s0 + 1) * maxv;
rre1(i, s0) {
if ((P0 - dep + 1) * i < A[maxv]) return;
A[maxv] -= i; if (!A[maxv]) {L[R[maxv]] = L[maxv]; R[L[maxv]] = R[maxv];} len0 += maxv;
if (len0) solve(dep, len0, L[maxv], A[maxv] ? i : INF); else {
solve(dep + 1, P, 0, x1);
if (i == 1 && !res_ex) {
if (!A[maxv]) L[R[maxv]] = R[L[maxv]] = maxv;
A[maxv] += i; return;
}
}
if (res_ex) return;
if (!A[maxv]) L[R[maxv]] = R[L[maxv]] = maxv; A[maxv] += i;
}
} else {
int i = K;
while (i) {
if (A[i] && i <= len) {
s0 = len / i <= A[i] ? len / i : A[i];
len0 = len - (s0 + 1) * i;
rre1(j, s0) {
A[i] -= j; if (!A[i]) {L[R[i]] = L[i]; R[L[i]] = R[i];} len0 += i;
if (len0) solve(dep, len0, L[i], x1); else {
solve(dep + 1, P, 0, x1);
if (j == 1 && !res_ex) {
if (!A[i]) L[R[i]] = R[L[i]] = i;
A[i] += j; return;
}
}
if (res_ex) return;
if (!A[i]) L[R[i]] = R[L[i]] = i; A[i] += j;
}
}
i = L[i];
}
}
}
}
int main()
{
int n0, x, sum, maxv;
while (1) {
scanf("%d", &n0); if (!n0) break; else {sum = 0; maxv = 0; re1(i, n) A[i] = 0; res_ex = 0;}
re(i, n0) {scanf("%d", &x); A[x]++; sum += x; if (x > maxv) maxv = x;} prepare();
re3(i, maxv, sum) if (!(sum % i)) {
P = i; P0 = sum / i - 1; solve(0, P, 0, INF);
if (res_ex) {printf("%d\n", i); break;}
}
}
return 0;
}
【附加內(nèi)容】
在mayan的代碼中有一個數(shù)組A0，用于在過程中備份A數(shù)組，使得它在下面搜索失敗之后能及時更新（因為這里的A經(jīng)歷了sol0處理，更新比較麻煩），這種備份數(shù)組在很多題里面都有應(yīng)用，不過要注意，這個數(shù)組一定要寫成局部的，不能寫成全局的！！（本沙茶在比賽的時候就是寫成全局的了，結(jié)果導(dǎo)致出錯查不出來的……）如果怕寫成局部的MLE，也可以寫成全局的，但是要分層，即對于每個搜索深度（v、dep等變量控制），要開專門的一層，保證搜索過程中各層不互相覆蓋。