[POJ 2975] & [POJ 2960]

博弈

题意：Nim问题的必胜策略为，取当前各堆石子数的异或和，若为0则为必败局面；否则取走部分石子使得异或和变为0，便可使对方陷入必败局面。问题为，给出一个局面，问有多少种不同的必胜策略。

分析：很简单，既然必胜策略已知，那么可以算出需要改变那些位才能转化为必败局面。由于，每次只允许改变一堆石子的数目，目标石子数小于等于当前石子数时对应一种必胜策略。最后算一算有多少个堆满足该条件即可。

#include<cstdio>

int n,a[1000],ans;

void solve()
{
    int i,j;
    ans=0;
    for(i=j=0;i<n;i++)
    {
        scanf("%d",a+i);
        j^=a[i];
    }
    if(!j)
    {
        puts("0");
        return;
    }
    for(i=0;i<n;i++)
    {
        if((a[i]^j)<=a[i])
            ans++;
    }
    printf("%d\n",ans);
}

int main()
{
    while(~scanf("%d",&n)&&n)
        solve();
    return 0;
}

#include<cstdio>

int n,a[1000],ans;

void solve()

{

int i,j;

ans=0;

for(i=j=0;i<n;i++)

{

scanf("%d",a+i);

j^=a[i];

}

if(!j)

{

puts("0");

return;

}

for(i=0;i<n;i++)

{

if((a[i]^j)<=a[i])

ans++;

}

printf("%d\n",ans);

}

int main()

{

while(~scanf("%d",&n)&&n)

solve();

return 0;

}

稍微增加难度的话，就是下面这题：

S-Nim

博弈

题意：对于基本的Nim问题，增加如下限制：每次取走的石子数必须在集合S中，若剩余石子不足则可以全部取走。问题是，对于某局面，是否存在必胜策略。

分析：对于给定的S集，考虑将剩余石子的数目划分类别。具体来说，将剩余为0或无法一步到达第0类的石子数设为第0类，可以一步到达第0类（但无法到达第1类）的设为第1类，并依次类推：可以一步到达第0…i-1类且无法到达第i类的设为第i类。这样分类之后，便可以将第i类堆与原Nim问题中的堆石子数为i对应起来。其依据在于，第i类总是能一步到达更低的类别，但无法保持当前状态（或者到达更高类别时会在下一步（由对手操作）回到该类）。由此，便可以对当前各堆的类别数取异或和，并按照结果是否为0来判定是否为必败局面。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,a[100],b[10001],c[10001];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%d",a+i);
    sort(a,a+n);
    b[0]=0;
    for(i=1;i<10001;i++)
    {
        memset(c,0,sizeof c);
        for(l=0;l<n&&i>=a[l];l++)
            c[b[i-a[l]]]++;
        for(l=0;c[l];l++);
        b[i]=l;
    }
}

void solve()
{
    int i,j,k,l;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&l);
        j=0;
        while(l--)
        {
            scanf("%d",&i);
            j^=b[i];
        }
        printf("%c",j?'W':'L');
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,a[100],b[10001],c[10001];

void init()

{

int i,j,k,l;

for(i=0;i<n;i++)

scanf("%d",a+i);

sort(a,a+n);

b[0]=0;

for(i=1;i<10001;i++)

{

memset(c,0,sizeof c);

for(l=0;l<n&&i>=a[l];l++)

c[b[i-a[l]]]++;

for(l=0;c[l];l++);

b[i]=l;

}

void solve()

{

int i,j,k,l;

scanf("%d",&m);

while(m--)

{

scanf("%d",&l);

j=0;

while(l--)

{

scanf("%d",&i);

j^=b[i];

}

printf("%c",j?'W':'L');

}

puts("");

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}