[AcWing] 1319.移棋子游戏 博弈论 Sg函数板子题

news/2024/2/27 21:31:17

题目链接:1319.移棋子游戏

题解

好久没写博弈论的题了,写几道复习一下,博弈论SG主要由两大部分组成:SG函数和SG定理

  1. SG(x)=mex(S),其中S是x的后继状态的SG函数值集合,mex(S)表示不在S内的最小非负整数。
  2. SG定理:游戏和的SG函数等于各子游戏SG函数的NIm(异或)和。

本题DAG图,博弈论SG的典型运用,记忆化搜索。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-xconst double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=2e3+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int> g[maxn];
int d[maxn];int sg(int u)
{if(d[u]!=-1) return d[u];set<int> s;for(int i=0;i<g[u].size();i++){int v=g[u][i];s.insert(sg(v));}for(int i=0;;i++){if(s.count(i)==0){d[u]=i;break;}}return d[u];
}int main()
{memset(d, -1, sizeof(d));int n,m,k; scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y; scanf("%d%d",&x,&y);g[x].push_back(y);}int ans=0;for(int i=1;i<=k;i++){int u; scanf("%d",&u);ans^=sg(u);}if(ans) cout << "win";else cout << "lose";
}

http://www.ppmy.cn/news/312753.html

相关文章

1319 移棋子游戏(sg函数模板)

1. 问题描述&#xff1a; 给定一个有 N 个节点的有向无环图&#xff0c;图中某些节点上有棋子&#xff0c;两名玩家交替移动棋子。玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点&#xff0c;无法移动者输掉游戏。对于给定的图和棋子初始位置&#xff0c;双方都会采取…

hpuoj【1319】小写换大写【字符串】

1319: 小写换大写 [水题] 时间限制: 1 Sec 内存限制: 128 MB 提交: 151 解决: 112 题目描述 读入一个英文文本行&#xff0c;将其中每个单词的第一个字母改为大写。 输入 随便输入几个单词&#xff0c;字符数组范围在1000以内。 输出 输出转换后的文本。 样例输入 acs go…

LightOJ 1319 - Monkey Tradition CRT除数互质版

本题亦是非常裸的CRT。 CRT的余数方程 那么定义 则 其中 为模mi的逆元。 /** Date : 2016-10-23-15.11* Author : Lweleth (SoungEarlfgmail.com)* Link : https://github.com/Lweleth* Version : $*/ #include <stdio.h> #include <iostream> #include <…

OpenGL 点光源的多遍阴影贴图

OpenGL点光源的多遍阴影贴图 OpenGL点光源的多遍阴影贴图简介源代码剖析主要源代码OpenGL点光源的多遍阴影贴图简介 我们学习了阴影贴图的基础知识-第一次从光源位置通过使用光方向作为视图矢量,第二次从相机使用第二次通过的数据来计算阴影。那时,大多数程序员问自己-这种方…

LightOJ 1319 - Monkey Tradition (中国剩余定理)

题意&#xff1a;http://www.lightoj.com/volume_showproblem.php?problem1319 就是x%a[i]b[i] 求x的值 讲解&#xff1a;http://www.cnblogs.com/fu3638/p/7455137.html #include<cstdio> #include<cstring> #include<algorithm> #include<iostream&g…

业务经验总结

DWD层做的事&#xff1a; 1.空值处理 2.日期标准化 3.过滤无意义的数据 4.维度退化和降维 5.用户行为宽表和业务表数据一致性 将用户行为宽表和业务表进行数据一致性处理 select case when a is null then b else a end as JZR, 数据验证、总分验证、主键验证、抽样验证…

MySQL 错误记录 请ctrl+f查找

MySQL错误代码大全 本章列出了当你用任何主机语言调用MySQL时可能出现的错误。首先列出了服务器错误消息。其次列出了客户端程序消息 B.1. 服务器错误代码和消息 服务器错误信息来自下述源文件&#xff1a; 错误消息信息列在share/errmsg.txt文件中。“%d”和“%s”分别代表编…

2018.10.12【BZOJ1319】【CEOI2008】oeder(最小割)

传送门 解析&#xff1a; 最小割入门题。 思路&#xff1a; 我们考虑直接做出全部的任务&#xff0c;然后考虑我们可能获得的最小亏损&#xff0c;其中放弃一个任务也是一种亏损&#xff0c;租用或购买一个机器也是一种亏损。 我们这样建图&#xff0c;从源点向每个任务连容量为…

[欧拉回路] Jzoj P1319 邮递员

