我比赛的时候怕不是在睡觉啊……

\(A\ Darker\ and\ Darker\)

我是不是想得太复杂了……根本没必要像我这样做吧……

首先问题可以转化成令\(p_{i,j}\)表示到\((i,j)\)这个白点最近的的黑点的距离，求\(\max\{p_{i,j}\}\)。而答案显然是可以二分的

对于某一个白点，我们怎么判断到它的距离不超过\(mid\)的范围内是否有黑点呢？这里的距离是曼哈顿距离，非常麻烦，我们坐标系变换一下把它转成一个切比雪夫距离，那么到它的距离不超过\(mid\)的范围就可以化成一个矩形了，预处理矩形的前缀和减一减就可以了

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=4005,M=1000;char s[N][N];int n,m,l,r,ans,mid,mp[N][N];inline int calc(R int x,R int y){    R int dx=x,dy=y,xx,yy;x=dx+dy+M,y=dx-dy+M;    dx=x+mid,dy=y+mid,xx=x-mid,yy=y-mid;    xx=max(xx,2+M),yy=max(yy,1-m+M),dx=min(dx,n+m+M),dy=min(dy,n-1+M);//  puts("qwq");//  printf("%d %d %d %d %d %d\n",x-M,y-M,xx-M,yy-M,dx-M,dy-M);    return mp[dx][dy]-mp[dx][yy-1]-mp[xx-1][dy]+mp[xx-1][yy-1];}bool ck(){    fp(i,1,n)fp(j,1,m)if(s[i][j]=='.'&&!calc(i,j))return false;    return true;}int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d",&n,&m),l=0,r=n+m,ans=0;    fp(i,1,n)scanf("%s",s[i]+1);    fp(i,1,n)fp(j,1,m)mp[i+j+M][i-j+M]=(s[i][j]=='#');    fp(i,2+M,n+m+M)fp(j,1-m+M,n-1+M)mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];//  mid=1,printf("%d\n",ck());    while(l<=r){        mid=(l+r)>>1;        ck()?(ans=mid,r=mid-1):l=mid+1;    }    printf("%d\n",ans);    return 0;}
        
       
      
     
    

\(B\ LRUD\ Game\)

发现左右的移动和上下的移动没有关系，那么我们分开考虑，以左右为例，上下同理

我们枚举是从左边出边界还是右边出边界，如果是左边出边界，那么一个人只会选\(L\)，另一个人只会选\(R\)，注意选\(R\)的那个人别自己\(R\)出边界。右边出边界同理

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'Z'||ch<'A'));    for(s[++len]=ch;(ch=getc())>='A'&&ch<='Z';s[++len]=ch);    return s[len+1]='\0',len;}const int N=2e5+5;char s[N],t[N];int n,m,len,sx,sy;bool calc(int n,int x,char a,char b){    int p=x;    fp(i,1,len){        if(s[i]==b)++p;if(p>n)return false;        if(t[i]==a)p=max(p-1,1);    }    p=x;    fp(i,1,len){        if(s[i]==a)--p;if(p<1)return false;        if(t[i]==b)p=min(p+1,n);    }    return true;}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read(),len=read(),sx=read(),sy=read(),read(s),read(t);    puts(calc(n,sx,'U','D')&&calc(m,sy,'L','R')?"YES":"NO");    return 0;}
        
       
      
     
    

\(C\ moving\ coins\)

我们考虑一次以\(u\)为根的操作，树上的所有节点中有且只有叶子节点会变得不再有硬币，而且发现此后它们再也不会有硬币，我们可以简单地认为所有叶子节点都被删除了

那么问题转化为每次选定一个根并删掉所有叶子，删完整棵树的人赢

我们考虑这棵树的直径\(L\)，假设\(L>2\)，根据定理，如果\(L\)为奇数那么所有直径过同一个点，如果\(L\)为偶数所有直径过同一条边，那么我们肯定能找到一个点，使得选其为根操作之后\(L-=2\)。而如果我们选在其中一条直径的一个叶子端点上，那么\(L-=1\)

而对于\(L=1\)的情况先手必胜，\(L=2\)的情况先手必败

于是问题可以转化为每次可以令\(L\)减一或减二，先让它减到\(2\)的赢

这应该是个比较经典的模型了，大家小时候应该都玩过，如果\(L\equiv 2\pmod{3}\)的时候后手胜，否则先手胜

