正题

题目链接:https://www.luogu.com.cn/problem/CF1369F

---

题目大意

$T$次游戏，每次给出一个$s$和$t$，两个人轮流操作，可以让$s=s+1$或者$s=s\times 2$，如果$s>t$的话那个人就输了。

每次输的人将作为下一次的先手，最后一把决定胜负。

求第一次先手的人是否有必胜/必败策略。

$1\le s\le t\le 10^{18},1\le T\le 10^5$

---

解题思路

先考虑一把里面是否有必胜策略，考虑用$SG$函数去求，因为我们只需要维护$SG$为$0$和不为$0$的信息就好了。

如果一个状态不能走到任何$0$状态那么这个节点就是$0$状态，为了方便，后面的$SG=2$都视为$SG=1$。

首先$\lfloor \frac{t}{2}\rfloor +1\sim t$这个范围中因为$\times 2$用不了，所以这个范围肯定是$01$交错的。

然后考虑从$\frac{t}{2}$开始往前每个状态都会额外指向一个乘二后的值，如果也就是前面$01$交错中每次跳两个，所以要么指向的都是$0$要么指向的都是$1$，如果指向的都是$0$，那么后面就有一段都是$1$，否则如果指向的是$1$显然不会产生影响，依旧是$01$交错。

然后让$t$继续除二，然后考虑如果后面是连续$1$段我们不需要考虑任何东西，如果后面是$01$交错就继续按照前面的做，直到到这段包括$s$我们就可以得到$s$的$SG$值了。

然后考虑必败，最后一步肯定是$\times 2$，所以我们直接让$t=\lfloor \frac{t}{2}\rfloor$，然后看是否必胜，这就是能否必败的答案了。

然后反过来$dp$一次就可以得到答案了。

时间复杂度：$O(T\log t)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,p[N][2],f[N][2]; bool check(ll s,ll t){bool now=0,k=0;ll r=t;while(t/2>=s){if(now)now=0,r=t/2;else now=k^!(t&1);t/=2;k=(r-t)&1;}return now|((r-s)&1); } signed main() {scanf("%lld",&n);for(ll i=1,s,t;i<=n;i++){scanf("%lld%lld",&s,&t);p[i][0]=check(s,t);if(t/2>=s)p[i][1]=check(s,t/2);else p[i][1]=1;}f[n][0]=p[n][0];f[n][1]=p[n][1];for(ll i=n-1;i>=1;i--){f[i][0]=(f[i+1][0]&p[i][1])|((!f[i+1][0])&p[i][0]);f[i][1]=(f[i+1][1]&p[i][1])|((!f[i+1][1])&p[i][0]);}printf("%lld %lld\n",f[1][0],f[1][1]);return 0; }

总结

以上是生活随笔为你收集整理的CF1369F-BareLee【博弈论,SG函数】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。