自动搬运

查看原文

来自洛谷，原作者为

	FL_sleake 漫漫月华无边

搬运于2025-08-24 23:04:03，当前版本为作者最后更新于2024-07-06 14:08:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

解题思路

维护坐标是简单的，注意走到边界处时及时停下即可。难点在于修改操作。

Subtask 1

由于 $q=1$，所以输出移动一次后的位置即可。

Subtask 2

$n,m$ 其实没有用。由于 $q \leq 100$，考虑按照题目描述的暴力修改 $c_i$ 即可。

Subtask 3

首先需要发现对 $c_i$ 进行偶数次修改等于没有修改，进行奇数次修改等于修改一次。

由于 $k=1$，所以每次修改的都是连续段，提高组选手可以考虑一个线段树砸上去。但是这是基础赛，所以我们考虑差分。维护一个 $flag$ 代表是否修改。如果第 $i$ 次移动结束后需要修改，先把 $flag$ 异或上 $1$，再维护一个差分数组 $cnt$，将 $cnt_{i+b_i+1}$ 也异或上 $1$。在第 $i$ 次移动前，让 $flag$ 异或上当前的 $cnt_i$ 即可。

Subtask 4 & 5

发现 $k$ 的加入并没有本质影响。实际上就是把 $c$ 序列按照下标除以 $k$ 的余数分成了 $k$ 组。提高组选手可以考虑 $k$ 个线段树砸上去，并没有刻意卡线段树。但是这是基础赛，所以我们考虑 $k$ 个差分砸上去即可。和 Subtask 3 没有本质区别。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,q;
string s[510];
char c[200010];
int a[200010],b[200010];
int cnt[200100][25],flg[25];
//修改的函数
char Change(char x){
	if(x=='U') return 'D';
	if(x=='D') return 'U';
	if(x=='L') return 'R';
	if(x=='R') return 'L'; 
}
signed main(){
	cin>>n>>m>>q>>k;
	for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];
	for(int i=1;i<=q;i++) cin>>c[i]>>a[i]>>b[i];
	int x=1,y=1;
	for(int i=1;i<=q;i++){
		int id;
      //判断除以k的余数
		if(i%k==0) id=k;
		else id=i%k;
		flg[id]^=cnt[i][id];
      //修改
		if(flg[id]) c[i]=Change(c[i]);
      //移动
		if(c[i]=='U') x=max(1ll,x-a[i]);
		if(c[i]=='D') x=min(n,x+a[i]);
		if(c[i]=='L') y=max(1ll,y-a[i]);
		if(c[i]=='R') y=min(m,y+a[i]);
      //修改，利用差分思想
		if(s[x][y]=='X') flg[id]^=1,cnt[i+b[i]*k+k][id]^=1;
	}
	cout<<x<<" "<<y<<endl;
	return 0;
}

事实上空间复杂度可以优化到 $\Theta(n)$，因为上述代码中 $cnt$ 数组实际用到的空间只有 $\Theta(n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,q;
string s[510];
char c[200010];
int a[200010],b[200010];
int cnt[200100],flg[25];
//修改的函数
char Change(char x){
	if(x=='U') return 'D';
	if(x=='D') return 'U';
	if(x=='L') return 'R';
	if(x=='R') return 'L'; 
}
signed main(){
	cin>>n>>m>>q>>k;
	for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];
	for(int i=1;i<=q;i++) cin>>c[i]>>a[i]>>b[i];
	int x=1,y=1;
	for(int i=1;i<=q;i++){
		int id;
      //判断除以k的余数
		if(i%k==0) id=k;
		else id=i%k;
		flg[id]^=cnt[i];
      //修改
		if(flg[id]) c[i]=Change(c[i]);
      //移动
		if(c[i]=='U') x=max(1ll,x-a[i]);
		if(c[i]=='D') x=min(n,x+a[i]);
		if(c[i]=='L') y=max(1ll,y-a[i]);
		if(c[i]=='R') y=min(m,y+a[i]);
      //修改，利用差分思想
		if(s[x][y]=='X') flg[id]^=1,cnt[i+b[i]*k+k]^=1;
	}
	cout<<x<<" "<<y<<endl;
	return 0;
}