自动搬运

查看原文

来自洛谷，原作者为

	DerrickLo **

搬运于2025-08-24 22:54:38，当前版本为作者最后更新于2024-10-23 12:38:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑转化成图论问题。

我们从 $(i,j)$ 到 $(j,k)$ 连一条边当且仅当从起始点 $i$，终止点 $j$ 的状态可以转化成起始点 $j$，终止点 $k$ 的状态。先考虑如何建图，考虑枚举终止点 $j$，然后将其余点按与 $j$ 点连边后与 $x$ 轴正方向的夹角排序，这里可以先按所在象限排序，再按斜率排序。然后我们考虑枚举 $i$，那么可以直接二分出来对应的 $k$，这样就能在 $\mathcal O(n^2\log n)$ 的时间内完成建图。

那么建完图之后，一个点 $i$ 如果是绿色点当且仅当存在 $j$ 使得 $(i,j)$ 在一个环内，一个点 $i$ 如果是蓝色点当且仅当它不是绿色点并且存在 $j\neq k$ 使得 $(i,j)$ 可以到达 $(i,k)$。

考虑缩点，第一问是简单的，第二问直接对于每个点维护一个 bitset，第 $i$ 位表示这个点是否有 $j$ 使得这个点能到达 $(i,j)$ 就可以了。

时间复杂度 $\mathcal O(n^2\log n+\frac{n^3}{\omega})$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,m,x[1005],y[1005],low[1000005],dfn[1000005],st[1000005],top,ins[1000005],cntt,fr[1000005],cnt,vis[1005],fff[1005],co[1000005],in[1000005];
vector<int>ve[1000005],ve2[1000005];
bitset<1005>f[1000005],g[1000005];
queue<int>qu;
struct ee{
	int u,v;
}e[1000005];
struct nd{
	int k,dis,id;
	long double xl;
	friend bool operator<(const nd&a,const nd&b){
		if(a.k!=b.k)return a.k<b.k;
		if(a.xl-b.xl>1e-18||b.xl-a.xl>1e-18)return a.xl-b.xl<1e-18;
		return a.dis<b.dis;
	}
	friend bool operator>(const nd&a,const nd&b){
		return b<a;
	}
}a[1005];
long double slope(int i,int j){
	if(x[i]==x[j]){
		return (int)-1e18;
	}
	return (long double)(y[i]-y[j])/(x[i]-x[j]);
}
int dist(int i,int j){
	return(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int get(int i,int j){
	return(i-1)*n+j;
}
void tarjan(int u){
	low[u]=dfn[u]=++cnt,st[++top]=u,ins[u]=1;
	for(int v:ve[u]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		cntt++;
		do{
			fr[st[top]]=cntt;
			ins[st[top]]=0;
		}while(st[top--]!=u);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++){
		int cnt=0;
		for(int j=1;j<=n;j++)if(i!=j){
			cnt++,a[cnt].dis=dist(i,j),a[cnt].xl=slope(i,j),a[cnt].id=j;
			if(x[j]>x[i]&&y[j]>=y[i])a[cnt].k=1;
			if(x[j]<=x[i]&&y[j]>y[i])a[cnt].k=2;
			if(x[j]<x[i]&&y[j]<=y[i])a[cnt].k=3;
			if(x[j]>=x[i]&&y[j]<y[i])a[cnt].k=4;
		}
		sort(a+1,a+cnt+1);
		for(int j=1;j<=cnt;j++){
			nd xx=a[j];xx.dis=-1e18;
			if(xx.k<=2)xx.k+=2;
			else xx.k-=2;
			int now=lower_bound(a+1,a+cnt+1,xx)-a;
			e[++m]={get(a[j].id,i),get(i,a[(now+t-2)%cnt+1].id)};
			ve[get(a[j].id,i)].emplace_back(get(i,a[(now+t-2)%cnt+1].id));
		}
	}
	for(int i=1;i<=n*n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n*n;i++)co[fr[i]]++,g[fr[i]][(i-1)/n+1]=1;
	for(int i=1;i<=n*n;i++)if(co[fr[i]]>1)vis[(i-1)/n+1]=1;
	for(int i=1;i<=m;i++)if(fr[e[i].u]!=fr[e[i].v]){
		ve2[fr[e[i].v]].emplace_back(fr[e[i].u]),in[fr[e[i].u]]++;
	}
	for(int i=1;i<=cntt;i++)if(!in[i])qu.push(i);
	while(!qu.empty()){
		int ft=qu.front();qu.pop();
		for(int v:ve2[ft]){
			f[v]|=f[ft],f[v]|=g[ft];
			if(--in[v]==0)qu.push(v);
		}
	}
	for(int i=1;i<=n*n;i++)if(f[fr[i]][(i-1)/n+1]&&!vis[(i-1)/n+1])vis[(i-1)/n+1]=2;
	for(int i=1;i<=n;i++){
		if(vis[i]==1)cout<<"G";
		else if(vis[i]==2)cout<<"B";
		else cout<<"R";
	} 
	return 0;
}