noi.ac775题解
Gameb
文件 OI : gameb
时限 : 1000ms
空间 : 512MiB
Alice 和 Bob 正在玩一个游戏。
具体来说，这个游戏是这样的，给定一个数列，从 Alice 开始，两个人轮流操作，每次操作可以从数列的头部或者尾部删去一个数字，当这个数列满足一定条件的时候，最后一次操作的人获胜。如果一开始就满足条件，则认为 Bob 获胜。
条件有的时候是单调不下降有的时候是单调，这会变化。
现在有一个长度为 \(n\) 的数列，两个人在上面玩了 \(m\) 次游戏，每次他们选定一个区间 \(l,r\) 作为游戏的场地。他们想知道如果两个人都采用最优策略，那么谁会获得胜利。
输入格式
第一行两个整数，第一个整数 \(n\) 表示序列的长度，第二个整数 \(type\)，如果为 \(1\) 则表示胜利条件是单调不下降，如果为 \(2\) 则是单调。
接下来一行 \(n\) 个整数，第 \(i\) 个整数表示 \(a_i\)。
接下来一个整数 \(m\)，表示游戏次数。
接下来 \(m\) 行，每行两个整数 \(l_i,r_i\) 表示区间。
输出格式
一共 \(m\) 行，每行一个字符串，如果 Alice 必胜则输出“Alice”，否则输出“Bob”。
样例数据
输入样例一
4 2 1 5 3 4 3 1 2 1 3 1 4输出样例一
Bob Alice Bob数据规模与约定
本题采用捆绑测试
对于 20 分的数据，\(n,m\le 5\)；
对于 40 分的数据，\(n,m\le 1000\)；
对于另外 30 分的数据，\(type=1\);
对于所有数据，满足 \(3\le n,m≤10^6,0≤a_i≤10^9,1≤l_i≤r_i≤n\)。
时间限制：\(1s\)
空间限制：512MB
正解
首先求一下每个点出发的单调序列长度
for(int i=n,p=n;i;i--){
if(st[i+1]<st[i]) p=i;
b[i]=p;
}
if(ty==2){for(int i=n,p=n;i;i--){
if(st[i+1]>st[i]) p=i;
b[i]=max(b[i],p);
}}
我们把一个游戏看成在二维平面上玩，一开始在\((0,0)\)
每次删掉开头，我们认为是从\((x,y)\)走到\((x+1,y)\)，删掉尾部是从 \((x,y)\)
走到\((x,y+ 1)\)。
那么假如左边删个，右边删\(y\)个，那么\(SG(x,y)=0\)，我们称之为终止态，那么和终止态相邻且不
为终止态的点\(SG = 1\)，称其为边界态。
不难发现对于一个\(x\)，终止态只有一个，而且随着\(x\)增大\(y\)是单调不降的，每次向上向右走
还有两个小结论:
-
假设\((x + 1,y+ 1)\)必败，那么\((x,y)\)必败
-
假设\((x + 1,y+ 1)\),\((x + 2,y+ 2)\)都必胜，那么\((x,y)\)必胜
考虑第二个结论的证明
这里的\((x + 2,y + 2)\)必胜是保证\((x,y+ 2)\),\((x + 1,y+ 2)\),\((x+2,y+ 1)\),\((x +2,y)\)均不为终止态。
因为\((x + 1,y+ 1)\)必胜则\((x + 2,y+ 1)\),\((x +1,y+2)\)中有一个必败。假设是\((x+1,y+1)\)必败，那么\((x+ 2,y)\)必胜，又因为\((x + 1,y+ 1)\)必胜，那么\((x + 1,y)\)必败，那么\((x,y)\)就必胜了。
另一种假设同理。
这里再加入另一种解释方式：
我们考虑现实博弈情景
设区间 \([l,r]\) 中的最长单调段的长度为 \(len\)。
\(len=r−l+1\)，即 \([ l , r ]\) 本身是单调段，先手必败；
\(len=r−l\)，根据上条可得这种情况先手必胜；
\(len=r−l−1\)，这里又分为 \([ l , r − 2 ]\) 是单调段、\([ l + 1 , r − 1 ]\) 是单调段、\([ l + 2 , r ]\) 是单调段三种情况:
- 若 \([ l , r − 2 ]\)是单调段，那么正常情况下大家都不会拿最后一个,不然对面再拿掉倒数第二个就 gg ，因此都是从左往右拿，直到剩下的是个单调段为止。那么就可以预处理 \(L_i\)
表示以 \(i\) 为右端点的最长单调段到哪，这样就可以算出步数，根据奇偶性算出先手的胜负；
tips: \(1,2,3,4,4,4,2,3\)，当拿剩\(4,4,4,2,3\) 的时候，先手直接拿掉最后一个，获胜
\([ l + 2 , r ]\) 是单调段的情况同理；
若 \([ l + 1 , r − 1 ]\) 是单调段，先手后手一前一后完事，先手必败。
所以问题等价于询问从(0,0)开始，一路向右上走到最大点的那个点的状态。
那么考虑\((0,0),(1,1),...,(m,m)\)这条对角线上(\((m,m)\)是终止态或者边界态)，那么只有三种
可能:
- 全为必胜;
- 全为必败;
- (m,m)为边界态必胜，其余必败。
那我们只要预处理\(b_1\)表示左端点为\(i\)，最长的单调区间的右端点的位置(也就是终止态)(也就是\(i\)开始向右延伸最长多长是合法的)
\(c_i = max(b_{i+1},b_i+1)\)也就是边界态。
询问那个的状态，只要看从那个点走到边界态的奇偶性就行了，注意不能看走到终止态的奇偶性
就不难二分出m。
如何二分？？？假如(m,m)是终止态就是情况2，否则双方要么一直删左边，要么一直删右边，只要再二分一下两种情况走到边界态的长度，然后判一下奇偶性(全奇必败，有偶必胜)即可。
while(L<R){
int len=(L+R)>>1;
if(c[l+len]>=r-len) R=len;
else L=len+1;
}
l+=L-1;r-=L-1;
L=0;R=r-l+1;
while(L<R){
int len=(L+R)>>1;
if(c[l+len]>=r) R=len;
else L=len+1;
}
u=L;
L=0;R=r-l+1;
while(L<R){
int len=(L+R)>>1;
if(c[l]>=r-len) R=len;
else L=len+1;
}
正解二
另一种解法（没想到吧）：
考虑\(sg\)函数的动态规划转移
设\(f[l][r]\)为区间\(l,r\)中是否先手必胜
那么我们很容易推出这个逻辑式：\(f[l][r]=\lnot f[l][r-1] \lor \lnot f[l+1][r]\)
那么我们再把这段抠过来：
设区间 \([l,r]\) 中的最长单调段的长度为 \(len\)。
\(len=r−l+1\)，即 \([ l , r ]\) 本身是单调段，先手必败；
\(len=r−l\)，根据上条可得这种情况先手必胜；
\(len=r−l−1\)，这里又.......(自己上去看)
所以我们列出了这个暴力的转移式：
那么， \(f [l + 1][r − 1] = 0\) 也就是 \(f [l ][ r] = 0\)
若 \(f[l + 1][r − 1] = 1\)，则一定有 \(f [l + 1][r − 2] = 0\)或 $f[l + 2] [r − 1] = 0 $，
这两个东西非常amzing啊，前者会导致 $f[l][r − 2] = 1 $ ，后者会导致$ f [l + 2 ][r ]= 1$
两者代入转移式都会使 \(f [l][r] = 1\) 因此 $ f[l][r]=f[l+1][r-1] $
那么这玩意和上面格路转移有什么区别？？？
所以我们考虑将这个询问序列向内缩
求出\(mid=(l+r)/2\)所在的一个单调区间，这既是答案
全部代码
TAGS
#include
// #include"../need.cpp"
using namespace std;
// #define int long long
#define itn int
constexpr int oo = 2000006;
int n,c,st[oo];
pair sp[oo],seg[oo];
int cnt,sum;
itn sr[oo],nr[oo],nl[oo];
int tmp[oo],m;
bool cmp(const pair &a,const pair &b){return a.firstb.second;}
int t;
main(void){
// fre();
freopen("gameb.in","r",stdin);
freopen("gameb.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> c;
for(int i=1;i<=n;i++) cin >> st[i];
if (c==1){
for(int i=n,p=n;i;i--){
if(st[i+1]> m;
int l,r;
itn ll,rr,u,v;
while(m--){
cin >> l >> r;
ll=0; rr=(r-l+1)/2;
if(sr[l]>=r){puts("liulei");continue;}
if(tmp[l]>=r){puts("se");continue;}
while(ll>1;
if(tmp[l+mid]>=r-mid) rr=mid;
else ll=mid+1;
}
l+=ll-1;r-=ll-1;
ll=0;rr=r-l+1;
while(ll>1;
if(tmp[l+mid]>=r) rr=mid;
else ll=mid+1;
}
u=ll;
ll=0;rr=r-l+1;
while(ll>1;
if(tmp[l]>=r-mid) rr=mid;
else ll=mid+1;
}
v=ll;
if((u&1)&&(v&1)) puts("liulei");
else puts("se");
}
exit(0);
}
else {
int last=1;
for(int i=2;i<=n;i++) if(st[i-1]>st[i]){
sp[++cnt]=make_pair(last,i-1);
last=i;
}
sp[++cnt]=make_pair(last,n);
last=1;
for(int i=2;i<=n;i++) if (st[i-1]seg[sum].second){
for(int j=last;j<=sp[i].first-1;j++)
nr[j]=seg[sum].second;
last=sp[i].first;
seg[++sum]=sp[i];
sr[sum]=sp[i].second;
}
for(int j=last;j<=n;j++) nr[j]=n;
for(int i=n,j=sum;i>=1;i--){
if (j&&i==seg[j-1].second) j--;
nl[i]=seg[j].first;
}
cin >> t;
while (t--){
int l,r,mid;
cin >> l >> r;
mid=(l+r)>>1;
int ll,rr,x=lower_bound(sr+1,sr+1+sum,(l+r+1)>>1)-sr;
int even=!((r-l+1)&1);
int t=min(mid-seg[x].first+even,seg[x].second-mid);
if (x+1<=sum&&seg[x+1].first<=mid)
t=max(t,min(mid-seg[x+1].first+even,seg[x+1].second-mid));
t=min(t,min(mid-l+even,r-mid));
ll=mid-t+even; rr=mid+t;
while (l=rr-1||nr[ll+1]>=rr+1)) ll--,rr++;
if (nr[ll]>=rr)
puts("liulei");
else if (nr[ll]==rr-1||nr[ll+1]>=rr)
puts("se");
else if (nr[ll]==rr-2)
puts(((rr-ll+1-(rr-nl[rr-1])-(nr[rr-2]>rr-1))&1)?"se":"liulei");
else if (nr[ll+2]>=rr)
puts(((rr-ll+1-(nr[ll+1]-ll)-(nr[ll]>ll+1))&1)?"se":"liulei");
else if (nr[ll+1]==rr-1)
puts("liulei");
else assert(0);
}
exit (0);
}
}
别看我这坨带便了好不好）