挑战最早挂 ！！元戎启行秋招-一面

时间线
7.1投递简历
7.11一面
7.12挂
面试内容：
三道算法题
//不会做，没想到可以这样转化.
1.Alice和Bob两个人正在玩游戏，轮流操作. Alice先手.
给定一个非严格递增的非负整数的数组, 每次操作选择一个区间[l,r]全部减一.
条件1：操作后的数组还是满足非严格递增
条件2：当数组元素全为0，则判定失败.
问谁胜利？
输入一个正整数n, 接下来输入n个元素，表示数组内容.
样例:
3
1 1 1 
输出：Alice胜

2
0 2
输出：Bob胜

题解：
把数组转化为差分数组.
区间-1操作，即变成选定下标[i,j] a[i]-1, a[j]+1,全部元素为0则失败
用石头的角度来看，对于第i堆的每个石头，可以移动 1,2,3,...n+1-i 次.
那么问题就转化成了经典nim博弈.
ans = 0;
a[i]的石头数是奇数，ans^= n+1-i;//a[i]是已经是差分数组了.
最终ans为0，则先手必败，反之，先手必胜.

//做了n*m的DP，没想到鸽巢原理
2.给定n,m.其中 n<=1e6, m <=1000  
给定一个n个元素的非负整数数组，问该数组是否存在一个非空序列，满足序列中的元素之和是m的倍数.  
样例：
3 5
5 5 5 
输出：YES  

题解：
鸽巢原理 + DP
通过鸽巢原理，可以发现，当n>=m时，必然存在一个子序列之和是m的倍数.直接输出YES
当n设dp[i][j]表示只看前i个元素，是否存在和%m为j的子序列.
dp[i][j] |= dp[i-1][j];//不选
dp[i][j] |= dp[i-1][((j - a[i])%m + m) % m];//选
最终输出dp[n][m]即可.

//写出来了
3.智力题
有一千个人犯罪后被抓了起来，他们被要求玩一个游戏来为自己免罪:
他们提前得知了游戏规则:典狱长会随机抽取这些犯人出来，他们会面对同一个桌子，上面有一枚硬币
1.犯人被叫出来可以指定这个硬币的正反面,也就是可以不动其正反性，也可以翻转。当他们操作完后就会被放回独立的牢房内
2.当某个犯人说出所有犯,人都已经被叫出来过了，且此时真的所有犯人都被叫出来了的话。犯人就胜利了
3.已知硬币一开始为正面
其中:典狱长会随机抽选犯人，这意味着他可能会叫出来某个犯人无数次，我们忽略他们花费的时间，假设典狱长是一个真随机的机器，并不断叫出犯人来完成这样的操作
有几个注意的点:
1.犯人们只有关押前提前知道了这件事情，他们可以约定一个必胜策略，这就需要你来帮助他们了
2.在游戏开始后(典狱长开始随机抽选)时犯人们不能直接通信，他们被关押起来>
3.请你设计一个必胜的游戏策略可以在有限次(即期望完成游戏的轮次不能为无限)点名后某个犯人能确定所有人真的全都被叫出来过，并且战胜典狱长

当时的题解：
犯人们约定一个计数员.
计数员负责计数，当看到硬币为反，则操作把硬币变为正，然后心里计数 +1 ，
看到硬币为正，则不操作，然后心里计数 +1
每个犯人约定只翻转一次，当看到硬币为反，则不操作，看到硬币为正，则翻转.
当计数员数到 999时，即可大声汇报.

面试时长1h30min
第二题做了一半
第三题智力题通过

隔日挂（据说算法题有做出一道就能过）