# Tag-博弈论

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

## Description

In a world where ordinary people cannot reach, a boy named "Koutarou" and a girl named "Sena" are playing a video game. The game system of this video game is quite unique: in the process of playing this game, you need to constantly face the choice, each time you choose the game will provide 1−3 options, the player can only choose one of them. Each option has an effect on a "score" parameter in the game. Some options will increase the score, some options will reduce the score, and some options will change the score to a value multiplied by −1 .

That is, if there are three options in a selection, the score will be increased by 1, decreased by 1, or multiplied by −1. The score before the selection is 88. Then selecting option will make the score become 9, and selecting option 2 will make the score 7 and select option 3 to make the score −8. Note that the score has an upper limit of 100 and a lower limit of −100. If the score is 99 at this time, an option that makes the score

## 题解

（对于我取消流同步的cin比自己写的快读要快这件事，我真的很疑惑……）

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 1e5+5;
int a[maxn],b[maxn];
unsigned long long mod;
unsigned long long k1, k2;
unsigned long long rng() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
int t;
int n,m,p;
int cnt = 0;
int c[maxn<<1];
int q[maxn<<1];
int com[maxn<<1];
struct point{
int val,id;
}e[maxn];
bool cmp(point a,point b

## 题解

l-r的SG函数异或和为0，即前缀异或和ssg满足ssg[r] = ssg[l-1]，问题转化为统计区间中有多少ssg相等的点对数。

## 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int n,m;
struct query{
int l,r,t,id;
}q[maxn];
int belong[maxn];
int upd[maxn];
int qcnt,dcnt;
int a[maxn],b[ma
2017-01-27 08:58:23 |  1 Comments  |  博弈论

# 博弈论相关（组合游戏）

### 特点

1.有很多歌独立的子游戏。
2.每次操作可以选取某个子游戏进行
3.所有的子游戏结束，全局游戏便结束

### 例1：取石子

1.最终状态异或和为0
2.对于一个必胜态（异或和不为0），存在一个必败后继状态。
3.对于一个必败态（异或和为0），不存在一个必败后继状态

### SG函数

X状态下的SG函数，SG[X] = MEX{${A}_{i}$$A_i$},其中MEX函数表示当前序列中最小的没有出现的自然数

#### SG函数与必胜必败的关系

SG函数为0,则当前状态先手必败，若不为0，则当前状态为先手必胜。

#### SG函数：游戏的和

SG定理：若局面X由若干个子游戏构成（${X}_{i}$$X_i$），则SG[X] = SG[X1]^SG[X2]^…^SG[XM]

#### 例题：

David 玩一个石子游戏。游戏中，有n堆石子,被编号为0..n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k{i

Title - Artist
0:00