首页 > 代码库 > ACdream群赛1112（Alice and Bob）

ACdream群赛1112（Alice and Bob）

2024-07-07 17:10:24   225人阅读

题意：http://acdream.info/problem?pid=1112

Problem Description

Here  is Alice and Bob again !

Alice and Bob are playing a game. There are several numbers.First, Alice choose a number n.Then he can replace n (n > 1)with one of its positive factor but not itself or he can replace n with a and b.Here a*b = n and a > 1 and b > 1.For example, Alice can replace 6 with 2 or 3 or (2, 3).But he can’t replace 6 with 6 or (1, 6). But you can replace 6 with 1. After Alice’s turn, it’s Bob’s turn.Alice and Bob take turns to do so.Who can’t do any replace lose the game.

Alice and Bob are both clever enough. Who is the winner?

解法：很好的博弈题。关键是找准每个数的状态。每个数的状态是每个数的分解后的质数的个数。然后就是获得每个数的状态号可以做到On，就是线性筛素数时候顺便将每个数的最小的质数因子筛出来，从小大大先预处理，然后求F(n)就等于F(n/least[n])+1。获得状态号，sg部分就不多说了。


代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=5000010;
const int INF=1000000007;

int f[300];
bool rem[Max];
int out[Max];
int least[Max];
int p=0;
void init()
{
    for(int i=2; i<Max; i++)
        if(!rem[i])
        {
            for(int j=i*2; j<Max; j+=i)
            {
                if(least[j]==-1)
                    least[j]=i;
                rem[j]=1;
            }
            least[i]=i;
        }
}
int getans(int t)
{
    if(f[t]!=-1)
        return f[t];
    int Rem[1000];
    memset(Rem,0,sizeof Rem);
    Rem[0]=1;
    for(int i=1; i<=t/2; i++)
    {
        Rem[getans(i)]=1;
        Rem[getans(t-i)]=1;
        Rem[getans(t-i)^getans(i)]=1;
    }
    int to=0;
    while(Rem[to])to++;
    return f[t]=to;
}
int F(int n)
{
    if(out[n]!=-1)
        return out[n];
    int ans=F(n/least[n])+1;
    return out[n]=ans;
}
int main()
{
    int n;
    memset(f,-1,sizeof f);
    memset(out,-1,sizeof out);
    memset(least,-1,sizeof least);
    f[1]=1;
    init();
    out[1]=0;
    for(int i=0; i<20; i++)
        F(1<<i);// cout<<i<<" "<<getans(i)<<endl;
    while(scanf("%d",&n)==1)
    {
        int ans=0;
        for(int i=0; i<n; i++)
        {
            int t;
            scanf("%d",&t);
            ans^=getans(F(t));
        }
        if(ans)
            puts("Alice");
        else
            puts("Bob");
    }
    return 0;
}



联系
我们