无严谨证明
Alice与Bob对局时 玩到游戏终局,Alice面对的可以必胜的情况如下
解释:如果有一边为0了,且另外一边不为0,如果A面对的是这种情况,那么A必胜
Q:如果两边都是0呢?
A:那么在A的上一轮,B做选择的时候,ta就可以抓住A了,所以双边0不行
根据A面对的这种必胜情况,我们以左右为01的情况,来反推,上一轮A面对的是什么
综合A面临的4种情况
A A A A
2 1 1 2 1 2 0 3
B B B B
我们会发现 两边的鲜花数差的绝对值是奇数
而观察B面对的情况
A A
1 1 0 2
B B
我们会发现 两边的鲜花数差的绝对值是偶数
难道先手面对绝对差值为奇数的情况必胜,偶数情况必败?
我们来推算一下,A先手面对绝对差值为偶数的情况
好的基本得出结论 如果先手面对的是绝对差值为奇数的情况,那么就是必胜的,反之必败
如此就转换成了 [1,n]与[1,m]可以组成多少个不重复的,绝对差值为奇数的数对
直接分类讨论n>m时
对于x(1<=x<=n) [1,m]有多少数可以组对
若x为奇数 所有的偶数可以与x组对
若x为偶数 所有的奇数可以与y组对
直接for循环累加就行了
class Solution {
public:
typedef long long ll;
ll query(int a,int b){//查询1~b 有几个abs(a-b)%2==1的数对
if (a%2==0) {//若a为偶数 就是查询 1~b有几个奇数
return (b+1)/2;
}
else {//若a为奇数 就是查询1~b有几个偶数
return b/2;
}
}
long long flowerGame(int n, int m) {
ll ans=0;
if (n<m) {
for (int i=1;i<=n;i++) {
ans+=query(i,m);
}
}
else {
for (int i=1;i<=m;i++) {
ans+=query(i,n);
}
}
//只要两边差值为奇数就必胜
return ans;
}
};