当前位置:编程学习 > C/C++ >>

HDU4317 Unfair Nim

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) 
         &

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,