第七周周记（博弈论入门与字符串入门）
（一）公平组合游戏（Impartial Combinatorial Game，IGC）
何为公平组合游戏？
基本可以看做满足以下条件的游戏
1.两个玩家，且游戏规则对两人而言是公平的
2.游戏的状态是有限的（正因有限且所有人绝对聪明可以得出必胜或必败的局面）
3.两人轮流进行操作，直到其中一个人无法继续操作
4.游戏局势不能区分玩家身份（即now和post可以相互转换）
1.Bash Game（P-position、N-position）
一个简单的Bash游戏基本可以看做：
一个线性的石堆（总共n颗），两个人从头往尾拿石子（每次可以拿1到m颗），谁拿到最后一颗石子谁获胜
简单地分析一下，当n小于等于m时，必然是第一个人取胜（n不为0）
当n大于m时，只要后手维持一个m+1的石子数量，那么后手必然取胜
实际上，所谓的Bash Game以及后面的Nim Game都可以看做是一种一方对于必胜局面的维持或者说一方对于另一方死局的维持，理解这个思想非常重要，对于后面理解sg之类的大有助益
一些简单扩展：
因为bash game的形式不一定是每次都能拿连续的石子（即每次都能拿1到m颗），他可能只能拿指定数量的石子，所以可以将NP与dp相结合来解决问题。
简单来说，就是检查每个状态之前状态是否有死局，如果有死局，那么对于当前的人而言，他只要执行一步操作就可以把对手逼入死局，相对而言，他只要维持当前状态下的局势就必胜，而当他前面所以可行操作都是非死局，那么他的对手就是必胜开局，无论他如何操作，他的对手都会维持当前状态下的局势，因此他（先手）必败。
上述就是一种简单的NP和dp结合的思路，打表找解
除此之外，因为NP问题一般都具有一定的规律性，所以我们也时常可以通过找出规律后用求余编译运算写题（一般就找出最小规模的死局，在上面推就好了，或者打个表找规律，比较看悟性了。。。）
2.Nim Game
Nim Game就像是Bash Game的扩展，从一个石堆扩展为多个石堆，情况变得更为复杂，但是我们还是可以通过小规模的结果推理得出必胜或者必败结果
{0,0,0}、{0,1,1}、{0,k,k} 先手必败
{1,1,1}、{1,1,2}、{1,1,3} 先手必胜
我们可以根据nim-sum的思想，对所有石堆求一个异或和，如果结果为0，则先手必败，反之，先手必胜
pis：这里想说说我的想法，nim-sum的操作就是转为二进制之后看每个位数的一是奇数个还是偶数个，如果有奇数个的1位置，那么就是先手必胜，对于我而言，我是把它看做一个类似操作数的想法，下面细讲。
如果每次都只能拿一个石子，那么显而易见的，就是简单的判断奇偶性，但在尼姆游戏中可以不只拿一个，那有什么办法可以保持一个“奇偶性”吗？
我们可以保持一个操作的奇偶性，简而言之，我们在上个学期就已经知道很简单的一个操作， 用二进制可以表示所有的数字，那么，每一个数组都可以分解为二进制表示，那么只要有一个分解位置上的一的个数不为偶数,我们就可以根据最前面的为奇数次的一做一个减法，把每一位的一都变为偶数次，于是，对手的必败局面就简单地产生了。
我讲的可能过于抽象，水平不足，自己理解可以，但讲起来就差了很多，下面附上我找到的讲的最生动形象的大佬blog
https://blog.csdn.net/qq_39861441/article/details/82936117
3.sg函数
sg函数就是将Bash Game和Nim Game转化为图游戏的一类通用方法，本质理解起来并不难，可以看做是一种dp的思想（反正我是这么想的），但sg函数的值和sg函数对于子问题的异或求和确实是引人深思
最早开始让我抱有疑惑的是hdu1848，书上代码用异或的方式将子问题进行了一个集合，当时想的很简单，考虑一个先后手的关系，分多次局面就好，但仔细想了一段时候之后和遇见新的题目hdu 2999之后，我越发确信之前想法的错误性，我开始思考sg值真正的意义
在看完一个知乎问题为什么会想到用异或来算SG函数？它的本质是什么？（https://www.zhihu.com/question/51290443utm_source=qq&utm_medium=social&utm_oi=1151186619196465152）之后，结合之前对于nim游戏的思考，我对这道题目有了一点新的想法。
sg函数导出的值其实可以看做是一组石堆里面的第几个石头，做一个简单的考虑，把每个sg值的0作为终点，因为之后便是死局，胜负已定，那sg值为2的点，保证了它前面的点（即减去固定石子数的点有1和0,此处的点个人认为可以看做一个状态的集合），他们是一个连续的结构，那么我们不就可以把它看做一个nim游戏来考虑了吗？这也正好解释了异或为什么能用来处理sg函数子问题的情况。
在理解了异或nim，sg函数之后，我们就能过快乐地处理nim game离散化的问题了，可以说这就是我这一周最大的收获了。
（二）字符串
1.字符串的基本操作
emm 这一块感觉没啥好讲的，基本没啥技术含量，大概写个模拟就好了，也顺道记录一道关于尺取法的题目，这方法真的蛮神奇的
先简单谈一谈尺取法，命名还算形象吧，真的写起来也很想一个尺子的移动过程。
通俗地来说一下尺取法的基本操作方式，它就是在确定一个满足条件的区间之后，确定一个大概的方向能够找到下一个满足条件的区间，然后根据方法设定，L前移一位，R移动到能够找到下一个满足区间的位置为止，再进行记录，如此反复，直到找完整个串。
顺道附上一个之前看的blog，感觉讲的很不错https://blog.csdn.net/lxt_lucia/article/details/81091597
以及例题HDU - 6103 Kirinriki
思路，预处理首尾相加的绝对值，然后按尺取法的思想进行操作即可，对于奇数长度和偶数长度要分开处理
ac代码
#include <bits/stdc++.h>
using namespace std;
int a[5005],cnt,t,n;
inline int cal(){ ## 尺取法计算
int idx = 0,sum = 0,ans = 0,s = 0;
while(1){
while(idx < cnt && sum + a[idx] <= n) sum += a[idx++];
ans = max(idx - s,ans);
sum -= a[s++];
if(idx >= cnt) break;
}
return ans;
}
int main()
{
scanf("%d",&t);
while(t--){
string s;
scanf("%d",&n);
cin >> s;
int len = s.size(),ans = 0;
for(int i = 0;i <= len;i++){ ## 偶数长度串预处理
cnt = 0;
for(int j = 1;j + i < len && j <= i;j++) a[cnt++] = abs(s[i+j] - s[i-j]);
ans = max(ans,cal());
}
for(int i = 0;i <= len;i++){ ## 奇数长度串预处理
cnt = 0;
for(int j = 1;j + i - 1 < len && j <= i;j++) a[cnt++] = abs(s[i+j-1] - s[i-j]);
ans = max(ans,cal());
}
printf("%d\n",ans);
}
return 0;
}
2.字符串hash
比较简单的思想，用空间换时间嘛，考虑进制转换就好了
但转什么进制也是有讲究的，如果你能保证你hash的字符串很短，范围在整数类型之内，那么你完全可以用26进制hash，问题不大。
但如果超出去了，你就要考虑一个取模的问题，而偶数进制hash在取模中会遇到取模完冲突大的问题，具体原因现在只能算半知半解，自己分析不太来，姑且放之前看的大佬blog
https://blog.csdn.net/wanglx_/article/details/40400693
前半部分有非常详细的分析，后半部分的扩展可以后期继续学习
hash其实感觉不是很深，可能是思考的还不够多，不过发现一件很神奇的事情，此处暂做记录，如果以后能明白，再在下面进行补充
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef unsigned long long ll;
int main()
{
ll ans = 1,base = 2,b = 64;
while(b){
if(b & 1) ans *= base;
base *= base;
b >>= 1;
}
ans--;
ll ans2 = 1;
ans2 <<= 64;
ans2 = ans2 - 1;
ll ans3 = 1,bas = 2,k = 128;
while(k){
if(k & 1) ans3 *= bas;
bas *= bas;
k >>= 1;
}
ans3 -= ans*ans;
printf("%I64u\n%I64u\n%I64u\n",ans,ans2,ans3);
return 0;
}
奇怪之处在于，用乘法运算的结果中，原数据好像完全被保留了，只是给我们看到的结果是取模之后的，而位运算的结果，却确确实实是把超出的部分抛弃掉了，这也是我百思不得其解的地方orz
摸鱼完毕，这周的内容确实不多，但消化的一般，之后慢慢补充