比赛 国庆欢乐赛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;
}