BZOJ3497 : Pa2009 Circular Game

摘要:
让第一手是$A$,第二手是$B$。将相同颜色的相邻块组合成一个块。首先,判断一些情况:如果所有的方格都满了,那么很明显,$A$会输。枚举$A$的第一个操作。如果B不能操作,那么$A$将获胜。如果没有自由拦网,显然不会是平局。该游戏相当于尼姆游戏,其中每堆石头的数量是两个相邻区块之间的距离。$AB$无法通过一步操作获得自由区块,但此时尼姆游戏$a$获胜,最终$a$胜出。

令先手为$A$,后手为$B$,将相邻同色棋子合并成块,首先特判一些情况:

  1. 如果所有格子都是满的,那么显然$A$必败。
  2. 否则如果所有块都只有一个棋子,那么显然平局。
  3. 枚举$A$的第一步操作,如果可以使得B无法操作,那么显然$A$必胜。

无视所有大小为$1$的块,考虑剩下块里相邻两块,它们往外扩张比往内缩更优:

  • 如果是形如[A_A]___B__A__BA____B___[AA_A],两边同色,所以中间这些块(包括位置)可以删除,不影响游戏结果。
  • 如果是形如[A_A]___B__A__B_A__[BB_B],两边异色,那么相邻两块相互靠近更优,可以等效替代成[A_A]___[BB][AA]__[BB][AA]__[BB_B]。

经过上述转化后,不再存在大小为$1$的块,当存在大小至少为$3$且内部存在空隙的自由块时,该块显然可以永远操作下去。假设不存在自由块,那么显然不会平局,游戏等价于每堆石子数为相邻两块间距的Nim游戏。

分以下情况讨论:

  1. $A$可以通过至多一步操作得到自由块,且可以阻止$B$得到自由块,此时结果为$A$胜。
  2. $AB$一开始都没有自由块,但都可以通过一步得到,$A$先堵$B$,$B$再堵$A$后双方都没有自由块,但是此时Nim游戏$A$胜,则最终$A$胜。
  3. $AB$都没法通过一步操作得到自由块,但是此时Nim游戏$A$胜,则最终$A$胜。
  4. $A$可以通过至多一步操作得到自由块,但是阻止不了$B$得到自由块,此时结果为平局。
  5. $A$无法得到自由块,也阻止不了$B$得到自由块,此时结果为$B$胜。
  6. 双方都没法得到自由块,但是此时Nim游戏$B$胜,则最终$B$胜。

时间复杂度$O(B+C)$。

