联训总结 DAY 6

二分答案法

1.基础

算法思想
以求最小值的最大值（最小值最大化）为例，尝试一个可能的答案，如果这个答案符合题目条件，那么它肯定是“最小”（可行解），但不一定是“最大”（最优解），然后我们换个更大的可能答案，如果也符合条件，那这个新可行解就更优，不断重复即可。怎么找呢？这时就该二分上场了。
二分前提
1.答案区间上下限确定，即最终答案在哪个范围是容易知道的。
2.检验某值是否可行是个简单活，即给你个值，你能很容易的判断是不是符合题目要求。
3.可行解满足区间单调性，即若x是可行解，则在答案区间内x+1（也可能是x-1）也可行。
实施方法
枚举一个答案，然后检测这个答案是否可行，可行往上分，不可行往下分。

2.例题

不可用

三分答案法

1.基础

当二分的函数值不是递增/减，而是先增后减或者先减后增时二分就挂了。此时需要三分法。如图：

如图这种情况先减后增有极小，若lm比rm低（即lm对应的函数值 < rm函数值）则极小点（图中最低点）肯定在[ left, rm ] ，反之在[ lm, right ]，剩下就跟二分一样根据大小关系调整区间就行了。那lm和rm取值多少？一个不错的取值是lm为整个区间的1/3点，rm为2/3点。
YJQ曰，三分法很玄学，有可能被卡死，也可能莫名其妙过大数据。
YJQ曰，有时我们可以使用2/7,5/7分法，避免被卡。

2.例题

不可用

模拟退火

不可用

博弈论

以下内容部分来自：clover_hxy的博客

经典的nim游戏

一共有N堆石子，编号1..n，第i堆中有个a[i]个石子。
每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子，至少取一颗，至多取出这一堆剩下的所有石子。
两个人轮流行动，取走最后一个的人胜利。Alice为先手。

我们定义Position
P：表示当前局面下先手必败
N：表示当前局面下先手必胜

N，P状态的转移满足如下性质：
1.合法操作集合为空的局面为P
2.可以移动到P的局面为N，这个很好理解，以为只要能转换到P局面，那么先手只需要使操作后变成P局面，那么后手就面临了一个必败的状态。
3.所有移动只能到达N的局面为P。无论怎么选取都会留给对手一个必胜状态。
其实知道这个之后应该是可以记忆化搜索或者用sg函数求解的，但是如果范围非常大，就没法做了。
就引进了nim游戏一个很神奇的结论：对于一个局面，当且仅当a1 xor a2 xor ...xor a[n]=0时，该局面为P局面，即必败局面。

证明如下：
1.全0的局面一定是P局面。
2.从任意一个异或值不为0（设为K）的局面一定可以转移到一个异或值为0的状态。由于异或计算的特殊性，我们知道一定有一个a[i]的某一位与k的最高位的1是相同的，那么必然有a[i] xor k小于a[i],我们可以通过改变a[i[的值为a[i]'，使a[_1] xor a[_2] xor a[i] xor ...xor a[n]=0。
3.对于任意一个局面，若异或值为0，则不存在任何一个移动可以使新的局面的异或值为0.如果一位的异或值为0，那么这一位上一定有偶数个1，那么只改变一个数，一定无法使其保持0。

Moore’s Nimk

n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。
这是一个nim游戏的变形，也是有结论的。

结论为：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。

证明如下：
1.全为0的局面一定是必败态。
2.任何一个P状态，经过一次操作以后必然会到达N状态：在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子，所以对于任何一个二进制位，1的个数至多改变k。而由于原先的总数为k+1的整数倍，所以改变之后必然不可能是k+1的整数倍。故在P状态下一次操作的结果必然是N状态。
3.任何N状态，总有一种操作使其变化成P状态。从高位到低位考虑所有的二进制位。假设用了某种方法，改变了m堆，使i为之前的所有位都回归到k+1的整数倍。现在要证明总有一种方法让第i位也恢复到k+1的整数倍。
有一个比较显然的性质，对于那些已经改变的m堆，当前位可以自由选择1或0。
设除去已经更改的m堆，剩下堆i位上1的总和为sum。

分类讨论：
(1)sum<=k-m,此时可以将这些堆上的1全部拿掉，然后让那m堆得i位全部置成0。
(2)sum>k-m 此时我们在之前改变的m堆中选择k+1-sum堆，将他们的第i位设置成1。剩下的设置成0.由于k+1-sum

2.例题 Bzoj 1022 小约翰的游戏

题意

反Nim游戏，即取走最后一个的人输。

解析

情况1. 每堆石子数量都为1时，堆数为偶数时先手胜，此时Nim和为0.
反之，堆数为奇数时先手必败。
情况2. 至少有一堆石子数量大于1时，
1)若只有一堆石子数量大于1(此时Nim和!=0)，先手可一定可以将局面变为奇数个1，使后手进入必败状态。
2)若有>=2堆石子数量大于1：
初始的Nim和==0时：
*1 取石子相当于减小某个数，即把某个数的某个二进制位k由1变为0，再改变低于k的位数。
*2 二进制位k为1的数有偶数。
假设先手将某数a的最高第k位改为0，又改了k之后的某些位，那么后手完全可以也找到另一个二进制第k位为1的数b，在第k位及之后做相同修改。若修改b之后，还存在大于1的数，就这样修改，并循环往复; 否则，后手完全可以不修改b，而是转化为情况 2- 1) 的先手而取胜。此种情况后手必胜
初始的Nim和!=0时：先手可通过调整最大的数，将局面变为 Nim和==0，他就成为了上面情况的"后手"。此种情况先手必胜 。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){  
    int T,n,i,x,SG,flag;  
    scanf("%d",&T);  
    while(T--){  
        scanf("%d",&n);  
        SG=flag=0;
        for(i=1;i<=n;i++){  
            scanf("%d",&x);  
            SG^=x;  
            if(x!=1) flag=1;
        }  
        if((SG==0&&flag==0)||(SG!=0&&flag==1)) printf("John\n");  
        else printf("Brother\n");  
    }  
    return 0;  
}