2012 Multi-University Training Contest 2
1008題
解題報告說得非常不清楚，完全不知道它想表達什麼。
題目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4317
題意：想辦法使N堆石子的數量異或之後為0。
N非常小，狀態壓縮自然從N入手，用二進制表示這N堆的所有選擇。
根據異或的性質，只要異或的這些數字對應二進制相同的位上有偶數個1，則這位異或的結果就為0。
dp[i][j]：i代表由低到高的第幾位，j是壓縮過後的狀態，如果某一位為1則表示在i-1位的相同位置加1產生了進位。dp[i][j]代表達到這樣的狀態所需的最小石子數。
在這樣的定義下，如果i能達到的最高位的進位j有偶數個1，則說明這是答案的一種選擇，只要選取這些取值中最小的就可以了。
下面考慮狀態之間的關系。
i狀態只可能由i-1的狀態得來。我們用c[i]記錄每一位石子數量的初始狀態，如果第k個石子的第i位為1，則c[i]的第k位就為1。
我們用num[x]表示x中1的個數，isEven[x]表示x中1的個數是否為偶數個。
對於一個j，由i-1狀態下的k得來，k要想到達j，需要滿足以下條件：
1. 保證k可以到達j
如果c[i]和k的某一位都為1，則在這一位一定產生了進位，j在這一位也必須為1，所以有一個約束條件：((j | (c[i] & k)) == j)
2. 保證i-1位的1的數量為偶數
由於j是狀態c[i]與k二進制加法得到的結果再進位，c[i] ^ k所得的數對應位，
如果為0，說明需要加上2來產生進位，結果還是0。
如果為1，說明需要加上1來產生進位，結果變為0。
所以：
如果j對應位為0：什麼也不用做。
如果j對應位為1，c[i] ^ k對應位為0：需要加2。
如果j對應位為1，c[i] ^ k對應位為1：需要加1變0,。
最終，只要本來就是偶數，或還有0位可以讓我們填上1個石子，我們就一定可以獲得偶數的情況，
因為j有1的位產生進位後一定為0，所以：
本來就是偶數：isEven[(~j) & (c[i] ^ k)]，除去j有1的位的1後剩下的1的數量為偶數
還有空閒的0位：j || num[(c[i] ^ k) | j] < n，因為只要有j就有0的存在，或除去有j有1位的地方有0存在
總的判定為：(isEven[(~j) & (c[i] ^ k)] || j || num[(c[i] ^ k) | j] < n)
3. 由狀態k到達狀態j
根據上面所說，我們找到了滿足條件的k，接下來要考慮需要石子的數量。
首先是已經有進位的位，c[i]和k對應位都為1，(c[i] & k)這樣的位無需考慮。
然後考慮是否要補一個石子來滿足偶數條件，有就加1。
接下來是c[i] ^ k對應位為1的情況，也就是(j & (c[i] ^ k))中1的數量，需要在這一位加上同等數量的石子。
最後是c[i] ^ k對應位為0的情況，也就是(j ^ (j & (c[i] ^ k)))中1的數量去掉(c[i] & k)中1的數量，需要在這一位上加上二倍數量的石子。
由於是第i-1位，需要的石子的數量要乘上1<<(i-1)。
綜上所述：
dp[i][j] = min(dp[i][j], dp[i-1][k] + (!isEven[(~j) & (c[i] ^ k)] + num[j & (c[i] ^ k)] + ((num[j ^ (j & (c[i] ^ k))] - num[c[i] & k]) << 1)) * (1 << (i-1)));
邊界條件：
dp[0][0] = 0，其它值為INF。
對於多堆情況，一定能找到一種方法使游戲成立，只有一堆的時候才會出現必輸的情況。
當n==1且數量不為0時，這是不可能滿足條件。
題目給的時限是10s，跑了1.5s，速度上不是太快。
[cpp]
#include <cstdio>
#include <cstring>
const int MAXN = 15;
const int MAXM = 25;
const int INF = 1000000000;
int n, m, a[MAXN];
int c[MAXM], dp[MAXM][1<<MAXN];
int num[1<<MAXN];
bool isEven[1<<MAXN];
inline int min(int x, int y)
{
return x < y ? x : y;
}
inline int getOneNumber(int x)
{
int result = 0;
while(x)
{
result += x & 1;
x >>= 1;
}
return result;
}
void init()
{
for(int i=0;i<(1<<MAXN);++i)
{
num[i] = getOneNumber(i);
isEven[i] = ((num[i] & 1) == 0);
}
}
int main()
{
init();
while(~scanf("%d", &n))
{
for(int i=0;i<n;++i)
{
scanf("%d", &a[i]);
}
if(n == 1)
{
if(a[0])
{
printf("impossible\n");
}
else
{
printf("0\n");
}
}
else
{
memset(c, 0, sizeof(c));
for(int i=1;i<MAXM;++i)
{
for(int j=0;j<n;++j)
{
if(a[j] & (1 << (i - 1)))
{
c[i] |= (1 << j);
}
if(c[i])
{
m = i + 1;
}
}
}
for(int i=0;i<=m;++i)
{
for(int j=0;j<(1<<n);++j)
{
dp[i][j] = INF;
}
}
dp[0][0] = 0;
for(int i=1;i<=m;++i)
{
for(int j=0;j<(1<<n);++j)
{
for(int k=0;k<(1<<n);++k)
{
if(dp[i-1][k] != INF)
{
if((j | (c[i] & k)) == j)
{
if(isEven[(~j) & (c[i] ^ k)] || j || num[(c[i] ^ k) | j] < n)
{
dp[i][j] = min(dp[i][j], dp[i-1][k] + (!isEven[(~j) & (c[i] ^ k)] + num[j & (c[i] ^ k)] + ((num[j ^ (j & (c[i] ^ k))] - num[c[i] & k]) << 1)) * (1 << (i-1)));
}
}
}
}
}
}
int ans = INF;
for(int i=0;i<(1<<n);++i)
{
if(isEven[i])
{
ans = min(ans, dp[m][i]);
}
}
printf("%d\n", ans);
}
}
return 0;
}
作者：CyberZHG
