526互联

AtCoder Grand Contest 033

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - Darker and Darker

从 # 向外广搜即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m;
char s[N][N];
int id[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	memset(id,63,sizeof(id));
	queue<pair<int,int> >q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='#')
			{
				id[i][j]=0;
				q.push(make_pair(i,j));
			}
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0],ty=y+dir[i][1];
			if(tx<1||tx>n||ty<1||ty>m) continue;
			if(id[tx][ty]>id[x][y]+1)
			{
				id[tx][ty]=id[x][y]+1;
				q.push(make_pair(tx,ty));
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,id[i][j]);
	printf("%d",ans);
	return 0;
}

B - LRUD Game

考虑从后往前做，维护出合法的上边界，下边界，左边界，右边界，判断一下起始位置是否在合法区间内即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int h,w,n;
int sr,sc;
char s[N],t[N];
int main()
{
	scanf("%d%d%d",&h,&w,&n);
	scanf("%d%d",&sr,&sc);
	scanf("%s",s+1);
	scanf("%s",t+1);
	int lr=1,rr=h;
	for(int i=n;i>=1;i--)
	{
		if(t[i]=='U') rr++;
		else if(t[i]=='D') lr--;
		if(lr>rr)
		{
			printf("NO");
			return 0;
		}
		lr=max(lr,1),lr=min(lr,h);
		rr=max(rr,1),rr=min(rr,h);
		if(s[i]=='U') lr++;
		else if(s[i]=='D') rr--;
		if(lr>rr)
		{
			printf("NO");
			return 0;
		}
		lr=max(lr,1),lr=min(lr,h);
		rr=max(rr,1),rr=min(rr,h);
	}
	int lc=1,rc=w;
	for(int i=n;i>=1;i--)
	{
		if(t[i]=='L') rc++;
		else if(t[i]=='R') lc--;
		if(lc>rc)
		{
			printf("NO");
			return 0;
		}
		lc=max(lc,1),lc=min(lc,w);
		rc=max(rc,1),rc=min(rc,w);
		if(s[i]=='L') lc++;
		else if(s[i]=='R') rc--;
		if(lc>rc)
		{
			printf("NO");
			return 0;
		}
		lc=max(lc,1),lc=min(lc,w);
		rc=max(rc,1),rc=min(rc,w);
	}
	if(lr<=sr&&sr<=rr&&lc<=sc&&sc<=rc) printf("YES");
	else printf("NO");
	return 0;
}

C - Removing Coins

每次操作的本质相当于以一个点为根，将所有叶子删除。可以发现，直径中的点肯定是最后被删除的，我们只需要考虑直径即可。

问题转化成了一个序列，每个人每次可以删除 \(1\) 或 \(2\) 个点。令 \(f_i\) 表示长度为 \(i\) 先手是胜还是负，转移即可。注意直径的长度为 \(2\) 的情况。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=200005;
int n;
vector<int>G[N];
int s,t,len;
int p;
int dis[N];
void dfs(int u,int father)
{
	dis[u]=dis[father]+1;
	if(dis[u]>dis[p]) p=u;
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs(v,u);
	}
	return;
}
bool dp[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	p=0;
	dfs(1,0);
	s=p;
	p=0;
	dfs(s,0);
	t=p;
	len=dis[t];
	dp[0]=false,dp[1]=true,dp[2]=false;
	for(int i=3;i<=len;i++)
	{
		if(i-1>=0&&!dp[i-1]) dp[i]=true;
		if(i-2>=0&&!dp[i-2]) dp[i]=true;
	}
	if(dp[len]) printf("First");
	else printf("Second");
	return 0;
}

D - Complexity

令 \(f_{i,j,l,r}\) 表示 \(i\sim j\) 行，\(l\sim r\) 列的时间复杂度为多少，转移是枚举分界点即可。可以发现，状态过多，无法通过此题。

可以发现，答案不会超过 \(\log n+\log m\)，考虑将答案计入状态中，令 \(f_{i,l,r,k}\) 表示 \(i\) 行，\(l\sim r\) 列时间复杂度为 \(k\) 最远能到哪行。

