15011418730 LV 7 @ 2025-8-24 21:47:52

自动搬运

来自洛谷，原作者为

	jiangby **

搬运于2025-08-24 21:47:52，当前版本为作者最后更新于2020-05-21 21:47:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我搞了好久，找半天找不到题解，最后只有靠着贴吧里的那一个糊到不行的图，一点一点看清是哪个字来做，我把做法大意和代码放在下面，供各位参考，如果有大佬知道为什么请私信告诉我。

首先暴力SG
$SG[x]=mex\{SG[x-i]\ xor\ SG[x-2i]\ xor...xor\ SG[x-ki]|x>=ki\}$ 然后通过不知道怎么样的做法发现以下结论

SG[x]=A_k[i]

其中 $i$ 是将 $x$ 变为 $k+1$ 进制后从低往高遇到的一个 $k$ 的位数，若没有则 $i=0$

然后 $A_k$ 满足

$$A_k[0]=0,A_k[x]=mex\{A_k[x_1]\ xor\ A_k[x_2]...\ xor\ A_k[x_k]|x_1,x_2...x_k<x\} $$

所以当我们求出 $A_k$ 时原问题就解决了，接下来是如何求出 $A_k$ 一直当 $x<=k+1$ 时 $A_k[x]=(2^{x-1})$ ,当 $x=k+2$ 时 $A_k[x]=2^{k+1}-1$ 因为前面的不能全选，所以不同，后面 $A_k[x]$ 继续是 $2^i$ 的形式，但是没隔 $k/2$ 个因为不能全部凑出所以会隔断一次，然后后面又继续(这里说的不是很清楚可以看代码)。下面是代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<ll,ll>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(ll x=y;x<=z;++x)
#define Red(x,y,z) for(ll x=y;x>=z;--x)
using namespace std;
char buf[1<<12],*p1=buf,*p2=buf,nc;ll ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline ll read(){
	ll x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}struct BigInteger {
    typedef unsigned long long LL;
 
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
 
    BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
    BigInteger(LL num = 0) {*this = num;}
    BigInteger(string s) {*this = s;}
    BigInteger& operator = (long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }
    BigInteger& operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return (*this).clean();
    }
 
    BigInteger operator + (const BigInteger& b) const {
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }
    BigInteger operator - (const BigInteger& b) const {
        assert(b <= *this); 
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = s[i] + g;
            if (i < b.s.size()) x -= b.s[i];
            if (x < 0) {g = -1; x += BASE;} else g = 0;
            c.s.push_back(x);
        }
        return c.clean();
    }
    BigInteger operator * (const BigInteger& b) const {
        int i, j; LL g;
        vector<LL> v(s.size()+b.s.size(), 0);
        BigInteger c; c.s.clear();
        for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
        for (i = 0, g = 0; ; i++) {
            if (g ==0 && i >= v.size()) break;
            LL x = v[i] + g;
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c.clean();
    }
    BigInteger operator / (const BigInteger& b) const {
        assert(b > 0);  
        BigInteger c = *this;       
        BigInteger m;               
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return c.clean();
    }
    BigInteger operator % (const BigInteger& b) const { 
        BigInteger c = *this;
        BigInteger m;
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return m;
    }
    int bsearch(const BigInteger& b, const BigInteger& m) const{
        int L = 0, R = BASE-1, x;
        while (1) {
            x = (L+R)>>1;
            if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
            else R = x;
        }
    }
    BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
    BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
    BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
    BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
    BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}
 
    bool operator < (const BigInteger& b) const {
        if (s.size() != b.s.size()) return s.size() < b.s.size();
        for (int i = s.size()-1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
    bool operator >(const BigInteger& b) const{return b < *this;}
    bool operator<=(const BigInteger& b) const{return !(b < *this);}
    bool operator>=(const BigInteger& b) const{return !(*this < b);}
    bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
    bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};
ostream& operator << (ostream& out, const BigInteger& x) {
    out << x.s.back();
    for (int i = x.s.size()-2; i >= 0; i--) {
        char buf[20];
        sprintf(buf, "%08d", x.s[i]);
        for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
}
istream& operator >> (istream& in, BigInteger& x) {
    string s;
    if (!(in >> s)) return in;
    x = s;
    return in;
}
ll A2[70],A10[25],vis[1050],A30[60];
inline void pre(){
	ll t=0;
	Rep(i,1,1024){
		vis[i]=(vis[i>>1]^(i&1));
		if(vis[i])A2[++t]=i;
	}Rep(i,0,10)A10[i]=1<<i;Rep(i,12,16)A10[i]=1<<i-1;Rep(i,18,19)A10[i]=1<<i-2;
	A10[11]=(1<<11)-1,A10[17]=(1<<16)-(1<<11)+(1<<6)-1;
	Red(i,20,1)A10[i]=A10[i-1];A10[0]=0;
	Rep(i,0,30)A30[i]=1<<i;Rep(i,32,46)A30[i]=1ll<<i-1;Rep(i,48,54)A30[i]=1ll<<i-2;
	A30[31]=(1ll<<31)-1,A30[47]=(1ll<<46)-(1ll<<31)+(1<<16)-1;
	Red(i,55,1)A30[i]=A30[i-1];A30[0]=0;
}ll n,k;
inline ll Get(){
	ll x=read();
	for(ll cnt=1;x;x/=k+1,cnt++)if(x%(k+1)==k)return cnt;
	return 0;
}inline ll GetB(){
	BigInteger x;cin>>x;
	for(ll cnt=1;x!=0;x/=k+1,cnt++)if(x%(k+1)==k)return cnt;
	return 0;
}
inline void Solve1(){
	ll tot=0;
	Rep(i,1,n)tot^=read();
	if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve2(){
	ll tot=0;
	Rep(i,1,n)tot^=A2[Get()];
	if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve10(){
	ll tot=0;
	Rep(i,1,n)tot^=A10[Get()];
	if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve30(){
	ll tot=0;
	Rep(i,1,n)tot^=A30[GetB()];
	if(tot)puts("Preempt.");else puts("Leapfrog.");
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	pre();
	for(ll t=read();t--;){
		n=read(),k=read();
		if(k==1)Solve1();
		else if(k==2)Solve2();
		else if(k==10)Solve10();
		else if(k==30)Solve30();
	}
	return 0;
}

ID

2412

时间

1000ms

内存

128MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[ZJOI2014] 取石子游戏

信息

1 条题解

自动搬运

以下是正文

[ZJOI2014] 取石子游戏

信息

还没有账户？

登录