20241020比赛总结

T1 Reverse

https://www.gxyzoj.com/d/hzoj/p/P980

假设1在点i时，这个1可以通过一次翻转到达那些点，将这些点和i连边，此时答案就是s到x的最短路

但是，此时边数也会到达\(n^2\)级别

考虑优化，因为边权均为1，所以可以直接bfs，可以发现每个点能转移的点的奇偶性是有限制的，而且每个点至多被更新一次

所以可以将所有点按奇偶性分类后丢进set，然后找到转移边界，暴力更新即可

注意，选出的子串的长度必须为k，所以在靠近两个端点的地方是不能取点作为中心的

代码：

#include<cstdio>
#include<set>
#include<queue>
#define it set<int>::iterator
using namespace std;
int n,m,s,k,b[100005],ans[100005];
double lmid,rmid;
set<int> s1,s2;
queue<int> q;
void bfs(int st)
{
	for(int i=1;i<=n;i++)
	{
		ans[i]=1e9;
	}
	ans[st]=0;
	q.push(st);
	if(st%2) s1.erase(st);
	else s2.erase(st);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		double ls=u-lmid,rs=rmid-u;
		int l=lmid-ls,r=rmid+rs;
		l=max(l,max(0,u-k+1)),r=min(r,min(n,u+k-1));
	//	printf("%d %d %d %d\n",u,l,r,ans[u]);
		if((u+k+1)%2)
		{
			it lid=s1.lower_bound(l);
			it rid=s1.lower_bound(r);
			while(*lid<=r&&lid!=s1.end())
			{
				if(b[*lid])
				{
					lid++;
					continue;
				}
				ans[*lid]=ans[u]+1;
				q.push(*lid);
				lid++;
			}
		//	printf("1");
			lid=s1.lower_bound(l);
			if(*rid<=r&&rid!=s1.end()) rid++;
			s1.erase(lid,rid);
		}
		else
		{
			it lid=s2.lower_bound(l);
			it rid=s2.lower_bound(r);
			while(*lid<=r&&lid!=s2.end())
			{
				if(b[*lid])
				{
					lid++;
					continue;
				}
				ans[*lid]=ans[u]+1;
				q.push(*lid);
				lid++;
			}
			lid=s2.lower_bound(l);
			if(*rid<=r&&rid!=s2.end()) rid++;
			s2.erase(lid,rid);
		}
	}
}
int main()
{
	freopen("reverse.in","r",stdin);
	freopen("reverse.out","w",stdout);
	scanf("%d%d%d%d",&n,&k,&m,&s);
	lmid=(1+k)*1.0/2.0,rmid=(n+n-k+1)*1.0/2.0;
	for(int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		b[x]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(i%2) s1.insert(i);
		else s2.insert(i);
	}
	bfs(s);
	for(int i=1;i<=n;i++)
	{
		if(ans[i]!=1e9) printf("%d ",ans[i]);
		else printf("-1 ");
	}
	return 0;
}