转移分成两种：

  • 切列：\(f_{f_{i,l,r,k-1}+1,l,r,k-1}\to f_{i,l,r,k}\)
  • 切行：对于一个分界点 \(p\)，\(\min(f_{i,l,p,k-1},f_{i,p+1,r,k-1})\to f_{i,l,r,k}\)，可以发现，\(f_{i,l,p,k-1}\) 随着 \(p\) 的增大而减小，\(f_{i,p+1,r,k-1}\) 随着 \(p\) 的增大而增大，二分 \(p\) 转移即可。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=205;
int n,m;
char s[N][N];
int a[N][N];
int sum[N][N];
int f[N][N][N][17];
int getsum(int l1,int l2,int r1,int r2)
{
	if(l1>l2) return -1;
	if(r1>r2) return -1;
	return sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='#') a[i][j]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
	for(int i=1;i<=n;i++)
		for(int l=1;l<=m;l++)
			for(int r=l;r<=m;r++)
			{
				int L=i,R=n,j=i-1;
				while(L<=R)
				{
					int mid=(L+R)/2;
					auto check=[=](int x)
					{
						return getsum(i,mid,l,r)==(mid-i+1)*(r-l+1)||getsum(i,mid,l,r)==0;
					};
					if(check(mid)) j=mid,L=mid+1;
					else R=mid-1;
				}
				f[i][l][r][0]=j;
			}
	if(f[1][1][m][0]>=n)
	{
		printf("%d",0);
		return 0;
	}
	for(int k=1;k<=ceil(log2(n))+ceil(log2(m));k++)
	{
		for(int i=1;i<=n;i++)
			for(int l=1;l<=m;l++)
				for(int r=l;r<=m;r++)
				{
					f[i][l][r][k]=f[i][l][r][k-1];
					f[i][l][r][k]=max(f[i][l][r][k],f[f[i][l][r][k-1]+1][l][r][k-1]);
					int L=l,R=r-1,j=i-1;
					while(L<=R)
					{
						int mid=(L+R)/2;
						int vl=f[i][l][mid][k-1],vr=f[i][mid+1][r][k-1];
						j=max(j,min(vl,vr));
						if(vl<vr) R=mid-1;
						else L=mid+1;
					}
					f[i][l][r][k]=max(f[i][l][r][k],j);
				}
		if(f[1][1][m][k]>=n)
		{
			printf("%d",k);
			return 0;
		}
	}
	return 0;
}

E - Go around a Circle

不妨令串中第一个字符为 R，为 B 时同理。则圆中肯定不会出现连续的两个 B，那么所有的 B 就将圆分成了若干个段。对于一段，考虑它需要满足的条件。

对于串中的第一段 R，不妨令其的长度为 \(len\)。首先每一段 R 的长度肯定为奇数，否则某些点向左向右的长度都为偶数，某些点向左向右的长度都为奇数，即 \(len\) 需要即为奇数也为偶数，显然不合法。如果 \(len\) 为奇数，这段对圆中段的长度限制为 \(len\)，否则为 \(len+1\)。

对于串中的某一段（不是第一段） R，令其长度为 \(len\)。如果 \(len\) 的长度为偶数，则对圆中段没有限制，因为起始点肯定在两个端点上，可以在一条边连续走 \(len\) 次后出去。否则对圆中段的长度限制为 \(len\)。

考虑序列怎么做。不妨设上面的限制为 \(lim\)，令 \(f_i\) 表示长度为 \(i\) 的圆中段的且 \(i\to i+1\) 的边为 B 的方案数，转移枚举上一个 B 的位置：

\[f_i=\sum\limits_{j=i-1-lim}^{i-2}f_j[(i-1-j)\bmod 2=1] \]

前缀和优化即可。环的话只需要枚举后面一段跟第一段相连的长度，相加即可。

