博弈论 记忆化搜索    发布于 2019-08-29   518人围观   0条评论

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 888. Then selecting option 1 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

查看更多
博弈论 贪心 思维题    发布于 2019-08-13   471人围观   0条评论

题目大意

先手有n张牌,后手有m张牌,如果某人打出了某种颜色的牌,那么另一个人就不能打这种颜色的牌,最后不能出牌的人输。求问是先手胜还是后手胜。

题解

两人都是按最优策略取的博弈,不过和SG函数并没有什么关系。

两个人肯定每回合都是贪心的取对自己最有利的方案。

首先我们将两人都有的颜色的牌抽出来,剩下的就是两人各自独立的牌集,不会受对方出牌的影响。

然后我们考虑被抽出来的牌,怎样取能使得局面变得对自己有利。

如果对于某种颜色,两人共有的这种颜色的牌比较大,那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。

然后当前的人出一种颜色的牌,就可以看成是把自己原有的这种颜色的牌全部收回,把对方原有的这种颜色的牌全部丢掉。

所以我们需要离散化颜色,然后对于公共颜色的牌全部抽出,然后按照两人手中的这种颜色的牌的总数从大到小排序,然后让先手先选,后手后选直到全部选完。

选完后我们比较一下两人手里的牌的总数。

如果先手手中的牌比后手多,则先手必胜,否则先手必败。

(对于我取消流同步的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
查看更多
莫队 博弈论 NIM博弈    发布于 2019-07-30   348人围观   0条评论

题目大意

先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。

问在L-R中有多少种后手取l-r的方案能够使得先手必胜。

题解

这题是一个经典的NIM博弈。我们需要用SG函数来解决。

我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0)

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

然后我们使用区间点对总数减去区间中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   676人围观   1条评论

博弈论相关(组合游戏)

基本条件

游戏由两方参与且双方均知道对方策略(三国杀1v1就不是博弈游戏,因为双方并不知道对方手牌)且均采取最优策略。

特点

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

例1:取石子

有n堆石子,双方进行博弈游戏,每次可以从某一堆中取出任意多的石子(不大于这堆石子数)每堆中有Ai个石子
我们设先手必败态为0,先手必胜态为1,那么这个必胜态和必败态的0和1可以建成一张图。
我们可以通过暴力递推来从图上递推,但是这样未免太慢了。
我们发现一条性质:当前的值等于所有子结构的异或和:
1.最终状态异或和为0
2.对于一个必胜态(异或和不为0),存在一个必败后继状态。
3.对于一个必败态(异或和为0),不存在一个必败后继状态

SG函数

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

SG函数与必胜必败的关系

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

SG函数:游戏的和

SG定理:若局面X由若干个子游戏构成(Xi),则SG[X] = SG[X1]^SG[X2]^…^SG[XM]

例题:

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

查看更多