CF1369F题解
FiraCode
·
·
题解
题解思路：
我们有 T 轮，只有最后一轮赢了才是赢了，所以前 T - 1 轮，随便就可以了。
状态：
必胜态：上一轮一定要输
必败态：上一轮一定要赢
所以我们知道了 i - 1 的状态，那么我们就可以求出第 i 轮的状态。
那么我们只要维护一个赢得状态值和输的状态值就可以得到结果。
难点就在他们怎么计算：
------------Win 数组分割线------------
那么我们就可以通过 $Win_{e,e}$ 求出 $Win_{e-1,e}$ 等。
若 e 是奇数：
Win_{e,e} = 0
$Win_{e - 2 , e} = 0$因为他是一个奇数，而奇数只能转移到必胜态，因为两个奇数相加，得偶数；奇数加一，就相当于奇数加奇数。所以只会转移到必胜态，所以他就是必败态。
$$\vdots$$
$$\vdots$$
以此类推
若 $e$ 是偶数：
> 当 $s$ 是偶数，那么 $s \times 2$ 就是必败态，所以当 $\left \lfloor \frac{e}{4} \right \rfloor < s \le \left \lfloor \frac{e}{2} \right \rfloor$，$s \times 2$ 一定是必胜态。
> 当在 $\left \lfloor \frac{e}{4} \right \rfloor$ 这个点时，他一定是必败态，因为他乘二，就会到 $s$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$，所以一定必败。
那么我们就可以递归去判断： $dfs (s , \frac{e}{4})$。
因为 $\left \lfloor \frac{e}{4} \right \rfloor$ 乘二到这个区间，而比他小的一定超不过这个区间，所以若能到必胜态区间 $\left \lfloor \frac{e}{4} \right \rfloor - 1$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$ 这个区间的数，必定是必败态，当我们可以转到 $\frac{e}{2}$ 就是必胜态。
这就是 $Win$ 数组的求法。
------------$Lost$ 数组分割线------------
也可以类似的分析一下：
> $\left \lfloor \frac{e}{2} \right \rfloor < s \le e $ 时，他一定是必胜态，那么对于 $\frac{e}{2}$ 一定是必败态，这就很像我们分析 $Win$ 时 $e$ 是偶数的情况，我们就可以直接让他转移到 $Win$ 的情况就可以了。
这样，Win 和 Lost 数组就都求出来了。
虽然我们前面说过要到着来，但是我们正着来就行了，那么当我们这一轮为先手，那么 Win 和 Lost 只有一个为 $1$，那么它就不能改变结果，若 Win 和 Lost 都是 $1$ 那么想输想赢都可以，这样最后的就可以知道了。
**注意：$1 \le s_i,e_i \le 10^{18}$，要开 long long！**
## AC CODE:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
bool dfs (ll s , ll e) {
if (e & 1) {//奇偶性是否相同
if (s & 1) return false;
else return true;
}
if (s > e / 2) {
if (s & 1) return true;
else return false;
}
if (s > e / 4) return true;//当他大于e/4时，和偶数为必胜态区间范围，所以返回true
return dfs (s , e >> 2);//递归
}
bool check (ll s , ll e) {
if (s > e / 2) return true;//奇数里这个区间为必胜态
return dfs (s , e >> 1);//否则返回和Win的共同部分
}
int main() {
int n;
cin >> n;
bool cur = false , win , lose;
for (int i = 0; i < n; ++ i) {
ll s , e;
cin >> s >> e;
win = dfs (s , e);//Win
lose = check (s , e);//Lost
win ^= cur;//和是否先手异或一下
lose ^= cur;
if (win == lose) break;//若Lost和Win一样 ，break
if (win) cur = 1;//若这一局你赢了，那么下一局你先手
else cur = 0;//否则就是后手
}
cout << win << ' ' << lose << endl;
return 0;
}
```
码字不易，求赞！