• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces 1369F. BareLee 题解

开发技术 开发技术 2周前 (04-29) 8次浏览

Codeforc++es 1369F. BareLee

Link!

题意

一盘博弈由若干小游戏组成。

每局小游戏包含两个正整数(s,e(s <= e)),每次操作可以将(s)变成(2s)(s+1),第一个把(s)变成大于(e)的人输。

每局游戏的输者在下一轮执先手,博弈的胜利由最后一盘小游戏的胜利决定,问你在第一局执先手的情况下,能否有必胜/必败策略。

我们先考虑小游戏的胜负:

(win(e,s))表示能否先手获胜。

如果(e)是奇数且(s)是奇数,那么先手必败,偶数反之。

证明如下:考虑最后的必败的状态一定有(s = e)时,此时无论怎么操作都会(s)大于(e)

无论先手怎么操作,后手都进行(+1)操作,发现先手操作时,(s)永远是奇数,因为(e)是奇数,所以先手必败。

如果(e)是偶数,当(e/2 < s <= e)时,只能执行(+1)操作,所以(win(e,s) = (e-s)mod{2})

(e/4 < s <= e/2)时,先手必胜。

证明如下:先手进行一次(*2)操作,此时答案为(!win(e,2s) (e/2 < 2s <= e)),此时就变回到上一种情况,因为(2s,e)都是偶数,所以(win(e,2s) = 0)

(s <= e/4)时,答案为(win(e/4,s))。原因是先操作使得(e/4 < s <= e/2)的人必输。

(lose(e,s))表示能否先手失败。

如果(2s > e),显然一次(*2)操作就可以输掉。

否则(lose(e,s) = win(e/2,s)),证明显然。

求出每一局小游戏后,可以倒着逆推求解,复杂度(O(n+logV)),(V)是值域。

#include<bits/stdc++.h>
#define int long long
#define N 1000015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
using namespace std;
int win(int e,int s){
	if(s == e) return 0;
	if(s+1 == e) return 1;
	if(e&1) return !(s&1);
	if(s <= e/4) return win(e/4,s);
	if(s <= e/2) return 1;
	return (e-s)&1;
}
int lose(int e,int s){
	if((s<<1) > e) return 1;
	return win(e/2,s);
}
int n,a,b,w[N],l[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld",&n);
	rep(i,1,n) {
		scanf("%lld%lld",&a,&b);
		w[i] = win(b,a); l[i] = lose(b,a);
	}
	a = w[n];
	per(i,1,n-1){
		if(a) {if(!l[i]) a ^= 1;}
		else if(w[i]) a ^= 1;
	}
	printf("%lld ",a);
	a = l[n];
	per(i,1,n-1){
		if(a){if(!l[i]) a ^= 1;}
		else if(w[i]) a ^= 1;
	}
	printf("%lldn",a);
	return 0;
}

程序员灯塔
转载请注明原文链接:Codeforces 1369F. BareLee 题解
喜欢 (0)