比赛 |
国庆欢乐赛3 |
评测结果 |
AWWWWWWTTTTTTTT |
题目名称 |
Following Directions |
最终得分 |
7 |
用户昵称 |
彭欣越 |
运行时间 |
24.232 s |
代码语言 |
C++ |
内存使用 |
21.12 MiB |
提交时间 |
2025-10-05 11:23:59 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1510;
int r[N],d[N],mk[N][N],num[N][N],sum[N][N],id[N][N],c[N*N];
int n,q,cnt,jsq,q1[N],q2[N],vis[N][N],p[N*N];
ll ans;
string s[N];
struct node {
int x,y;
}f[N][N];
void dfs (int x,int y,int sm) {
//cout << x <<' '<< y <<endl;
if (mk[x][y]) sm--;
num[x][y]=sm;
id[x][y]=cnt;
mk[x][y]=1;
if (x>n) {
sum[x][y]=d[y];
p[cnt]=d[y];
ans+=num[x-1][y]*d[y];
//cout << num[x-1][y] <<' '<< d[y] <<endl;
return;
}
if (y>n) {
sum[x][y]=r[x];
p[cnt]=r[x];
ans+=num[x][y-1]*r[x];
//cout << num[x-1][y] <<' '<< d[y] <<endl;
return;
}
if (s[x][y-1]=='R') {
//num[x][y+1]+=num[x][y];
//cout << num[x][y+1] <<' '<< num[x][y] <<endl;
dfs(x,y+1,sm+1);
sum[x][y]=sum[x][y+1];
return;
}
if (s[x][y-1]=='D') {
//num[x+1][y]+=num[x][y];
//cout << num[x][y+1] <<' '<< num[x][y] <<endl;
dfs(x+1,y,sm+1);
sum[x][y]=sum[x+1][y];
return;
}
}
void dfs1 (int x,int y,int cnt) {
if (cnt!=id[x][y]) {
id[x][y]=cnt;
jsq++;
}
if (x<=0||y<=0) return;
if (s[x][y-2]=='R') {
dfs1(x,y-1,cnt);
}
if (s[x-1][y-1]=='D') {
dfs1(x-1,y,cnt);
}
return;
}
void dfs2 (int x,int y,int cnt) {
if (cnt!=id[x][y]) {
id[x][y]=cnt;
jsq++;
}
if (x>n||y>n) return;
if (s[x][y-1]=='R') {
num[x][y+1]+=c[cnt];
dfs2(x,y+1,cnt);
return;
}
if (s[x][y-1]=='D') {
num[x+1][y]+=c[cnt];
dfs2(x+1,y,cnt);
return;
}
return;
}
int main () {
freopen("zunxun.in","r",stdin);
freopen("zunxun.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++) {
//for (int j=1;j<=n;j++) num[i][j]=1;
cin >> s[i];
cin >> r[i];
//cout << r[i] <<' '<< i <<endl;
}
for (int i=1;i<=n;i++) cin >> d[i];
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (mk[i][j]) continue;
cnt++;
dfs(i,j,1);
//cout << num[i][j] <<endl;
}
}
cout << ans <<endl;
cin >> q;
for (int i=1;i<=q;i++) {
cin >> q1[i] >> q2[i];
jsq=0;
int t=id[q1[i]][q2[i]],t1;
c[t]-=num[q1[i]][q2[i]]-c[t];
dfs2(q1[i],q2[i],t);
if (s[q1[i]][q2[i]-1]=='R') {
s[q1[i]][q2[i]-1]='D';
t1=id[q1[i]+1][q2[i]];
}else{
s[q1[i]][q2[i]-1]='R';
t1=id[q1[i]][q2[i]+1];
}
//cout << id[1][2] <<' '<< s[q1[i]][q2[i]-1] <<endl;
c[t1]+=num[q1[i]][q2[i]]-c[t];
dfs1(q1[i],q2[i],t1);
dfs2(q1[i],q2[i],t1);
ans+=jsq*(p[t1]-p[t]);
cout << ans <<endl;
}
return 0;
}