下棋计算

经典博弈

分析

树的删边游戏,参见论文。
参考代码

莫队

Every-SG

hdu 3595

code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int INF = 1e9;

int vis[30], sg[30];
void init()
{
    sg[0] = 0;
    for(int i = 0; i < 30; i++)
    {
        memset(vis, 0, sizeof vis);
        for(int j = 1; j < i; j++)
        {
            vis[sg[j] ^ sg[i - j]] = 1;
        }
        for(int j = 0; j < i; j++) vis[sg[j]] = 1;
        for(int j = 0; ; j++)
        {
            if(!vis[j])
            {
                sg[i] = j;
                printf("sg[%d]:%d\n", i, j);
                break;
            }
        }
    }
}

int main()
{
    //init();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        int ans = 0;
        while(n--)
        {
            int x;
            scanf("%d", &x);
            if(x % 4 == 3) x++;
            else if(x % 4 == 0) x--;
            ans ^= x;
        }
        if(ans) puts("Alice");
        else puts("Bob");
    }
    return 0;
}

splay 

SG函数

分析

Every-SG游戏,对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数,通过dfs找到必败态和必胜态的转移,对于必胜态,尽可能的慢结束游戏,对于必败态尽可能快的结束游戏。

bzoj
3489(AC)

Anti+Multi SG 233

hdu 2509

分析

看完论文就会做了,

一堆石子数量为2 时
的后继有:0,1和(1,1),他们的SG值分别为0,1,0,所以sg(2) =2。

一堆石子数量为3
时的后继有:0、1、2、(1,2),他们的SG值分别为0、1、2、3,所以sg(3) =
4。

一堆石子数量为4
时的后继有:0、1、2、3、(1,3)和(2,2),他们的SG值分别为0,1,2,4,5,0,所以sg(4)
= 3.

打表可以找到规律,见代码。

bzoj 3747(AC)

Multi-SG

hdu 3032

pku 2311

pku 3537

bzoj 2940

bzoj 1188

bzoj 3576

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MAXN = 1e3 + 10;

int next[MAXN], head[MAXN], to[MAXN]; // 前向星
int vis[MAXN]; // 标记数组
// v[i]: 这里就解决了冲突,因为每添加一条边,其实是加入两条边,但是题目本身会存在重边的情况,注意到cnt初始化为1,第一条边是从2开始的,
//       这样每经过一条边,会把相应的v[i]和v[i^1]置为1,正好使得每条边只会被访问一次而不和题目的重边冲突。
int v[MAXN];
int w[MAXN];   // 标记环
int s[MAXN];   // 栈
int cnt, top;
int add(int u, int v)
{
    to[++cnt] = v;
    next[cnt] = head[u];
    head[u] = cnt;
}

int dfs(int x)
{
    vis[x] = 1;
    s[++top] = x;
    int ans = 0;
    for(int i = head[x]; i; i = next[i])
    {
        if(!v[i])
        {
            v[i] = 1; v[i ^ 1] = 1;
            int tmp = 0;
            if(!vis[to[i]]) tmp = dfs(to[i]) + 1;
            else
            {
                int q = s[top--];
                while(q != to[i])
                {
                    w[q] = 1;
                    q = s[top--];
                }
                top++;
                return 1;
            }
            if(w[to[i]]) ans ^= (tmp & 1); // 本来要判断环的奇偶性,回溯的时候是0,1交替,010101...
            else ans ^= tmp;
        }
    }
    return ans;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int ans = 0;
        while(n--)
        {
            memset(next, 0, sizeof next);
            memset(head, 0, sizeof head);
            memset(vis, 0, sizeof vis);
            memset(v, 0, sizeof v);
            memset(w, 0, sizeof w);
            int m, k; cnt = 1; top = 0;
            scanf("%d%d", &m, &k);
            for(int i = 0; i < k; i++)
            {
                int x, y;
                scanf("%d%d", &x, &y);
                add(x, y);
                add(y, x);
            }
            ans ^= dfs(1);
        }
        if(ans) puts("Sally");
        else puts("Harry");
    }
    return 0;
}

bzoj 2324

博弈论进阶之SG函数

hdu3032

Nim游戏

pku 2975

bzoj 1299

题意

一共有n个游戏,每一个游戏有两堆石子,一次移动可以从大的那堆石子里拿小的那堆石子的整数倍的石子。只要是可以操作的游戏都要进行操作,不能进行操作的人负。

bzoj 1125

不平等博弈有空再看

sg 函数

参考
通俗易懂
论文

poj 2451

阶梯博弈

bzoj 1115

BC #90B

pku 1704

hdu 4315

hdu 3389

几类经典的博弈问题

  1. 阶梯博弈:
    只考虑奇数号楼梯Nim,若偶数楼梯只作容器,那么游戏变为Nim。题目
  2. 翻转硬币:
    局面的SG值为局面中每个正面朝上的棋子单一存在时的SG值的异或和。题目
  3. Multi-SG游戏:
    对于一个单一游戏,不同的方法可能会将其分成不同的多个单一游戏。每一方法对应的多个单一游戏的游戏的和即可以表示这种方法的NP状态。而这个单一游戏的SG函数即为未在所有方法的SG函数值中出现过的最小值。题目
  4. Anti-SG游戏和SJ定理 (在论文中有详细的论述和证明)
  5. Every-SG游戏:
    对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。题目
  6. 树的删边游戏:
    叶子节点的SG值为0;中间节点的SG值为它的所有子节点的SG值加1后的异或和。题目
  7. 无向图的删边游戏:
    我们可以对无向图做如下改动:将图中的任意一个偶环缩成一个新点,任意一个奇环缩成一个新点加一个新边;所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG
    值。

