HDU 6597 Game [不平等博弈+三进制状态]
Problem给定一个多个3*3的棋盘格,包含#,.,O和X
Alice和Bob轮流对这些棋盘格做操作,当一方不能操作了算输
Alice每次可以选择一个O,将其变成#
同时,对以下三种事件挑选一种发生:[不能不选]
选择的格子上下格子均变成#
选择的格子左右格子均变成#
上述两种事件同时发生
Bob每次可以选择一个X,将其变成#,没有任何伴随事件
如果Alice或者Bob始终能赢则对应输出Alice和Bob
否则如果先手或者后手始终能赢则对应输出First和Second
否则直接输出Others
Solution$SN={Alice \ can \ get|Bob \ can \ get}$
非平等博弈只存在三种情况:
$SN>0$:Alice总能够取胜
$SN<0$:Bob总能取胜
$SN==0$:后手总能取胜
我们对$3*3$棋盘进行三进制状压
暴力预处理出每种状态下的$SN$,$Multi-SN$情况将$SN$相加判断即可
123456789101112131415161718192021222324252627282930313233343536 ...
POJ 2931 Procrastination [不平等博弈]
Problem游戏开始有四座塔,每座均由正方体叠成,所有正方体是黑色或者白色
玩家$L$和$R$轮流操作,每次选定一个正方体,将正方体及其以上正方体全部拿走
$L$玩家只能选择白色正方体,$R$玩家只能选择黑色正方体,不能操作者输
如果$L$玩家无论先手或者后手都能赢,则称局面为$W-configuration$
定义子局面为三塔局面即为$C$,对于完整局面$(C,T)$
如果对于任意塔$T$,$(C2,T)$为$W-configuration$时,$(C1,T)$均为$W-configuration$
则称$C1$不劣于$C2$,给定$C1$和$C2$,判断$C1$是否不劣于$C2$
Solution考虑一座塔的SN值,当塔为空时$SN={|}=0$
如果塔包含一个白色正方体,则玩家L拥有可转移到$0$的决策,$SN={0|}=1$
如果塔包含n个白色正方体,则$SN={0,1,…,n-1|}=n$
同理塔包含n个黑色正方体时$SN=-n$
当塔包含n个白色正方体和顶端一个黑色正方体时,$SN={0,1,…,n-1|n}={n-1|n}=n-\frac{1}{2}$
如果包含n个白色 ...
2019NowCoder 8E Explorer [线段树分治+并查集]
Problem有$10^9$只小怪兽,第$i$只编号为$i$
有一张$n$个点,$m$条边的无向图$(n,m \le 10^5)$
每条边只允许编号在$[l,r]$之间的小怪兽通过
问有多少小怪兽可以从$1$点抵达$n$点
Solution我们对边标号区间$[l,r]$进行离散,最多产生$2*m-1$个区间,左闭右开处理
对区间进行时间分治,在线段树节点上保存覆盖子树所有区间的边$id$
对线段树DFS遍历,当$1$和$n$连通时将节点包含的编号统计入答案即可
连通性判断用可回溯并查集,复杂度$O(mlog_2m)$
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include <bits/stdc++.h>using namespace std;const int N = 200000 + 10;// Union ...
CF 938 G Shortest Path Queries [线段树分治+并查集+线性基]
Problem给定一张无向边权图,要求维护三个操作
OP1.$[x,y,z]$:在点$x$和点$y$之间加一条边权为z的边,保证之前没有边
OP2.$[x,y]$:将点$x$和$y$之间的边删除,保证之前有边
OP3.$[x,y]$:查询$x$到$y$的路径的异或最小值,可以是非简单路
Solution图上两点异或路径的最小值为生成树上异或距离和树上环的组合
我们以OP3为时间线建线段树,将覆盖操作时间点的边保存在线段树节点
对OP3的线段树进行DFS遍历,用并查集维护两点间的$xor$距离
当成环时将环加入$xor$线性基,在叶节点查询$xor$线性基和$xor$距离组合的最小值即可
线性基空间$O(30)$可以选择直接传参,并查集空间$O(n)$需回溯
时间复杂度$O(mlog_2t)$,$t$为OP3的数量,$m$为总边数
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697 ...
2019NowCoder 10F Popping Balloons [枚举+线段树]
Problem给定$n(n \le 10^5)$个点的坐标$(x,y)$
选择三条距离相邻距离为r的竖线和三条相邻距离为r的横线,使得线上的点数量最多
Solution考虑枚举横线的选取,数据结构维护竖线的极值
我们把相邻为r的三条竖线的值的和保存在第一条竖线上,即可数据结构维护
考虑枚举的横线和竖线的重复点部分,我们将枚举的横线上的点删除,修改竖线,统计完加回
每个点只会被删除三次,因此总复杂度$O(nlog_2n) $
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>using namespace std;const int L = 100000;const int N = 300000 + 10;vector<int> v[N];int d[N], T[N << 2], M;void upd(int x, int y) { T[M + x] += y; ...
HDU 6653 Halt Hater [构造]
Problem你位于$(0,-1)$到$(0,0)$的路上,每到一个整点,你可以选择左右转或者直行,右转不产生代价,左转的代价为$a$,直行的代价为$b$,求抵达目标点$(x,y)$的最小代价
Solution考虑到右转不花费代价,我们将每四条边缩点,以方格中心为点重构图
在新图中,直行代价为$b$,斜行代价为$a$,先求出通过斜行或者直行走到一条直线上的最小代价,然后求解一条直线的最小代价即可
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;typedef long long ll;int a, b;ll Calc(ll x, ll y) { if (y < x) swap(x, y); ll res = x * min(a, 2 * b); y -= x; res += (y / 2) * 2 * min(a, b); if (y & 1) res += b; return res; ...