为什么ABC那么多？建议Atcoder多出些ARC/AGC，好不容易才轮到AGC……

A

签到。就是以黑点为源点做多元最短路，由于边长是1直接bfs就好了，求最长路径。

#include
using namespace std;
const int N=,dx[]={,,,-},dy[]={,-,,};
int n,m,ans,qs,qe,d[N][N],qx[N*N],qy[N*N];
char mp[N][N];
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)scanf("%s",mp[i]+); for(int i=;i<=n;i++) for(int j=;j<=m;j++) if(mp[i][j]=='.')d[i][j]=1e9; else d[i][j]=,qx[qe]=i,qy[qe++]=j; while(qsn||v<||v>m||d[u][v]<=d[x][y]+)continue;
d[u][v]=d[x][y]+,ans=max(ans,d[u][v]);
qx[qe]=u,qy[qe++]=v;
}
}
cout<<ans<<endl;
}

B

实际上上下和左右可以分开算。假设只有U和D，那么所有U/D操作结束后，若保留在棋盘，则在区间[L,R]，于是根据是先手还是后手的操作，更改区间，若区间在操作途中为空或最终区间不包含棋子所在行/列，则先手获胜，反之后手获胜

#include
using namespace std;
const int N=2e5+;
int n,m,p,sr,sc;
char s[N],t[N];
bool walk1()
{
int L=,R=n;
for(int i=p;i;i--)
{
if(t[i]=='U')R=min(n,R+);else if(t[i]=='D')L=max(,L-);
if(s[i]=='U')L++;else if(s[i]=='D')R--;
if(L>R)return ;
}
return (srR);
}
bool walk2()
{
int L=,R=m;
for(int i=p;i;i--)
{
if(t[i]=='L')R=min(m,R+);else if(t[i]=='R')L=max(,L-);
if(s[i]=='L')L++;else if(s[i]=='R')R--;
if(L>R)return ;
}
return (scR);
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&p,&sr,&sc);
scanf("%s",s+);
scanf("%s",t+);
if(walk1()||walk2())puts("NO");
else puts("YES");
}

C

发现每次操作对树的改变只有2种：1、删去所有叶节点（n=2时不可使用）。2、保留其中一个叶节点，删去其他点（n=1时不可使用）。开始瞎蒙个SG函数的错误结论上去，白掉5min。然后发现树等价于长为直径的链上游戏，于是DP链长度为i时先手是否必胜即可。

#include
using namespace std;
const int N=2e5+;
int n,f[N],dep[N];
vectorG[N];
void dfs(int u,int fa)
{
for(int i=;idep[t])t=i;
for(int i=;i<=n;i++)dep[i]=;
dfs(t,);
t=;
for(int i=;i<=n;i++)t=max(t,dep[i]);
if(f[t])puts("First");else puts("Second");
}

D

很容易发现答案是O(logn)级别的，不妨考虑按照答案分步DP，设f[ans][i][j][k]表示答案<=ans，上下边界分别为i,j，左边界为k，右边界最靠右能达到多少。然后考虑转移，竖切可以直接转移，横切由于枚举横切点发现上下区间的DP值一个是先增后减，另一个是先减后增，然后可以二分转移。假设n,m同级，复杂度O(n3log2n)

#include
using namespace std;
const int N=;
int n,m,f[][N][N][N];
char s[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%s",s[i]+); for(int i=n;i;i--) for(int j=i;j<=n;j++) for(int k=m;k;k--) if(i==j) { if(k==m)f[][i][j][k]=m+; else f[][i][j][k]=s[i][k]==s[i][k+]?f[][i][j][k+]:k+; } else f[][i][j][k]=s[i][k]==s[i+][k]?min(f[][i][i][k],f[][i+][j][k]):k; for(int ans=,t=;;ans++,t^=) { if(f[t][][n][]==m+){printf("%d\n",ans);return ;} for(int i=n;i;i--) for(int j=i;j<=n;j++) for(int k=m;k;k--) { f[t^][i][j][k]=f[t][i][j][k]==m+?m+:f[t][i][j][f[t][i][j][k]]; if(i>;
if(f[t][i][mid][k]<=f[t][mid+][j][k])
f[t^][i][j][k]=max(f[t^][i][j][k],f[t][i][mid][k]),r=mid-;
else f[t^][i][j][k]=max(f[t^][i][j][k],f[t][mid+][j][k]),l=mid+;
}
}
}
}
}

EF

咕

result：rank217 rating+=47 now_rating=1925