1

这是编程竞赛中的问题，我“发现”了如何在 2 人游戏中通过状态。

问题是：在两个玩家 A 和 B 之间进行另一种游戏，其中 A 总是先开始，从给定的矩阵中选择一些字母并从给定的字典中造词。然后丢弃这些字母。下一位玩家从剩下的字母中选择。最后一个说不出话的人就输了。每场比赛都发挥得淋漓尽致。

从 我在这里引用的社论

    To iterate over all non-empty subsets of the given 
    set when they represented using bitmasks:

    submask = mask
    while submask > 0
        // do the job with the submask
        submask = (submask - 1) AND mask

在我看到的一个解决方案中

    int solve(int state)
    {
        if(dp[state]!=-1)
            return(dp[state]);

        int res=1;
        int nstate=state;
        while(1)
        {
            if(valid[nstate])
                res=solve(state&(~nstate));
            if(res==0)
                break;
            nstate=((nstate-1)&state);
            if(nstate==0)
                break;
        }
        if(res==0)
            dp[state]=1;
        else
            dp[state]=0;
        return(dp[state]);
    }

此代码有另一个与 ~ 的 AND。

我实际上无法理解这里的“状态”是什么，以及它如何将我们带入所有状态？请解释一下。

4

1 回答 1

2

状态说明

状态是剩余字母的集合。

我们用 1 替换我们仍然拥有的字母，用 0 替换已经消失的字母。

这会产生一个二进制数，它是变量掩码中保存的数字。

例如，假设我们在游戏开始时有字母 ABCDEFGH，而在某个时刻我们只剩下字母 B 和 D。

数字 0x50 将代表当前状态：

ABCDEFGH  at start
-B-D----  at current point in game
01010000  replace with 1's for letters we still have
0x50      treat as a binary number

小玩意儿

两种解决方案都使用位 twiddle nstate=((nstate-1)&state)。

如果以 nstate=state 开头，此代码将生成状态的所有子集。

这是什么意思？好吧，假设我们有当前字母 B 和 D 的状态。此状态的所有可能的非空子集是 {B,D},{B},{D}。

这些将由二进制数 01010000,01000000,00010000 表示。

我们可以看到这些确实是通过执行以下 Python 代码生成的：

state=0b01010000
nstate=state
while nstate:
    print bin(nstate)
    nstate=(nstate-1)&state

给出输出：

0b01010000
0b01000000
0b00010000

为什么这行得通？

粗略地说，代码用于nstate = nstate-1对所有可能的二进制数进行倒计时，并& state跳过我们不关心的位发生变化的部分（通过立即将它们设置为零，而不是等待它们计数降至零）。

于 2013-02-25T21:35:02.670 回答