2020CCPC网络赛1005 Lunch (变形Nim博弈)

2020CCPC网络赛1005 Lunch (变形Nim博弈)
题意:给定你n个巧克力块,每一块巧克力的长度为l[i],两个人轮流操作,每一次操作选择一个当前的长度l的一个大于等于2的因子,然后将这个巧克力分为l/factor(l)块,当所有的巧克力变为1之后,此时再进行操作的人就会输掉游戏,问你当前给定n和每个巧克力的l[i]后,先手是输还是赢。

思路:当看到先手是赢还输的情况后,就可以想到应该是个博弈问题。然后我们可以想到假如一个长度被分成了偶数个巧克力块,增加的操作次数为偶数,那么他并不会改变当前状态下的胜负关系。而假如是增加的奇数次数的巧克力块的话,当前状态下的胜负关系是会发生改变的。
并且因为上面我们说的增加偶数个是对胜负关系没有贡献的,因此假如这个数因数中有多个2的话,我们只需要就算一个,因为再多的2和一个2的贡献是一样的,然后计算它的质因数的个数,也就是质因数分解下的每个质因子的幂次数相加。
这样就相当于与把一块巧克力用它含有的质因数个数代替了,因为这些质因数都是互不影响的个体,可以类似把他们看做一推石子中的每一个石子,因此这个问题就变成了Nim游戏的形式了,把他们的质因数的个数异或和求出即可得到答案了。

MAXN太大会超时的,5e4就够用了。
代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const int MAXN = 5e4+7;//筛素因子打到 根号N即可
int prime[MAXN],cnt;
bool vis[MAXN];
//考虑质因数分解
void Prime()//欧拉筛求一下质数
{
for(int i = 2;i < MAXN;i ++){
if(!vis[i])
prime[++cnt] = i;
for(int j = 1;j <= cnt&&prime[j]*i < MAXN;j ++){
vis[prime[j]*i] = 1;
if(i % prime[j] == 0)
break;
}
}
}
//直接因数分解 会超时 所以先用线性筛 把素数处理一下 然后再直接用素因数筛
//因为先把合数因子去掉了 所以简单的质因子分解 是遍历所有根号n前面的数 但是这个题会超时 所以就先打出素因子直接处理素因子即可
int a[17],num[17];

int main()
{
int T,n;
Prime();
scanf("%d",&T);
while(T--){
memset(num,0,sizeof(num));
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&a[i]);
}
int cot = 0;
int ans = 0;
for(int i = 1;i <= n;i ++){
if(a[i]%2 == 0) num[i]++;//因数2的贡献只计算一次 因为他并不会改变 当前的胜负关系 所以多个和一个的作用效果是一样的
while(a[i]%2 == 0){
a[i] >>= 1;
}
for(int j = 1;j <= cnt && prime[j] <= a[i];j ++){
while(a[i]%prime[j] == 0){
num[i]++;
a[i] /= prime[j];
}
}
if(a[i] > 1) num[i]++;//大于1就还要再分解一次
ans ^= num[i];
}
if(ans) puts("W");
else puts("L");
}
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

2020CCPC网络赛1005 Lunch (变形Nim博弈)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 2020CCPC网络赛1005 Lunch (变形Nim博弈)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