自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:26:03，当前版本为作者最后更新于2021-06-14 15:28:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

巨大多简单题。

两个图案相等，至少要满足它们的点数相等，这里就有一个单调性。

考虑双指针，当前右端点扫描到 $r$，我们只需要将左端点移动到位置 $l$ 使得 $[l,r]$ 内画出的图恰有和给定图案一样的点数。

接下来的问题有两个：

• 如何求当前图案的点数：不妨设起点是 $(0,0)$，由于我们只需要 $2n\times 2m$ 个点，所以对每个位置维护当前有几笔经过了它，事实上更简单的实现是直接用 map 维护每个二元组有几笔经过它，当这个值清零是点数减少 $1$，当这个值从 $0$ 变成 $1$ 时点数增加 $1$；

• 如果比较两个图案：首先我们将它们对齐：让它们的左边界和上边界分别是 $x=0,y=0$，然后就可以用哈希比较了，设计哈希时要支持平移，所以对 $(x,y)$ 设定 $a^xb^y$ 的哈希值就比较合适。

时间复杂度为 $O(nm+l\log l)$。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010,P1=998244353,P2=10000019,P3=1000000009;
int inv1,inv2,l,m,n,cnt,cnt2,tot,hs,hs2,mnx,mny,cur,pos[MAXN],typ[MAXN],nx[MAXN],ny[MAXN];
string s;
multiset <int> mx,my;
map <pair<int,int>,int> mp;
int qpow (int a,int b) {
	if (b<0) {b=P3-1+b;}
	int res=1;
	while (b) {
		if (b&1) {res=(1ll*res*a)%P3;}
		a=(1ll*a*a)%P3,b>>=1;
	}
	return res;
}
int calc () {
	int mnnx=*(mx.begin()),mnny=*(my.begin());
	return (1ll*hs2*((1ll*qpow(inv1,mnnx)*qpow(inv2,mnny))%P3))%P3;
}
int main () {
	getline(cin,s);
	int len=s.length();
	for (int i=0;i<len;i++) {
		if (s[i]>='0'&&s[i]<='9') {l=l*10+s[i]-'0';}
	}
	getline(cin,s);
	len=s.length();
	nx[0]=ny[0]=0;
	for (int i=0;i<len;i++) {
		if (s[i]=='u') {
			cnt++;
			typ[cnt]=1,pos[cnt]=i+1,nx[cnt]=nx[cnt-1]-1,ny[cnt]=ny[cnt-1];
		} else if (s[i]=='d') {
			cnt++;
			typ[cnt]=2,pos[cnt]=i+1,nx[cnt]=nx[cnt-1]+1,ny[cnt]=ny[cnt-1];
		} else if (s[i]=='l') {
			cnt++;
			typ[cnt]=3,pos[cnt]=i+1,nx[cnt]=nx[cnt-1],ny[cnt]=ny[cnt-1]-1;
		} else if (s[i]=='r') {
			cnt++;
			typ[cnt]=4,pos[cnt]=i+1,nx[cnt]=nx[cnt-1],ny[cnt]=ny[cnt-1]+1;
		}
	}
	scanf("%d%d",&n,&m);
	mnx=n,mny=m;
	for (int i=1;i<=n;i++) {
		cin >> s;
		for (int j=0;j<m;j++) {
			if (s[j]=='X') {
				mnx=min(mnx,i),mny=min(mny,j+1),cnt2++;
				hs=(hs+(1ll*qpow(P1,i)*qpow(P2,j+1))%P3)%P3;
			}
		}
	}
	inv1=qpow(P1,P3-2),inv2=qpow(P2,P3-2);
	hs=(1ll*hs*((1ll*qpow(inv1,mnx)*qpow(inv2,mny))%P3))%P3;
	tot=1,hs2=1;
	mx.insert(0),my.insert(0);
	mp[make_pair(0,0)]=1;
	while (cur<cnt&&tot<cnt2) {
		cur++;
		mx.insert(nx[cur]),my.insert(ny[cur]);
		if (mp.find(make_pair(nx[cur],ny[cur]))==mp.end()) {
			tot++;
			mp[make_pair(nx[cur],ny[cur])]=1;
			hs2=(hs2+(1ll*qpow(P1,nx[cur])*qpow(P2,ny[cur]))%P3)%P3;
		} else if (mp[make_pair(nx[cur],ny[cur])]==0) {
			mp[make_pair(nx[cur],ny[cur])]=1;
			tot++;
			hs2=(hs2+(1ll*qpow(P1,nx[cur])*qpow(P2,ny[cur]))%P3)%P3;
		} else {
			mp[make_pair(nx[cur],ny[cur])]++;
		}
	}
	if (calc()==hs) {
		printf("YES\n1 %d\n",pos[cur]);
		return 0;
	}
	for (int i=1;i<cnt;i++) {
		mx.erase(mx.find(nx[i-1])),my.erase(my.find(ny[i-1]));
		if (--mp[make_pair(nx[i-1],ny[i-1])]==0) {
			tot--;
			hs2=(hs2-(1ll*qpow(P1,nx[i-1])*qpow(P2,ny[i-1]))%P3+P3)%P3;
		}
		while (cur<cnt&&tot<cnt2) {
			cur++;
			mx.insert(nx[cur]),my.insert(ny[cur]);
			if (mp.find(make_pair(nx[cur],ny[cur]))==mp.end()) {
				tot++;
				mp[make_pair(nx[cur],ny[cur])]=1;
				hs2=(hs2+(1ll*qpow(P1,nx[cur])*qpow(P2,ny[cur]))%P3)%P3;
			} else if (mp[make_pair(nx[cur],ny[cur])]==0) {
				mp[make_pair(nx[cur],ny[cur])]=1;
				tot++;
				hs2=(hs2+(1ll*qpow(P1,nx[cur])*qpow(P2,ny[cur]))%P3)%P3;
			} else {
				mp[make_pair(nx[cur],ny[cur])]++;
			}
		}
		if (calc()==hs) {
			printf("YES\n%d %d\n",pos[i+1],pos[cur]);
			return 0;
		}
	}
	printf("NO\n");
	return 0;
}