「FSLOI Round I」迷雾 题解
FL_sleake
·
·
题解
解题思路
维护坐标是简单的，注意走到边界处时及时停下即可。难点在于修改操作。
Subtask 1
由于 q=1，所以输出移动一次后的位置即可。
Subtask 2
#### 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 没有本质区别。
### 代码示例
```cpp
#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)$。
```cpp
#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;
}
```