专栏文章

题解：P14445 [ICPC 2025 Xi'an Practice] Follow the Sequence

wwangyizhi
P14445题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minatr1a
此快照首次捕获于
2025/12/01 23:23
3 个月前
此快照最后确认于
2025/12/01 23:23
3 个月前
查看原文
模拟。

题目分析

先暴力求出在 nn 步之内能走到的地方。
容易发现，接下来的移动构成了一个循环。假设 nn 步之后走到的地方是 (x0,y0)(x_0,y_0)，若第一个循环走到过 (x,y)(x,y)，那么必可以走到 (x+x0t,y+y0t)(x+x_0 t,y+y_0 t)，其中 t∈Nt \in \mathbb{N}。
考虑如何判断一个位置能否能被走到。特判 x0=y0=0x_0=y_0=0。考虑 x0>0x_0 > 0 的情况（其余情况类似），取 p=−inf⁡p=-\inf，我们可以将第一个循环中的一个点 (x,y)(x,y) 尽可能向左挪，取最大的 tt 使得 x′=x−x0t≥px'=x-x_0t \ge p，这时 y′=y−y0ty'=y-y_0t。考虑询问的 (a,b)(a,b) 能否为这个位置对应的位置，同样取最大的 kk 满足 a′=a−x0k≥pa'=a-x_0k \ge p，令 b′=b−y0kb'=b-y_0k，发现只要 (a′,b′)=(x′,y′)(a',b')=(x',y') 且 k≥tk \ge t。而且这个条件是充要的，且不重不漏。
map 实现，O(nlog⁡n)O(n \log n)。

Code

CPP
#include<bits/stdc++.h>
//bool Mst;
using namespace std;
using ll=long long;
using ld=long double;
#define int ll
using pii=pair<int,int>;
const int inf=1e9;
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	map<char,pii> dir;
	dir['U']={0,1},dir['D']={0,-1},dir['L']={-1,0},dir['R']={1,0};
	int t;cin>>t;
	while(t--) [&]()->void
	{
		map<pii,int> mp;
		int n,m,x0=0,y0=0,x=0,y=0,swp=0;
		cin>>n>>m;
		string s;
		cin>>s;
		for(char ch:s)
		{
			auto [dx,dy]=dir[ch];
			x0+=dx,y0+=dy;
		}
		if(x0==0&&y0==0)
		{
			for(char ch:s)
			{
				mp[{x,y}]=1;
				auto [dx,dy]=dir[ch];
				x+=dx,y+=dy;
			}
			int ans=0,xx,yy;
			while(m--) cin>>xx>>yy,ans+=mp[{xx,yy}];
			cout<<ans<<"\n";
			return;
		}
		if(!x0) swp=1,swap(x0,y0);
		int px;
		if(x0>0) px=inf;
		else px=-inf;
		for(char ch:s)
		{
			int t=(x-px)/x0;
			int xx=x-t*x0,yy=y-t*y0;
			if(mp.count({xx,yy})) mp[{xx,yy}]=min(mp[{xx,yy}],t);
			else mp[{xx,yy}]=t;
			auto [dx,dy]=dir[ch];
			if(swp) swap(dx,dy);
			x+=dx,y+=dy;
		}
		int ans=0;
		while(m--)
		{
			int xx,yy;cin>>xx>>yy;
			if(swp) swap(xx,yy);
			int t=(xx-px)/x0;
			xx-=t*x0,yy-=t*y0;
			if(mp.count({xx,yy})&&mp[{xx,yy}]<=t) ans++;
		}
		cout<<ans<<"\n";
	}();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...