作為一個算法的不入門興趣者，玩着參加了下Google Code Jam，如預料的在第二輪被淘汰，不過事後分析其實也不是沒有希望了，隻需要20分就可以晉級哦。
下面發發我事後研究的題解報告。
本來好久沒來，也不想發這裡，可是另外一個blog說字數超過限制，是以嘛……
閑話少說，下面發題解了，大家輕拍。代碼參考了下ACRUSH的，高手就是寫得比我好看得多。
A. Cheating a Boolean Tree
題意描述
在這個題目中，我們将考慮一種叫做布爾樹(boolean tree)的二叉樹。在這種樹種，每一層都是完整的，除了最下面一層，在最下層中，所有結點都盡可能地靠近左邊。此外，樹中每個節點都擁有0個或2個子結點。
布爾樹特殊之處在于每個節點都擁有一個值，1或0。此外，每個内部結點(非葉子結點)都有一個“與門”或“或門”。内部結點的取值是通過其兩個子結點進行對應的“與”或“或”運算的值。所有葉結點的值是通過輸入獲得，是以所有結點的值都可以通過計算獲得。
樹的根結點是我們特别關注的。我們希望根結點的取值是指定的值V，1或者0。不幸的是，往往根結點實際的值并不是我們所希望的。然而幸運的是，我們可以通過改變某些結點的門來得到希望的取值。
給定一棵布爾樹和樹中可以改變門的結點，找出需要改變最少多少個門才可以得到想要的取值，如果不能得到值，則輸出”IMPOSSIBLE”。
輸入
輸入的第一行包含測試資料的組數，N。後面跟着N組測試資料。
每組資料第一行有兩個數M和V。M訓示這棵樹有多少結點，它能夠保證每個結點都有0個或2個子結點。V表示希望的根結點取值，0或1。
接下來M行描述樹中的節點，第X行描述第X個結點。
前(M-1)/2行描述内部結點。每行有兩個數G和C，每個取值都是0或1。G表示結點的門，1代表與門，0表示或門。C表示這個結點的門是否可以改變，0表示不能改變，1表示可以變動。
接下來(M+1)/2行描述葉子結點。每行包含一個數I，0或1，葉結點的值。
下圖中是個執行個體：
輸出
每組測試資料輸出下面的格式：
Case #X: Y
X指第幾組，Y表示最少要變動幾個門，如果不能得到需要的值，則Y為IMPOSSIBLE。
限制
1<N<=20
小測試資料：
最多30個結點
大測試資料：
最多10000個結點。
示例
Input
2
9 1
1 0
1 1
1 1
0 0
1
1
1
5 0
1 1
0 0
1
1
Output
Case #1: 1
Case #2: IMPOSSIBLE
解題思路
總的說來，這道題的本質是考遞歸的應用，同時需要考慮對于中間狀态的儲存。
#include <cstdio>
#include <iostream>
using namespace std;
//比較a和b，如果b比a小，則将b的值賦給a
//注意a是引用的
template<class T> inline void checkmin(T &a, T b)
{
if(b<a) a=b;
}
//訓示不可能
const int impossible = 100000;
//數組的最大數目
const int maxsize = 40000;
int n; //結點數目
int f[maxsize][2]; //用于儲存第x個結點要取某值需要改變多少次的中間結果
//數組第一個是結點的序号，第二個則是表示取值是或
int G[maxsize], C[maxsize], X[maxsize];
//分别儲存各結點的門，可否改變，取值
//計算結點的值
//x,y是兩子結點的值，op是門的種類
int calc(int x, int y, int op)
{
if(op == 1)
return x & y;
else
return x | y;
}
//遞歸計算要改變的數目
//id是第幾結點，exp是值希望該結點是何值
int Solve(int id, int exp)
{
//子結點時
if(id > (n-1)/2)
//如果結點的值等于希望值則傳回，否則傳回
return (exp == X[id]) ? 0:impossible;
int &ret = f[id][exp];
if(ret != -1) //如果取值不為-1，則傳回數組中的值
return ret;
ret = impossible;
//周遊子結點的所有可能
for(int left = 0; left < 2; left++)
{
for(int right = 0; right < 2; right++)
{
//如果計算等于希望的值，則分别計算兩個子結點需要改變的次數
//并與ret比較，将小的指派給ret
if(calc(left, right, G[id]) == exp)
checkmin(ret, Solve(id*2,left)+Solve(id*2+1,right));
//如果該結點可以改變則計算改變門後的情況，與上類似
if(C[id] == 1 && calc(left,right, 1-G[id])==exp)
{
checkmin(ret, Solve(id*2,left) + Solve(id*2+1,right)+1);
}
}
}
return ret;
}
int main()
{
FILE *in;
FILE *out;
in = fopen("A-samll-attempt0.in", "r");
out = fopen("A-large-result.out", "wt");
int testcase; //測試資料組數
scanf("%d", &testcase);
int exp;
for(int caseId = 1; caseId <= testcase; caseId++)
{
fprintf(out, "Case #%d: ", caseId);
scanf("%d%d", &n, &exp);
for(int i = 1; i <= (n-1)/2; i++)
{
scanf("%d%d", &G[i], &C[i]);
}
for(int i = (n-1)/2+1; i <= n; i++)
{
scanf("%d", &X[i]);
}
memset(f, -1, sizeof(f));
//運算
int ret = Solve(1,exp);
//輸出
if(ret == impossible)
fprintf(out, "IMPOSSIBLE/n");
else
fprintf(out, "%d/n", ret);
}
return 0;
}
![處理PCX檔案[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)