于是求个直径就行了

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=2e5+5;struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int mx[N],n,res;void dfs(int u,int fa){    mx[u]=1;    go(u)if(v!=fa)dfs(v,u),cmax(res,mx[v]+mx[u]),cmax(mx[u],mx[v]+1);    cmax(res,mx[u]);}int main(){//  freopen("testdata.in","r",stdin);    n=read();    for(R int i=1,u,v;i
        
       
      
     
    

\(D\ Complexity\)

首先有一个结论，\(A_{ij}\)是\(O(\log(H+W))\)级别的。因为我们横竖对半分之后一定能把它分成只有一个格子的情况

那么我们只要模拟一下就行了，枚举\(A_{ij}\)，并算出\(fl_{i,j,k}\)表示对于\((i,j)\)为右上角，\((k,j)\)为右下角的矩形此时横向的长度最大是多少，以及\(fu_{i,j,k}\)表示以\((i,j)\)为左下角，\((i,k)\)为右下角的矩形此时纵向的长度最大为多少。只要某一个时刻整个矩形都被包括了那么就输出答案

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=205;int fl[N][N][N],fu[N][N][N],gl[N][N][N],gu[N][N][N];char mp[N][N];int L[N][N],U[N][N],n,m;int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d",&n,&m);    fp(i,1,n){        scanf("%s",mp[i]+1);        fp(j,1,m){            L[i][j]=(mp[i][j]==mp[i][j-1])?L[i][j-1]+1:1;            U[i][j]=(mp[i][j]==mp[i-1][j])?U[i-1][j]+1:1;        }    }    fp(x,1,n)fp(y,1,m){        for(R int xx=x,mn=233;mp[x][y]==mp[xx][y];++xx)cmin(mn,L[xx][y]),fl[x][y][xx]=mn;        for(R int yy=y,mn=233;mp[x][y]==mp[x][yy];++yy)cmin(mn,U[x][yy]),fu[x][y][yy]=mn;    }    for(int res=0;233;++res){        if(fl[1][m][n]==m||fu[n][1][m]==n)return printf("%d\n",res),0;        memcpy(gl,fl,sizeof(fl)),memcpy(gu,fu,sizeof(fu));        fp(x,1,n)fp(y,1,m){            fp(xx,x,n)fl[x][y][xx]+=gl[x][y-gl[x][y][xx]][xx];            fp(yy,y,m)fu[x][y][yy]+=gu[x-gu[x][y][yy]][y][yy];        }        fp(x,1,n)fp(y,1,m){            for(R int xx=x,X=1;xx<=n;++xx,++X)                for(R int yy=y-fl[x][y][xx]+1;yy<=y&&fu[xx][yy][y]
        
       
      
     
    

\(E\ Go\ around\ a\ Circle\)

完了数数都数不来了……

我们分情况考虑，如果全都是同一种颜色，假设全都为\(R\)，那么连续两段蓝色的圆弧肯定不合法，问题转化为一个长度为\(n\)的序列，不允许有两个相邻的蓝色，首尾也不许同时蓝色的方案数。记一下\(dp_{0,1,2,3}\)分别表示开始是否为蓝色，当前最后一个是否为蓝色的方案数，转移显然

如果不是同一种颜色，假设开头的颜色为\(R\)，那么依然不允许存在两端相邻蓝色圆弧。然后还有两个结论

• 整个序列一定是由若干段组成的，其中每一段都形如连续奇数个红色+一个蓝色

• 每一段序列的长度都有一个限制，不能超过\(L\)

先考虑第一个结论，如果连续红色的个数为偶数，我们不妨设序列最前面有连续\(k\)个\(R\)，如果\(k\)是奇数，把起始点设为这段红色的结尾就\(gg\)，如果\(k\)是偶数，把起始点设为这段红色结尾前一个依然\(gg\)，所以只有红色个数是奇数合法

第二个结论，对于开头的连续\(k\)个\(R\)，如果\(k\)是偶数，则最多只能放连续\(k+1\)个红色，如果\(k\)是奇数则最多只能放连续\(k\)个。如果这\(k\)个连续\(R\)不在开头，那么它们前面是一个\(B\)，也就是说我们现在在一段红色的一个端点处。如果\(k\)是偶数，显然可以走回来，如果\(k\)是奇数，那么这段连续红色的个数不能超过\(k\)。

那么我们预处理出\(dp_i\)表示长度为\(i\)的序列的合法方案数，发现奇数的位置肯定全都是红色，所以我们只要考虑偶数位置怎么放就行了，转移也比较显然

最后是旋转导致的多种方案数，我们枚举第一个蓝色和最后一个蓝色之间的距离，乘上对应的系数就好了

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=2e5+5,P=1e9+7;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}char s[N];int f[N],dp[2][5],n,m,res,t;void solve1(){    dp[0][0]=dp[0][3]=1,t=0;    for(R int i=1;i
         
          =lim+2)f[i]=dec(f[i],f[i-(lim+2)]); } res=0; for(R int i=2;i<=lim;i+=2)upd(res,mul(f[n-i],i)); printf("%d\n",res);}int main(){// freopen("testdata.in","r",stdin); scanf("%d%d%s",&n,&m,s+1); if(s[1]=='B')fp(i,1,m)s[i]^='B'^'R'; bool flag=0; fp(i,1,m)if(s[i]=='B'){flag=1;break;} if(!flag)solve1();else solve2(); return 0;}
         
        
       
      
     
    

\(F\)题咕了