BNU17047-nim博弈

2024-05-04 19:38
文章标签 博弈 nim bnu17047

本文主要是介绍BNU17047-nim博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:题目链接

 

题意:题目意思很明确。就是现在有N个数字,每次一个人上去,可以把一个数字换成它的一个因子替换。直到有一

人使得所有的数字的乘积为1的时候,这个人就赢了。

 

分析:因为我们知道:对于任意一个数字A,我们都可以把这个数字写成A=p1^q1 * p2^q2 * ……* pn^qn (pi是质

数)、所以我们每次的操作就相当于任选一个数字。然后从中拿走若干素数。这样的话,问题就可这个数字中存在的

数的个数有关了。这样就回归到了Nim博弈,相当于有n堆石子,每次选一堆,从中拿走一部分石子,问最后谁赢,

以,我们只要处理每一个数字的素数因子的个数就可以了(不过,估计写挫了,跑了3620ms)

 

代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;int QuickMod(int  a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}
#define maxn 100010int num[maxn];
int cnt[maxn];
int prime[3000];
bool isprime(int x)
{if(x == 0 || x == 1)return false;if(x == 2 || x == 3)return true;for(int i = 2; i*i <= x; ++i)if(x%i == 0)return false ;return true;
}
int T;
int n;
void init()
{int k = 0;for(int i = 0; i < 2500; ++i){if(isprime(i))prime[k++] = i;}T = 0;
}
int work(int &x)
{int ans = 0;for(int i = 0; prime[i]*prime[i] <= x; ++i){while(x % prime[i] == 0){x /= prime[i];ans++;}}if(x != 1)ans++;return ans;
}
void solve()
{int ans = 0;T++;for(int i = 0; i < n; ++i){cnt [i] = work(num[i]);ans ^= cnt[i];}if(!ans)printf("Test #%d: Bob\n",T);else{for(int i = 0; i < n; ++i){int flag = 0;int tp = ans ^ cnt[i];if(!flag){for(int j = 0; j < cnt[i]; ++j){if((tp^j) == 0){flag = 1;break;}}}if(flag){printf("Test #%d: Alice %d\n",T, i+1);break;}}}
}int main()
{init();while(scanf("%d", &n) == 1){mem(num, 0);mem(cnt, 0);for(int i = 0; i < n; ++i)scanf("%d", &num[i]);solve();}return 0;
}


 

 

这篇关于BNU17047-nim博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959959

相关文章

poj2505(典型博弈)

题意:n = 1,输入一个k,每一次n可以乘以[2,9]中的任何一个数字,两个玩家轮流操作,谁先使得n >= k就胜出 这道题目感觉还不错,自己做了好久都没做出来,然后看了解题才理解的。 解题思路:能进入必败态的状态时必胜态,只能到达胜态的状态为必败态,当n >= K是必败态,[ceil(k/9.0),k-1]是必胜态, [ceil(ceil(k/9.0)/2.0),ceil(k/9.

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

AI模型的未来之路:全能与专精的博弈与共生

人工智能(AI)领域正迅速发展,伴随着技术的不断进步,AI模型的应用范围也在不断扩展。当前,AI模型的设计和使用面临两个主要趋势:全能型模型和专精型模型。这两者之间的博弈与共生将塑造未来的AI技术格局。本文将从以下七个方面探讨AI模型的未来之路,并提供实用的代码示例,以助于研究人员和从业者更好地理解和应用这些技术。 一、AI模型的全面评估与比较 1.1 全能型模型 全能型AI模型旨在在多

简单取石子游戏~博弈

很坑爹的小游戏,至于怎么坑爹,嘎嘎~自己研究去吧~! #include<stdio.h>#include<windows.h>#include<iostream>#include<string.h>#include<time.h>using namespace std;void Loc(int x,int y);/*定位光标*/void Welcome(); /*创建欢迎界面*/

综合评价 | 基于熵权-变异系数-博弈组合法的综合评价模型(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 根据信息熵的定义,对于某项指标,可以用熵值来判断某个指标的离散程度,其信息熵值越小,指标的离散程度越大, 该指标对综合评价的影响(即权重)就越大,如果某项指标的值全部相等,则该指标在综合评价中不起作用。因此,可利用信息熵这个工具,计算出各个指标的权重,为多指标综合评价提供依据。 变异系数只在平均值不为

“苹果税”引发的苹果与腾讯、字节跳动之间的纷争与博弈

北京时间9月10日凌晨一点的Apple特别活动日渐临近,苹果这次将会带来iPhone16系列新品手机及其他硬件产品的更新,包括iPad、Apple Watch、AirPods等。从特别活动的宣传图和宣传标语“閃亮時刻”来看,Apple Intelligence将会是史上首次推出,无疑将会是iOS 18的重头戏和高光时刻。 不过就在9月2日,一则“微信可能不支持iPhone16”的

美业收银系统怎么选择?博弈美业系统展示、美业SaaS管理系统源码戳

美业收银系统是一种专为美容、美发、美甲、SPA等美业门店设计的全面性结账解决方案,其重要性在于它为门店提供了全面的业务管理功能。美业收系统可以处理销售、预约管理、库存追踪和员工绩效等多项任务,不仅能够简化交易流程,还能提高门店管理效率,是提升门店竞争力和盈利能力的利器。 一套优秀的美业收银系统要专业、智能、高效、便捷!博弈美业包括PC、pad、手机APP、小程序四大端口,一套系统解决连锁美业多种

智能对决:提示词攻防中的AI安全博弈

智能对决:提示词攻防中的AI安全博弈 在2024年上海AIGC开发者大会上,知名提示词爱好者工程师云中嘉树发表了关于AI提示词攻防与安全博弈的精彩演讲。他深入探讨了当前AI产品的安全现状,提示词攻击的常见手段及其应对策略。本文将对他的演讲进行详细的解读与分析,并结合实际案例和技术手段,探讨如何在AI应用开发中提高安全性。 1. AI产品安全现状 随着大模型(如GPT系列)和AI应用的普及,A

综合评价 | 基于层次-熵权-博弈组合法的综合评价模型(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 AHP层次分析法是一种解决多目标复杂问题的定性和定量相结合进行计算决策权重的研究方法。该方法将定量分析与定性分析结合起来,用决策者的经验判断各衡量目标之间能否实现的标准之间的相对重要程度,并合理地给出每个决策方案的每个标准的权数,利用权数求出各方案的优劣次序,比较有效地应用于那些难以用定量方法解决的课题

拍卖与博弈:计算广告中的底价问题

流量变现和RTB 现代计算广告中,最广泛的流量交易模式为实时竞价模式,即Real-Time-Bidding(RTB)。实时竞价顾名思义,就是在流量到达时被放到交易市场进行公开的,实时的竞拍,参与竞拍的广告主赢得竞拍后,即可获得对这个流量的投放权,整个流程如图示。 以新浪微博的信息流广告为例,当我们刷微博时,微博的信息流(或者timeline)中会夹杂着广告,假设微博将信息流的第4和第10位作为