AThegameofOsho（20162017ACMICPC,EgyptianCollegiateProgrammingContest(ECPC16)）题解xiaodangao

题目链接：A - The game of Osho
思路：SG打表找规律，发现在b为奇数时，0、1均匀分布，b为偶数时且满足n%(b+1) = b时sg值为2，打表程序如下:
$Code1:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e5+10;
ll b,_;int n;
int f[N];


int sg(int id){
    if(f[id] != -1)return f[id];
    set<int>S;
    ll p = 1;
    while(p<=id){
        S.insert(sg(id-p));
        p=b*p;
    }
    int now = 0;
    while(S.count(now))now++;
    f[id] = now;
    return now;
}
void solve(){
    while(true){
        memset(f,-1,sizeof f);f[0] = 0;f[1] = 1;
        read(b);read(n);
        rep(i,0,n){
            if(sg(i)==2)printf("%d\n",i);
        }
    }
}

signed main(){solve(); return 0; }

AC代码如下：
$Code2:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e5+10;
ll b,_;int n;
int f[N];


int sg(int id){
    if(f[id] != -1)return f[id];
    set<int>S;
    ll p = 1;
    while(p<=id){
        S.insert(sg(id-p));
        p=b*p;
    }
    int now = 0;
    while(S.count(now))now++;
    f[id] = now;
    return now;
}
void solve(){
    freopen("powers.in","r",stdin);
    read(_);
    while(_--){
        int t;
        read(t);
        int ans = 0;
        rep(i,1,t){
            read(b);read(n);
            if(b & 1){
                ans ^= n%2;
            }
            else if(n%(b+1) == b)ans^=2;
            else {
                int x = n%(b+1);
                ans ^= x%2;
            }
        }
        if(!ans)puts("2");else puts("1");
    }
}

signed main(){solve(); return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章