#include<cstdio>
#include<cstring>
#define CLR(x) memset(x,0,sizeof x)
const int N=1000010,BUF=12000000;
char Buf[BUF],*buf=Buf;
int Case,m,n,ce,A,B,i,j,k,o,x,st,a[N],b[N],can10,can11,can01,can00;
struct P{
  int x;char col;
  P(){}
  P(int _x,char _col){x=_x,col=_col;}
}q[N];
struct E{
  int len,cnt,dis;char col;
  E(){}
  E(int _len,int _cnt,int _dis,char _col){len=_len,cnt=_cnt,dis=_dis,col=_col;}
  bool free(){return len>cnt&&cnt>=3;}
}e[N];
int cfree[2],cmove[2],cnt[2],cmay[2],sum[2],CFREE,CMAY0,CMAY1;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline void cal(){
  if(e[0].col==e[ce-1].col){
    ce--;
    e[0].len+=e[ce].len+e[ce].dis;
    e[0].cnt+=e[ce].cnt;
  }
  CLR(cfree),CLR(cmove),CLR(cnt),CLR(cmay);CLR(sum);
  for(i=0;i<ce;i++){
    cnt[e[i].col]++;
    if(e[i].free())cfree[e[i].col]++,cmove[e[i].col]++,cmay[e[i].col]++;
    if(e[i].len>e[i].cnt)cmove[e[i].col]++;
    if(e[i].dis){
      cmove[e[i].col]++;
      if(e[i].cnt>=3){
        cmay[e[i].col]++;
        sum[e[i].col]^=e[i].dis;
      }
    }
    if(e[(i-1+ce)%ce].dis){
      cmove[e[i].col]++;
      if(e[i].cnt>=3){
        cmay[e[i].col]++;
        sum[e[i].col]^=e[(i-1+ce)%ce].dis;
      }
    }
  }
}
inline bool can_block_b(){
  if(cfree[1])return 0;
  if(cmove[1]>1)return 0;
  for(i=0;i<ce;i++)if(e[i].col==1&&e[i].len>e[i].cnt)return 0;
  for(i=0;i<ce;i++)if(e[i].col==1){
    if(e[i].dis&&e[(i+1)%ce].len>1)return 1;
    if(e[(i-1+ce)%ce].dis&&e[(i-1+ce)%ce].len>1)return 1;
  }
  return 0;
}
inline void change(int x,int y){
  CFREE=cfree[0],CMAY0=cmay[0],CMAY1=cmay[1];
  if(e[x].cnt>=3)CFREE++,CMAY0++;
  if(e[y].cnt>=3&&!e[y].free())CMAY1--;
}
inline int solve(){
  read(m),read(A),read(B);
  for(i=1;i<=A;i++)read(a[i]);
  for(i=1;i<=B;i++)read(b[i]);
  //Circle is full, so A can't move
  if(A+B==m)return -1;
  n=0;
  i=j=1;
  while(i<=A&&j<=B)if(a[i]<b[j])q[++n]=P(a[i++],0);else q[++n]=P(b[j++],1);
  while(i<=A)q[++n]=P(a[i++],0);
  while(j<=B)q[++n]=P(b[j++],1);
  ce=0;
  for(i=1;i<=n;i=j+1){
    for(j=i;j<n&&q[i].col==q[j+1].col;j++);
    e[ce++]=E(q[j].x-q[i].x+1,j-i+1,q[j+1].x-q[j].x-1,q[i].col);
  }
  e[ce-1].dis=q[1].x-q[n].x-1+m;
  cal();
  //All blocks' length is 1, draw
  for(i=0;i<ce;i++)if(e[i].len!=1)break;
  if(i>=ce)return 0;
  //A can't move
  if(!cmove[0])return -1;
  //A can make B not to move
  if(can_block_b())return 1;
  for(i=0;i<ce;i++)if(e[i].len>1){st=i;break;}
  for(i=0;i<ce;i=j){
    for(j=i+1;j<=ce;j++)if(e[(st+j)%ce].len>1)break;
    int l=(st+i)%ce;
    if(e[l].col!=e[(st+j)%ce].col)for(k=i+1,o=1;k<j;k++,o^=1){
      x=(st+k)%ce;
      if(o)e[x].dis=0;
      e[x].len=e[x].cnt=2;
    }else{
      e[l].len+=e[l].dis;
      e[l].dis=0;
      for(k=i+1,o=1;k<j;k++,o^=1){
        x=(st+k)%ce;
        if(o)cnt[e[x].col]--;
        e[l].len+=e[x].len+e[x].dis;
        e[l].cnt+=e[x].cnt;
      }
    }
  }
  //No such blocks
  if(!cnt[0])return -1;
  if(!cnt[1])return 1;
  for(i=n=0;i<ce;i++)if(e[i].len>1)e[n++]=e[i];
  for(ce=i=1;i<n;i++)if(e[i].col==e[ce-1].col){
    e[ce-1].len+=e[i].len+e[ce-1].dis;
    e[ce-1].cnt+=e[i].cnt;
    e[ce-1].dis=e[i].dis;
  }else e[ce++]=e[i];
  cal();
  //A can't move
  if(!cmove[0])return -1;
  //A can make B not to move
  if(can_block_b())return 1;
  can10=can11=can01=can00=0;
  CFREE=cfree[0],CMAY0=cmay[0],CMAY1=cmay[1];
  if(CFREE){
    if(!CMAY1)can10=1;
    if(cfree[1])can11=1;
  }
  for(x=i=0;i<ce;i++)x^=e[i].dis;
  for(i=0;i<ce;i++)if(e[i].col==0){
    if(e[i].dis){
      change(i,(i+1)%ce);
      if((CMAY0>1||CFREE)&&!CMAY1)can10=1;
      if(CFREE&&CMAY1)can11=1;
      if(!CFREE&&CMAY1)can01=1;
      if(!CMAY1&&x==e[i].dis)can00=1;
      if(!CFREE&&CMAY0==1&&!CMAY1)if(x^e[i].dis^sum[0])can00=1;
    }
    if(e[(i-1+ce)%ce].dis){
      change(i,(i-1+ce)%ce);
      if((CMAY0>1||CFREE)&&!CMAY1)can10=1;
      if(CFREE&&CMAY1)can11=1;
      if(!CFREE&&CMAY1)can01=1;
      if(!CMAY1&&x==e[(i-1+ce)%ce].dis)can00=1;
      if(!CFREE&&CMAY0==1&&!CMAY1)if(x^e[(i-1+ce)%ce].dis^sum[0])can00=1;
    }
  }
  if(can10)return 1;
  if(can00)return 1;
  if(can11)return 0;
  if(can01)return -1;
  return x?1:-1;
}
int main(){
  fread(Buf,1,BUF,stdin);read(Case);
  while(Case--){
    int x=solve();
    if(x>0)puts("B");
    if(!x)puts("R");
    if(x<0)puts("C");
  }
  return 0;
}

  

