教材资源网站建设,天元建设集团有限公司长清分公司,国外服务器租赁,公司如何申请一个网站网址前几天做过一道题目#xff0c;是Nim游戏的一个扩展#xff0c;也不能说扩展吧#xff0c;只是说另一种常见的状态。
问题引入#xff1a;
给定n堆石子#xff0c;每堆石子有vi#xff08;1vi1e5) 个#xff0c;每次可以取一堆中的一些石子#xff0c;使得剩…前几天做过一道题目是Nim游戏的一个扩展也不能说扩展吧只是说另一种常见的状态。
问题引入
给定n堆石子每堆石子有vi1vi1e5) 个每次可以取一堆中的一些石子使得剩下的石子为1到vi/k个为最后的是先手胜还是后手胜如果先手胜则输出相应的操作策略。
思考
当k2的时候显然就退化成了la 5059 的题目我们以此为基础来考虑肯定要先计算出sg的函数表然后观察规律lrj在训练指南中说的很清楚打表的规则也很简单下面给出lrj所打出的表 0 1 0 2 1 3 0 4 2 5 当然lrj是从奇偶性来分析的那么很容易得出 sgxn%20sgn/2这样的结论因为k2刚好有一些特性被提现出来了。所以
#include bits/stdc.h
using namespace std;typedef long long ll;
ll sg(ll n)
{return n%20 ? n/2 : sg(n/2);
}
int main()
{int T;scanf(%d,T);while(T--){int n;ll x;scanf(%d,n);ll ans0;while(n--){scanf(%lld,x);ans^sg(x);}if(ans)printf(YES\n);elseprintf(NO\n);}return 0;
}
那么当k2的时候又该怎么去解决难道比葫芦画瓢要推出 sgn%k0n/ksgn/k 这样的结论如果真的这样我只能说比葫芦画瓢的能力只用在了记答案上这种能力应该是一种分析该问题的方法正确的解法无非是打sg表寻找规律。
笔者随手推了一下那么打出的表如下
k3 0 1 2 0 3 4 1 5 6 k40 1 2 3 0 4 5 6 1 7 8 9
可以发现都有123456……这个序列而再去翻看上面的n2的情况发现都存在这样的规律但是好像没什么用具体编程还是没办法操作再去细看发现打断123456这个序列的的下标x都是x%k1而且去掉123456这样的数后得到的都是原序列那么也就是说当x%k1时sgxsgx/k 否则这样的123456序列实际上是由x-阶梯层数得到的什么是阶梯层数当k3的时候x123就属于第一层x456 就属于第二层那么容易得出
x%k1 ? sg(x/k) : x-x/k-(x%k!0);
于是上题的第二种解法为
#include bits/stdc.h
using namespace std;typedef long long ll;
ll k2;
ll sg(ll x){if (x1) return 0;return x%k1 ? sg(x/k) : x-x/k-(x%k!0);
}
int main()
{int T;scanf(%d,T);while(T--){int n;ll x;scanf(%d,n);ll ans0;while(n--){scanf(%lld,x);ans^sg(x);}if(ans)printf(YES\n);elseprintf(NO\n);}return 0;
}而对于51nod中要求求必胜操作时只需预处理一下sg值然后枚举每一位根据sg值来逆推符合条件的x即可。
提交地址 http://www.51nod.com/onlineJudge/questionCode.html#!problemId1661
#include bits/stdc.h
using namespace std;typedef long long ll;
const int N1e55;ll n,k,sl[N],sr[N],v[N],vt[N];
ll sg(ll x){if (x1) return 0;return x%k1 ? sg(x/k) : x-x/k-(x%k!0);
}int main()
{sl[0]sr[n1]0;cinnk;ll p0,ans0;for (int i1;in;i){scanf(%lld,vi);vt[i]sg(v[i]);sl[i]sl[i-1]^vt[i];}for (int in;i1;i--) sr[i]sr[i1]^vt[i];for (int i1;in;i){ll ttsl[i-1]^sr[i1],txceil(1.0*v[i]/k);if (v[i]1||vt[i]tt) continue;ll ttl(ll)(1.0*tt*k/(k-1)1);if (ttl%k1) ttl--;for (int j0;j64;j){if (ttltx) break;ttlttl*k1;}if (ttlv[i]sg(ttl)tt){pi;ansttl;break;}}if (sl[n]) coutAlice p ansendl;else puts(Bob);
}
