2023/12/1
博弈论
巴什博弈
（只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。）
P/N分析
N为先手必胜态， P为先手必败态
那么首先对于石子为0时，该状态无路可走，所以先手必败，P点
对于1~3，可以走到0点，让后手的状态为P，既然对手必败了，那么我们先手必胜
总结为：对于一个状态，若能到达的状态都是N状态，即自己无论怎么走对手一定必胜，则必定先手必败。反之如果能走到一个点让对手先手必败，那这个点就是先手必胜
尼姆博弈1
有n堆石子，每次任选1堆，取走若干个，先拿完的赢
参考异或和的意义：表示二进制上每一位1的个数的奇偶性，若为奇数则异或和在这一位上表现为1。
异或和为0，说明每一位都为偶数个，现在我们取走石子，相当于拿走一些位上的1，这就必使异或和非0
考虑清楚上述结论：我每一次操作都保持异或和为0，对方则只能使异或和非0。
那么异或和非0，则说明石子未被取尽。说明什么，对方一定无法取胜！
而我每次保持异或和为0，并且每一轮的石子数量都在减少，说明我一定能在某一次操作后使石子数为0，即我取胜
那么显然原本 a[1] ^ a[2] ^ ……^ a[i] ^ …… ^a[n] = s, 现在变成了a[1] ^ a[2] ^ ……^ (a[i] ^ s ) ^ …… ^a[n] = s ^ s = 0。
设有 m 堆扑克牌，每堆牌的数量分别为 a0,a1,…,am，设 a0 ^ a1 ^ … ^ am = ans，若 ans = 0，则后手必胜，即输出 0。反之，先手必胜，此时需要输出其可行的方案数，根据尼姆博弈，若能找到某个位置 k，使得
(ans ^ ak) <= ak，则将方案数加一，最后输出方案数即可。
就是与异或和再异或得到的数比自身小的数，因为这堆就这么多，不能拿比他还多的扑克牌
尼姆博弈k
有n堆石子，每次任选k堆，取走若干个，先拿完的赢
把所有数字（每堆的石子个数）转换成二进制后，求每一位上1的个数，如果每一位都满足1的个数%(k+1)==0，那么就是必败态
sg函数
1.sg()为0是必败态，sg（）！=0 是必胜态
2.sg(x)=n 表示x点可以到达sg(y)=1,2,...,n-1的点
sg(x)={v|mex[sg(v)] } ,其中v是x可以通往的下个状态点（经过一次操作，x状态能变为v状态）
若x状态为必败态，则sg(x) = 0
那么我们只要从必败态开始，找寻能通过操作变成它的状态，就能根据定义计算出它们的sg值，不断通过已知sg值的状态计算未知sg值的状态。
因为博弈论抽象为有向图后必为一个连通图，所以能计算出所有状态的sg值。
//sg打表
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 10;
int dp[N];
int mex(set<int> st)
{
for (int i = 0;; i++)
{
if (st.find(i) == st.end())
return i;
}
}
int sg(int x)
{
if (dp[x] != -1)
return dp[x];
set<int> st;
for (int i = 1; i <= x; i *= 2)
st.insert(sg(x - i)); //x为当前点，x-i枚举所有能转移到的点
dp[x] = mex(st);
return dp[x];
}
void solve()
{
memset(dp, -1, sizeof dp);
int n;
while (cin >> n)
{
if (sg(n))
cout << "Kiki\n";
else
cout << "Cici\n";
}
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
子问题合并
若是该博弈问题能分割成多个子模型，那我们是不是就能减小状态数，然后单独求解每个子模型的sg值
那现在问题就转化成了，现在知道了多个子问题的sg值，我们如何求出该问题的sg值
其实就是所有子问题的sg值异或和让我们来看看sg值的含义，对于一个状态x，sg(x) = k, 那就代表着状态x能转移到 sg(y) = 0 ~ k – 1的状态y。
发现没有，这是否跟尼姆博弈中的取石子操作十分相似。若一堆石子有k个，那么选取这堆进行操作，取的石子个数为 1 ~ k个。所以在我操作完之后，该堆石子会变为0 ~ k – 1个。
完全一毛一样，那么我们在尼姆博弈中的必胜策略是不是也同样能迁移到SG中？只要所有子问题的异或和非0，那么我就可以保证我所有子问题的异或和为0，那么我就是必胜
即sg(x) = sg(x[1] ^ x[2] ^ …… ^ x[n]) != 0, x为必胜态
D. Professor Higashikata
重点是判断字符串中哪些点是重要的，从而来判断在有cnt个1的时候哪些点需要被放1.
并查集维护一些点的终点都是相同且遍历的时候不确定的情况
#include <bits/stdc++.h>
using namespace std;
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define endl '\n'
const int N = 1e6 + 10;
int fa[N];
int n, m, q;
int a[N], t[N];
void init()
{
for (int i = 1; i <= n + 1; i++)
fa[i] = i;
}
int find(int x)
{
if (fa[x] == x)
return x;
else
{
fa[x] = find(fa[x]);
return fa[x];
}
}
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int val) // 对a[x]+val,同时修改t数组，t是真实意义上的树状数组
{
while (x <= n)
{
t[x] += val;
x += lowbit(x);
}
}
int getsum(int x) // 计算sum[1,x] 1到x的前缀和 ，a[1]..a[x]的和
{
int sum = 0;
while (x)
{
sum += t[x];
x -= lowbit(x);
}
return sum;
}
int query(int l, int r) // 区间求和 ， 前缀相减
{
return getsum(r) - getsum(l - 1);
}
void solve()
{
cin >> n >> m >> q;
init();
string s;
cin >> s;
s = " " + s;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (s[i] == '1')
cnt++;
}
// cerr << cnt << endl;
int tot = 0;
while (m--)
{
int l, r;
cin >> l >> r;
for (int i = find(l); i <= r; i = find(i))
{
fa[i] = i + 1;
a[i] = ++tot;
if (s[i] == '1')
add(a[i], 1);
}
}
while (q--)
{
int pos;
cin >> pos;
if (!a[pos])
{
if (s[pos] == '1')
{
cnt--;
s[pos] = '0';
}
else
{
cnt++;
s[pos] = '1';
}
}
else
{
if (s[pos] == '1')
{
cnt--;
add(a[pos], -1);
s[pos] = '0';
}
else
{
cnt++;
add(a[pos], 1);
s[pos] = '1';
}
}
int x = query(1, cnt);
if (cnt >= tot)
{
cout << tot - query(1, tot) << endl;
}
else
cout << cnt - x << endl;
}
}
signed main()
{
Acode;
int T = 1;
while (T--)
{
solve();
}
return 0;
}