注意串中全相等的情况，特判即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
const int MOD=1000000007;
int n,m;
char s[N];
long long f[N];
long long sum[N];
long long g[N][2];
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	int lim=n;
	bool flag=false;
	for(int i=1,j=1;i<=m;i=j)
	{
		while(j<=m&&s[i]==s[j]) j++;
		int len=j-i;
		if(j<=m)
		{
			if(i==1)
			{
				if(len&1) lim=min(lim,len);
				else lim=min(lim,len+1);
			}
			if(s[i]==s[1]&&len%2==1) lim=min(lim,len);
		}
		else if(i==1) flag=true;
	}
	long long ans=0;
	if(flag)
	{
		f[0]=1,sum[0]=1;
		for(int i=1;i<=n;i++)
		{
			if(i-2>=0) f[i]=sum[i-2];
			sum[i]=(sum[i-1]+f[i])%MOD;
		}
		for(int i=0;i<=n-2;i++)
			ans=(ans+f[i]*(n-i)%MOD)%MOD;
		ans++;
	}
	else
	{
		f[0]=0,g[0][0]=0;
		f[1]=1,g[1][1]=1;
		for(int i=2;i<=n;i++)
		{
			f[i]=(g[i-2][i&1]-(i-1-lim-1>=0?g[i-1-lim-1][i&1]:0)+MOD)%MOD;
			g[i][0]=g[i-1][0],g[i][1]=g[i-1][1];
			g[i][i&1]=(g[i][i&1]+f[i])%MOD;
		}
		for(int i=1;i<=n;i++)
			if(n-i<=lim&&(n-i)%2==1) ans=(ans+f[i]*(n-i+1)%MOD)%MOD;
	}
	printf("%lld",ans);
	return 0;
}

F - Adding Edges

可以发现，如果存在边 \((a,b)\)，\((a,c)\) 且 \(b\) 在 \(a,c\) 上，那么可以将 \((a,c)\) 断开连上 \((b,c)\)，这样最后的结果是相同的。

令 \(top_{a,b}\) 表示 \(T\) 中 \(a\to b\) 的路径上在 \(G\) 中第一个与 \(a\) 有边相连的点。

考虑在 \(G\) 中加入一条边 \((a,b)\)，如果存在 \(top_{a,b}\)，加入 \((top_{a,b},b)\) 即可。同理如果存在 \(top_{b,a}\)，加入 \((a,top_{b,a})\) 即可。更新以 \(a\) 为根 \(b\) 的子树中的点 \(v\)，如果存在 \(top_{a,v}\)，加入 \((top_{a,v},b)\)，否则将 \(top_{a,v}\) 更新为 \(b\)。

然后以每个点为起始点，扫一遍即可。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=2005;
int n,m;
vector<int>G[N];
int fa[N][N];
void dfs(int u,int father,int p)
{
	fa[p][u]=father;
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs(v,u,p);
	}
	return;
}
int top[N][N];
void add(int a,int b)
{
	if(top[a][b]==b||top[b][a]==a) return;
	if(top[a][b]!=a) return add(top[a][b],b);
	if(top[b][a]!=b) return add(a,top[b][a]);
	top[a][b]=b,top[b][a]=a;
	vector<pair<int,int> >edge;
	queue<int>q;
	q.push(b);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:G[u])
		{
			if(v==fa[a][u]) continue;
			if(top[a][v]==a)
			{
				top[a][v]=b;
				q.push(v);
			}
			else edge.push_back(make_pair(b,top[a][v]));
		}
	}
	swap(a,b);
	q.push(b);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:G[u])
		{
			if(v==fa[a][u]) continue;
			if(top[a][v]==a)
			{
				top[a][v]=b;
				q.push(v);
			}
			else edge.push_back(make_pair(b,top[a][v]));
		}
	}
	for(auto [u,v]:edge)
		add(u,v);
	return;
}
int ans;
void solve(int u,int father,int pre)
{
	if(u!=pre&&top[pre][u]!=pre) pre=u,ans++;
	for(int v:G[u])
	{
		if(v==father) continue;
		solve(v,u,pre);
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int u=1;u<=n;u++)
		dfs(u,0,u);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			top[i][j]=i;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
		solve(i,0,i);
	printf("%d",ans/2);
	return 0;
}