【XSY3949】取石子遊戲（博弈，線段樹）

題面

取石子遊戲

題解

我們把一個有 n n n 個石子， Alice 每次能拿 a a a 個， Bob 每次能拿 b b b 個的堆稱為狀态 ( n , a , b ) (n,a,b) (n,a,b)。石子數太大的時候不利于分析，嘗試簡化一下：

可以證明狀态 ( n , a , b ) (n,a,b) (n,a,b) 的結果同 ( n   m o d   ( a + b ) , a , b ) (n\bmod (a+b),a,b) (nmod(a+b),a,b) 狀态的結果相同。

是以我們隻需對每一個 n ← n   m o d   ( a + b ) n\gets n\bmod(a+b) n←nmod(a+b)，然後隻考慮 n < a + b n<a+b n<a+b 的情況。

注意兩人此時的步數是相同的，是以他們各自的最優政策是最大化“他們自己接下來走的步數-另一個人接下來走的步數”，不妨設這個值對于兩人而言是 s a , s b s_a,s_b sa​,sb​。

對于每個堆分類讨論：

• 若 n < a , b n<a,b n<a,b，那麼兩人都不能取這個堆，直接扔掉。
• 若 a ≤ n < b a\leq n<b a≤n<b 或 b ≤ n < a b\leq n<a b≤n<a。不妨是 a ≤ n < b a\leq n<b a≤n<b（ b ≤ n < a b\leq n<a b≤n<a 的情況同理），此時這一堆隻有 Alice 可以取，那麼直接對 s a s_a sa​ 貢獻 ⌊ n a ⌋ \left\lfloor\dfrac{n}{a}\right\rfloor ⌊an​⌋。

• 若 a , b ≤ n a,b\leq n a,b≤n，注意到 n < a + b n<a+b n<a+b，是以此時隻要有一個人在這個堆裡取了石子，另一個人就不能取了，換言之前者 “占領” 了這堆石子。那麼對于 Alice 來說，如果她 “占領” 了這堆石子，那麼她可以多走 ⌊ n a ⌋ \left\lfloor\dfrac{n}{a}\right\rfloor ⌊an​⌋ 步，Bob 同理。

  可能有人覺得此時 Alice 按 ⌊ n a ⌋ \left\lfloor\dfrac{n}{a}\right\rfloor ⌊an​⌋ 從大到小 “占領”、Bob 按 ⌊ n b ⌋ \left\lfloor\dfrac{n}{b}\right\rfloor ⌊bn​⌋ 從大到小 “占領” 就可以了，但這并不符合最優政策。

  不妨設滿足 a , b ≤ n < a + b a,b\leq n<a+b a,b≤n<a+b 的堆一共有 m m m 堆。對于第 i i i 堆，設如果先手 “占領” 了這堆石子，先手可以多走 A i A_i Ai​ 步，如果對手 “占領” 了這堆石子，對手可以多走 B i B_i Bi​ 步。設 A i A_i Ai​ 的總和為 S A SA SA， B i B_i Bi​ 的總和為 S B SB SB。

  假設先手取的堆的編号為 p 1 , p 2 , ⋯   , p k p_1,p_2,\cdots,p_k p1​,p2​,⋯,pk​，那麼先手和後手的步數差等于：

  D A = A p 1 + ⋯ + A p k − ( B − B p 1 − ⋯ − B p k ) = ( A p 1 + B p 1 ) + ⋯ + ( A p k + B p k ) − S B \begin{aligned} D_A=&A_{p_1}+\cdots+A_{p_k}-(B-B_{p_1}-\cdots-B_{p_k})\\ =&(A_{p_1}+B_{p_1})+\cdots+(A_{p_k}+B_{p_k})-SB \end{aligned} DA​==​Ap1​​+⋯+Apk​​−(B−Bp1​​−⋯−Bpk​​)(Ap1​​+Bp1​​)+⋯+(Apk​​+Bpk​​)−SB​

  那麼後手和先手的步數差也可以同理推出： D B = ( A p 1 + B p 1 ) + ⋯ + ( A p k + B p k ) − S A D_B=(A_{p_1}+B_{p_1})+\cdots+(A_{p_k}+B_{p_k})-SA DB​=(Ap1​​+Bp1​​)+⋯+(Apk​​+Bpk​​)−SA。

  由于雙方都需要優化他們各自的 D D D，而 S A SA SA、 S B SB SB 又是一個定值，是以他們都會按 ( A i + B i ) = ⌊ n a ⌋ + ⌊ n b ⌋ (A_i+B_i)=\left\lfloor\dfrac{n}{a}\right\rfloor+\left\lfloor\dfrac{n}{b}\right\rfloor (Ai​+Bi​)=⌊an​⌋+⌊bn​⌋ 從大到小輪流 “占領”。

  注意占領也是需要步數的，那麼如果 m m m 為奇數，先手會多耗費一步占領。是以為了維護這個東西，不妨把 A i ← A i − 1 A_i\gets A_i-1 Ai​←Ai​−1， B i ← B i − 1 B_i\gets B_i-1 Bi​←Bi​−1。

  至于維護這個東西，先把 ( A i + B i ) (A_i+B_i) (Ai​+Bi​) 離線下來排序再用線段樹即可。