免责声明:文章转载自《BZOJ3497 : Pa2009 Circular Game》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇微信小程序:wx.request之post请求后端无法获取数据的问题AFN和MBProgressHUD组合封装下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

jenkins 配置 ssh连接远程服务器并执行相关命令

5、配置完成后,点击TestConfiguration返回Success即证明Jenkins所在宿主机可以正常链接到待部署机。...

PLSQL常用配置之窗口/版面保存、SQL格式化/美化、SQL注释去掉注释等快捷键配置、登陆历史修改配置

//Blog.csdn.net/eyeidolon/article/details/8251791 PLSQL常用配置的快捷键配置,如窗口/布局保存、SQL格式化/美化和SQL注释删除,以及登录历史修改1的配置。PL/SQLDeveloper记住登录密码当使用PL/SQLDeveloper时,默认情况下PL/SQLDeveloper会执行此窗口中的所有SQL...

USBWriter之后恢复磁盘大小

USBWriter之后恢复磁盘大小的方法:1,cmd2,diskpart3,listdisk4,selectdisk*5,clean6、在我的电脑点右键,管理,然后选磁盘管理,选择USB后,右键,然后再新建卷就可以了。...

MySQL学习笔记:字符串前后补全0

遇到一个要求:如果位数小于6,则需要使用函数LPAD()和RPAD()自动完成6位。LPAD使用字符串padstr填充并完成左侧的str,直到其长度达到len个字符,并返回str。...

mac格式化重装系统

4.选择“重新安装MacOS”5.按照以下步骤中的提示进行操作。安装需要半个多小时。在此期间无法断开网络,否则需要重新安装...

应用程序-特定 权限设置并未向在应用程序容器 不可用 SID (不可用)中运行的地址 LocalHost (使用 LRPC) 中的用户 NT AUTHORITYSYSTEM SID (S-1-5-18)授予针对 CLSID 为 {D63B10C5-BB46-4990-A94F-E40B9D520

此安全权限可以使用组件服务管理工具进行修改。根据APPID为{9CA88EE3-ACB7-47C8-AFC4-AB702511C276}在注册表中找到HKEY_CLASSES_ROOTAppID{9CA88EE3-ACB7-47c8-AFC4-AB702511C276}右键选择权限:加入SYSTEM用户并赋予完全控制权限:如果在注册表中没有权限添加用户,则需...