Lyrance

博弈论与期望概率

1、博弈论1.1、组合游戏规则Introduction

规则

有两个参与者

任意时刻都有确定的状态

轮流操作

当某一轮当前操作者无法操作,游戏结束

无论怎样操作,游戏都可以在有限步数内结束(无平局)

规则规定了任意状态可以到达的状态

参与者拥有游戏本身,和游戏过程的所有信息

必胜必败状态

结束状态的性质由规则决定

一个非结束状态,如果他可以到达一个必败状态,则其为必胜状态,否则其为必胜状态

1.2、Sprague-Grundy函数Introduction

Sprague-Grundy函数又称SG函数,是一种定义在组合游戏上的函数,用$g(x)$表示$x......

42

数据结构

1、线段树1.1、普通线段树Introduction

分两段维护,区间更改就打标记即可

有一些题会维护好多标记,注意运算顺序

1.2、权值线段树Introduction

普通的线段树是以坐标为下标,权值线段树以权值为下标

可以轻松查找k大k小之类的

2、主席树Introduction

函数式编程的思想,只增添不修改

利用权值线段树,每次只会增加一条链,所以复杂度是$O(logn)$的

因为权值线段树是可以进行加减操作的,所以可以求kth问题

3、平衡树4、动态树5、根号算法

16

图论

1、最短路1.1、DijkstraIntroduction

用堆优化

Codevoid dijkstra()

{

priority_queue <PA, vector<PA>, greater<PA> > q;

memset(dis, -1, sizeof(dis));

memset(vis, 0, sizeof(vis));

q.push(MK(0, s));

dis[s] = 0;

while(!q.empty())

{

int x = q.top().second;q.pop();

if (vis[x]) continue;

vis[x] = 1......

23