比赛 国庆欢乐赛3 评测结果 AAAAAAAAAAAAAAA
题目名称 Following Directions 最终得分 100
用户昵称 梦那边的美好TE 运行时间 0.773 s
代码语言 C++ 内存使用 19.42 MiB
提交时间 2025-10-05 09:18:46
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
const int N=2010;
int f[N*N],n,siz[N*N],q,c[N*N];
char s[N][N];
long long sum;
int id(int x,int y){
    return (x-1)*(n+1)+y;
}
int main(){
    freopen("zunxun.in","r",stdin);
    freopen("zunxun.out","w",stdout); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=n;j++){
            if(s[i][j]=='R')f[id(i,j)]=id(i,j+1);
            else f[id(i,j)]=id(i+1,j);
        }
        scanf("%d",&c[id(i,n+1)]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&c[id(n+1,i)]);
    }
    for(int i=n;i>=1;i--){
        for(int j=n;j>=1;j--){
            int x=id(i,j);
            c[x]=c[f[x]];
            sum+=c[x]; 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x=id(i,j);
            siz[x]++;
            siz[f[x]]+=siz[x];
        }
    }
    printf("%lld\n",sum);
    scanf("%d",&q);
    int i,j,x,y,v1,v2;
    while(q--){
        scanf("%d %d",&i,&j);
        x=id(i,j);
        y=x;while(f[y])y=f[y];v1=c[y];
        y=f[x];while(f[y])siz[y]-=siz[x],y=f[y];
        if(s[i][j]=='D'){
            f[x]=id(i,j+1);
            s[i][j]='R';
        }else{
            f[x]=id(i+1,j);
            s[i][j]='D';
        }
        y=f[x];while(f[y])siz[y]+=siz[x],y=f[y];v2=c[y];
        sum+=1ll*(v2-v1)*siz[x];       
        printf("%lld\n",sum);
    }
    return 0;
}