Description 邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路&#xff08;输入数据将会保证这么一条路是一定存在的&#xff09;。 但是&#xff0c;每条路线都是有一个花费的。各个村子里的村民希望邮递员到达他们村子的时间越早…

【每日一题】 1319. 连通网络的操作次数

【每日一题】 1319. 连通网络的操作次数 避免每日太过咸鱼&#xff0c;一天搞定一道LeetCode算法题 一、题目描述 用以太网线缆将 n 台计算机连接成一个网络&#xff0c;计算机的编号从 0 到 n-1。线缆用 connections 表示&#xff0c;其中 connections[i] [a, b] 连接了计算…

Light Oj 1319 (中国剩余定理)

题目链接&#xff1a;http://lightoj.com/volume_showproblem.php?problem1319 中国剩余定理模版&#xff0c;详解------>>>&#xff08;中国剩余定理讲解&#xff09; 1319 - Monkey Tradition PDF (English)StatisticsForum Time Limit: 2 second(s)Memory Limit:…

[lightoj1319] 中国剩余定理

题目链接&#xff1a;lightoj1319 —————————————- 概述 题目的大意如下。 对于一个数L&#xff0c;已知&#xff1a; L≡r1(mod p1) L≡r2(mod p2) …… L≡rn(mod pn) 其中 pi 均为质数且各不相同。现让你求最小的L&#xff0c;满足上述条件。 ——————…

【JZOJ1319】邮递员

description 邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路&#xff08;输入数据将会保证这么一条路是一定存在的&#xff09;。   但是&#xff0c;每条路线都是有一个花费的。各个村子里的村民希望邮递员到达他们村子的时…

TOJ-1319 Odd Loving Bakers

There is a group of n (1 ≤ n ≤ 100) bakers in the town of Utopia. These bakers hold a monthly celebration in which they award a prize to some of the luckier among themselves. These lucky guys are chosen as follows: In the beginning there are some chalk m…

AcWing 1319. 移棋子游戏

sg函数是一张有向无环图 尼姆博弈对每一张图sg&#xff08;值&#xff09;进行游戏 就是加强版的集合尼姆博弈(集合尼姆博弈中拓展是根据集合可能的新状态)&#xff0c;这里是回归本质&#xff0c;sg操作是对每个状态拓展出边&#xff0c;并通过出边sg值集合进行mex操作&#x…

ZOJ 1319 Black Box

/*优先队列*/ #include<iostream> #include<queue> #include<algorithm> using namespace std; int main() {int caseN0;cin>>caseN;while(caseN--){int i0,j1,N0,M0;cin>>N>>M;int *anew int[N1];int *unew int[M1];for(i1;i<N;i)cin…

关于Windows 7 64位系统 HP M1319f 打印机无法扫描的解决办法

此办法主要针对Windows7 64位系统的用户&#xff0c;对于Xp系统或者Windows8系统没有验证。 笔者在将电脑重装成win7 64位系统后在安装hp打印机驱动的时候打印机自带的驱动盘提示不支持64位系统&#xff0c;笔者只能在HP官网上下载64位系统的驱动&#xff0c;但是这时候问题出现…

“HP LaserJet M1319f 激光一体机”在 Windows XP 下实现共享打印

一、“HP LaserJet M1319f 激光一体机”在 Windows XP 下实现共享打印 文章简介 在主机端上安装了激光一体机的驱动程序后&#xff0c;为了让网络中其他客户机使用该一体机进行打印&#xff0c;需要安装设置共享打印机。可以将 HP LaserJet M1319f 激光一体机设置为共享打印机。…

【Leetcode】DP | 打家劫舍,当一个机灵的小偷

198 打家劫舍 令 D [ i ] D[i] D[i]表示前 i i i间房子的最大收益&#xff1a; D [ i ] max ⁡ ( D [ i − 1 ] , D [ i − 2 ] n u m s [ i ] ) D [ 0 ] n u m s [ 0 ] D [ 1 ] max ⁡ ( n u m s [ 0 ] , n u m s [ 1 ] ) D[i] \max(D[i -1], D[i-2]nums[i]) \\ D[0] …

安卓大作业 书籍列表APP

系列文章 安卓大作业 书籍列表APP 文章目录 系列文章1&#xff0e;背景2&#xff0e;功能3. 源代码获取 1&#xff0e;背景 我做的项目是一个可以查看到书籍列表以及详情效果的内容&#xff0c;主要使用到的技术有Intent数据传递以及数据库存储的应用&#xff0c;其次使用的组…
最新文章