是以三種情況我們都處理完了。

代碼如下：

#include<bits/stdc++.h>

#define N 200010
#define lc (k<<1)
#define rc (k<<1|1)
#define int long long

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,x[N],a[N],b[N];
int suma[N],sumb[N];
int tot,p[N],q[N],rk[N];
int s[N],pa[N],pb[N];
int sum[N<<2][2];
bool size[N<<2];

bool cmp(int a,int b)
{
	return p[a]>p[b];
}

void up(int k)
{
	size[k]=size[lc]^size[rc];
	if(size[lc])
	{
		sum[k][1]=sum[lc][1]+sum[rc][0];
		sum[k][0]=sum[lc][0]+sum[rc][1];
	}
	else
	{
		sum[k][1]=sum[lc][1]+sum[rc][1];
		sum[k][0]=sum[lc][0]+sum[rc][0];		
	}
}

void update(int k,int l,int r,int x,int y)
{
	if(l==r)
	{
		size[k]=1;
		sum[k][1]=y;
		sum[k][0]=0;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(lc,l,mid,x,y);
	else update(rc,mid+1,r,x,y);
	up(k);
}

signed main()
{
//	freopen("ex_C2.in","r",stdin);
//	freopen("ex_C2_my.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		x[i]=read(),a[i]=read(),b[i]=read();
		x[i]%=(a[i]+b[i]);
		suma[i]=suma[i-1],sumb[i]=sumb[i-1];
		s[i]=s[i-1],pa[i]=pa[i-1],pb[i]=pb[i-1];
		if(x[i]<a[i]&&x[i]<b[i]) continue;
		if(x[i]<a[i])
		{
			sumb[i]+=x[i]/b[i];
			continue;
		}
		if(x[i]<b[i])
		{
			suma[i]+=x[i]/a[i];
			continue;
		}
		p[i]=x[i]/a[i]+x[i]/b[i]-2,q[++tot]=i;
		s[i]+=p[i],pa[i]+=x[i]/a[i]-1,pb[i]+=x[i]/b[i]-1;
	}
	sort(q+1,q+tot+1,cmp);
	for(int i=1;i<=tot;i++) rk[q[i]]=i;
	bool tag=0;
	for(int i=1;i<=n;i++)
	{
		if(rk[i]) update(1,1,tot,rk[i],p[i]),tag^=1;
		int fi=sum[1][1];
//		int se=(s[i]-sum[1])/2;
		int tmp=suma[i]-sumb[i]+fi-pb[i];
		bool Af=(tmp>0||(tmp==0&&tag));
		tmp=sumb[i]-suma[i]+fi-pa[i];
		bool As=(tmp<0||(tmp==0&&(!tag)));
		if(Af&&As) puts("Alice");
		else if((!Af)&&(!As)) puts("Bob");
		else if(Af) puts("First");
		else if(As) puts("Second");
	}
	return 0;
}
/*
4
3 2 4
4 5 2
1 1 2
5 3 4
*/