D.OR
题目链接
简要题解
仔细观察可以发现
\[c_i-b_i=(a_{i-1}+a_i)-(a_{i-1}|a_i)=a_{i-1} \& a_i \]那么我们令\(d_i=c_i-b_i=a_{i-1}\&a_i\)，再令\(e_i=d_i\bigoplus b_i=a_{i-1}\bigoplus a_i\)。
这时我们对限制进行了转换，所有限制都成了位运算的形式，就可以按位考虑合法性了。
我们枚举\(a_i\)的每一位上的值，再利用\(e_i\)确定整个\(a_i\)在该位上的值，然后检验是否合法即可。
最终的答案就是每一位上方案的乘积。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,Ans=1,A[MAXN],B[MAXN],C[MAXN],D[MAXN],E[MAXN];
int Read()
{ int a=0,c=1; char b=getchar();
while(b!='-'&&(b<'0'||b>'9')) b=getchar();
if(b=='-') c=-1,b=getchar();
while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
return a*c;
}
int Calc(int Bit,int St)
{ A[1]=St*Bit;
for(int i=2;i<=n;i++)
{ A[i]=(E[i]^A[1])&Bit;
if((A[i]|A[i-1])!=(B[i]&Bit)) return 0;
}
return 1;
}
int main()
{ n=Read();
for(int i=2;i<=n;i++) B[i]=Read();
for(int i=2;i<=n;i++) C[i]=Read();
for(int i=2;i<=n;i++) D[i]=C[i]-B[i],E[i]=B[i]^D[i]^E[i-1];
for(int i=0;i<=30;i++) Ans*=Calc(1<<i,0)+Calc(1<<i,1);
printf("%d\n",Ans);
}
F.Robots
题目链接
简要题解
对于前两种机器人，我们可以预处理出某个点最下和最右能走到哪儿，然后直接回答，因此下文只考虑第三种机器人。
这道题的暴力做法是\(O(q*n^2)\)的，即对每一个询问的矩形，直接遍历一次。
实际上我们发现，询问的矩形有很多重叠的地方，这些信息是可以重复利用的。
重复利用信息，那么就需要把多个询问一起处理，自然会想到分治，我们按行来分治。
假设我们当前需要处理第\(L\)行到第\(R\)行内的询问矩形，那么我们令\(Mid=(L+R)/2\)。
当前我们只处理起点在\([L,Mid]\)行，终点在\([Mid,R]\)行的询问，其余的询问可以继续递归分治处理。
我们对于第\([L,Mid]\)行中的每个点\((i,j)\)，求出它能走到第\(Mid\)行中的哪些点，设这个点集为\(F[i][j]\)。
对于\([Mid,Ri]\)行中的每个点\((i,j)\)，求出第\(Mid\)行有哪些点可以走到它，设这个点集为\(G[i][j]\)。
那么对于一个询问来说，我们只要判断\(F[X1][Y1]\)和\(G[X2][Y2]\)是否有交即可。
\(F[i][j]\)和\(G[i][j]\)可以直接转移，单次求\(F\)和\(G\)的时间复杂度是\(O(n^3)\)的，由于分治每一层都得求，总复杂度为\(O(n^3logn)\)。
处理一个询问的复杂度是\(O(n)\)的，处理所有询问的复杂度是\(O(q*n)\)的。
递归过程中需要分治询问，这部分的复杂度为\(O(q*logn)\)
实际上，我们对\(F\)和\(G\)的操作都可以用\(bitset\)实现，因此直接用\(bitset\)优化，时间复杂度可以除上一个\(\omega\)。
总复杂度为\(O(q*logn+\frac{q*n+n^3logn}{\omega})\)
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=510;
const int MAXQ=5e5+10;
struct ELE{ int X1,Y1,X2,Y2; }Q[MAXQ];
char Mat[510][510];
int n,m,Ls,Qs,Ans[MAXQ],Seq[MAXQ],Td[MAXQ];
int Right[MAXN][MAXN],Down[MAXN][MAXN];
bitset<MAXN>F[MAXN][MAXN],G[MAXN][MAXN],Zero;
int Read()
{ int a=0,c=1; char b=getchar();
while(b!='-'&&(b<'0'||b>'9')) b=getchar();
if(b=='-') c=-1,b=getchar();
while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
return a*c;
}
void Divide(int Le,int Ri,int Sl,int Sr)
{ if(Sl>Sr||Le>Ri) return ;
int Mid=(Le+Ri)/2,Nl=Sl,Nr=Sr;
for(int i=m,j=1;i>=1;i--,j++)
{ F[Mid][i].reset(),G[Mid][j].reset();
if(Mat[Mid][i]=='0') F[Mid][i].set(i),F[Mid][i]|=F[Mid][i+1];
if(Mat[Mid][j]=='0') G[Mid][j].set(j),G[Mid][j]|=G[Mid][j-1];
}
for(int i=Mid-1;i>=Le;i--)
for(int j=m;j>=1;j--)
F[i][j]=(Mat[i][j]=='0'?F[i][j+1]|F[i+1][j]:Zero);
for(int i=Mid+1;i<=Ri;i++)
for(int j=1;j<=m;j++)
G[i][j]=(Mat[i][j]=='0'?G[i][j-1]|G[i-1][j]:Zero);
for(int i=Sl;i<=Sr;i++)
if(Q[Seq[i]].X2<Mid) Td[Nl++]=Seq[i];
else if(Q[Seq[i]].X1>Mid) Td[Nr--]=Seq[i];
else Ans[Seq[i]]=(F[Q[Seq[i]].X1][Q[Seq[i]].Y1]&G[Q[Seq[i]].X2][Q[Seq[i]].Y2]).any();
for(int i=Sl;i<=Sr;i++) Seq[i]=Td[i];
Divide(Le,Mid-1,Sl,Nl-1),Divide(Mid+1,Ri,Nr+1,Sr);
}
int main()
{ n=Read(),m=Read();
for(int i=1;i<=n;i++) scanf("%s",Mat[i]+1);
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
{ Right[i][j]=(Mat[i][j+1]=='0'?Right[i][j+1]:j);
Down[i][j]=(Mat[i+1][j]=='0'?Down[i+1][j]:i);
}
Qs=Read();
for(int i=1;i<=Qs;i++)
{ int T=Read(),X1=Read(),Y1=Read(),X2=Read(),Y2=Read();
if(X1>X2||Y1>Y2||Mat[X1][Y1]!='0'||Mat[X2][Y2]!='0') continue ;
if(T!=3) Ans[i]=(T==1?Down[X1][Y1]>=X2&&Y1==Y2:Right[X1][Y1]>=Y2&&X1==X2);
else Q[i]=(ELE){X1,Y1,X2,Y2},Seq[++Ls]=i;
}
Divide(1,n,1,Ls);
for(int i=1;i<=Qs;i++) puts(Ans[i]?"yes":"no");
}
J.Tree
题目链接
简要题解
我们把博弈双方设为\(S\)和\(T\)，\(S\)先手，设游戏结束时，\(S\)和\(T\)的移动步数为\(F(S)\)和\(F(T)\)。
那么\(S\)希望\(F(S)-F(T)\)尽量大，\(T\)希望这个值尽量小。
也就是说，决策时需要考虑两个因素，自己走的步数尽量多，别人走的步数尽量少。
假设当前决策为\(S\)，那么\(S\)有两种决策，要么\(S\)朝着\(T\)移动，要么\(S\)朝着其他方向的一条最长链移动。
如果\(S\)没有朝着\(T\)移动，那么\(S\)和\(T\)就再也不会相互影响决策，只能各自按着最长链移动。
于是我们可以在树上把\(S\)到\(T\)的这条链单独拉出来，再处理出链上每个点不经过链，所能走到的最长链的长度。
我们用堆来维护\(S\)和\(T\)当前所能走到的最长链长度，然后模拟决策过程。
如果\(S\)没有朝着\(T\)移动，那么我们可以立马计算贡献，否则\(S\)朝着\(T\)走一步，轮到\(T\)决策，这个贡献递归处理即可。
\(S\)决策时，会取两种情况中贡献较大的那一个，\(T\)决策时会取较小的那一个。
时间复杂度\(O(nlogn)\)。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
struct EDGE{ int u,v,Next; }Edge[MAXN*2];
bool Vis[MAXN];
int n,S,T,Es,Ps,First[MAXN];
int Fa[MAXN],Deep[MAXN];
int Path[MAXN],Long[MAXN];
priority_queue<int>Hs,Ds,Ht,Dt;
int Read()
{ int a=0,c=1; char b=getchar();
while(b!='-'&&(b<'0'||b>'9')) b=getchar();
if(b=='-') c=-1,b=getchar();
while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
return a*c;
}
int Min(int A,int B){ return A<B?A:B; }
int Max(int A,int B){ return A>B?A:B; }
void Link(int u,int v){ Edge[++Es]=(EDGE){u,v,First[u]},First[u]=Es; }
void Dfs(int Now,int Ba)
{ Fa[Now]=Ba;
for(int i=First[Now],v;i!=-1;i=Edge[i].Next)
if((v=Edge[i].v)!=Ba) Dfs(v,Now);
}
int Get_Path(int Np){ return Path[++Ps]=Np,Vis[Np]=1,Np==T?0:Get_Path(Fa[Np]); }
int Dfs2(int Now,int Nd)
{ int Ret=Nd;
for(int i=First[Now],v;i!=-1;i=Edge[i].Next)
if(!Vis[v=Edge[i].v]) Vis[v]=1,Ret=Max(Ret,Dfs2(v,Nd+1));
return Ret;
}
int Dpt(int Ns,int Nt);
int Dps(int Ns,int Nt)
{ if(Ns+1==Nt) return Long[Ns]-Long[Nt];
Ds.push((Ns-1+Long[Ns])),Dt.push(Long[Ns]+Ps-Ns);
while(!Ht.empty()&&!Dt.empty()&&Ht.top()==Dt.top()) Ht.pop(),Dt.pop();
while(!Hs.empty()&&!Ds.empty()&&Hs.top()==Ds.top()) Hs.pop(),Ds.pop();
return Max(Long[Ns]-Ht.top()+Ps-Nt,Dpt(Ns+1,Nt)+1);
}
int Dpt(int Ns,int Nt)
{ if(Ns+1==Nt) return Long[Ns]-Long[Nt];
Ds.push((Nt-1+Long[Nt])),Dt.push(Long[Nt]+Ps-Nt);
while(!Hs.empty()&&!Ds.empty()&&Hs.top()==Ds.top()) Hs.pop(),Ds.pop();
while(!Ht.empty()&&!Dt.empty()&&Ht.top()==Dt.top()) Ht.pop(),Dt.pop();
return Min(Hs.top()-Ns+1-Long[Nt],Dps(Ns,Nt-1)-1);
}
int main()
{ n=Read(),S=Read(),T=Read();
memset(First,-1,sizeof(First));
for(int i=1,u,v;i<n;i++) u=Read(),v=Read(),Link(u,v),Link(v,u);
Dfs(T,T),Get_Path(S);
for(int i=1;i<=Ps;i++) Long[i]=Dfs2(Path[i],0);
for(int i=1;i<=Ps;i++) Ht.push(Long[i]+Ps-i);
for(int i=1;i<=Ps;i++) Hs.push(i-1+Long[i]);
printf("%d\n",Dps(1,Ps));
}