bzoj 3578 GTY的人类基因组计划 (AC)

Anti-Nim

bzoj 1022

题意

Multi-SG

给 n 堆石子, 每次有两步可选的操作,

  1. 将一堆 石子分成两堆
  2. 拿走一堆石子的任意个

最后不能行动的输。

博弈论入门之威佐夫博弈

题目

bzoj 2962(AC)

Hackenbush和纳什均衡直接弃掉了

题意

  1. 有 N个局部联通的图。
  2. Harry 和
    Sally轮流从图中删边,删去一条边后,不与根节点相连的部分将被移走。Sally为先手。
  3. 图是通过从基础树中加一些边得到的。
  4. 所有形成的环保证不共用边,且只与基础树有一个公共点。
  5. 谁无法移动谁输。

bzoj 3910
(好像可以并查集?)

博弈论进阶之Every-SG

poj3710

FFT

树的删边游戏

pku 3710

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MAXN = 1e3 + 10;

int dp[MAXN][MAXN];

int dfs(int p, int q)
{
    if(p > q) swap(p, q);
    if(!p) return dp[p][q] = 0;
    int k = q / p, tp = q % p, tq = p;
    int flag = dfs(tp, tq);
    if(k == 1)
    {
        dp[p][q] = dp[tp][tq] + 1;
        return flag ^ 1;
    }
    else
    {
        if(!flag) dp[p][q] = dp[tp][tq] + 1;
        else dp[p][q] = dp[tp][tq] + 2; // 后面存在一个不是终止态的必败态,这样至少会增加2步。
        return 1;
    }
}

int main()
{
    int N;
    memset(dp, -1, sizeof dp);
    while(~scanf("%d", &N))
    {
        int ans = 0;
        while(N--)
        {
            int p, q;
            scanf("%d%d", &p, &q);
            dfs(p, q);
            ans = max(ans, dp[min(p, q)][max(p, q)]);
        }
        puts((ans & 1) ? "MM" : "GG");
    }
    return 0;
}

树上莫队

博弈论入门之巴什博奕

hdu3595

bzoj
4520(AC)

并没有什么理论基础的机智博弈

pku 2484

bzoj 2463

bzoj 3895

pku 1740

bzoj 1982

pku 2505

day1  bzoj  3648 寝室管理
 环套树+点分治

博弈论入门之斐波那契博弈

高斯消元

博弈论进阶之Anti-SG游戏与SJ定理

后缀自动机

不过确实是没时间了,毕竟博弈只是一小块内容。

KD-tree

SG函数部分内容大多借鉴自zyf学长
也有一些自己独到的理解

bzoj 3123 (AC)

博弈论入门之nim游戏

SG函数

pku 2425

pku 2960

bzoj 1874

bzoj  1513  (AC)

题目还有很多没切完

bzoj 4176  (AC)

博弈论进阶之树的删边游戏与无向图的删边游戏

bzoj
1493(AC)

博弈论进阶之Multi-SG

code 1743 (AC)

mobius反演

day2  FJ集训  贪吃蛇

APIO  2012 kunai

APIO  2008 免费道路

bzoj 3029

bzoj
4154(AC)

分治

bzoj
1636

bzoj  4537

bzoj
4811(AC)

hdu 3592

bzoj 2813 (AC)

bzoj  4500

差分约束

UVA 10766

bzoj 1024

bzoj
2707(AC)

bzoj 2820  yy的gcd (AC)

hdu 3853 (逆推)

bzoj 3212(AC)

poj 2482  (扫描线)(AC)

bzoj
3456(AC)

据说可以写dsu on the tree

bzoj
1699

bzoj
4555(AC)

88bifa必发唯一官网,bzoj 1299 (AC)

bzoj 2898

codeforces
623E

启发式合并+并查集

bzoj 1502

st表

计算几何

bzoj 1778

bzoj 3489(AC)

bzoj 412(AC)

splay 

记忆化搜索

bzoj
3884 

bzoj 1507 (块状链表AC)

bzoj 2669(AC)

点分治

bzoj 4491

bzoj 1645 城市地平线 (扫描线)
(AC)

bzoj 4372 

bzoj
1770(AC)

博弈:

bzoj
2406(AC)

poj 2983

有上下界的网络流

bzoj
4034 (AC)

线段树

bzoj 4213

poj 2795
 从小区间向大区间枚举,枚举当前位置,查询当前字母出现在后面的那些位置,然后将位置之间的答案相乘累加给当前区间。

bzoj
4130

bzoj 3925

分块

神奇数论

差分约束

bzoj 1969(AC)

bzoj 3226
(目前想法:将每两个点之间加入一个点将所有开区间的操作作用在插入的点上,变成闭区间操作,最后插叙的时候如果在加入的点中就是开区间,AC)

bzoj 1356
(找出所有的直线,按照其中一个端点排序,对于端点相同的两条线段,单调的找直角,然后计算另一个点的坐标看是否存在,如果存在就更新答案。内存有点卡)

bzoj 4540(AC)

bzoj
2844

APIO  2009 oil  bzoj 1177

生成树计数

概率期望

bzoj 4085

二维线段树+标记永久化

bzoj 4336

链剖

bzoj 3529 sdoi 2014  (AC)

hdu 5267 动态点分治,和hdu
5571类似,可以对于每一位分开考虑。

bzoj 3159 (AC)

启发式合并+树上主席树

codeforces
343D(AC)

bzoj 1758 (TLE)

APIO  2009 会议中心  bzoj 1178

codeforces 716E

bzoj 4059

codeforces
444C(可以用线段树,每次暴力修改,直到区间的颜色相同)(AC)

bzoj 3435
不会替罪羊树啊,会了再说。。。

乱搞