[USACO23JAN] Following Directions S 题解

FFTotoro · 2023-01-31 19:37:49 · 题解

因为本题时限高达 8s，我们就大胆地想如何较为简单地维护本题的操作。

显然，每一次翻转标志操作，为了减少运算次数，我们只需更改本次操作有影响到的坐标即可。

为了便利解题，我们定义几个数组：

同时，我们定义一个点的“前驱”为可以通过一步直接走到这个坐标的坐标，“后继”为这个坐标能一步走到的下一个坐标。

第一次操作前，先预处理出 f,r 数组，暴力搜索求出所有奶牛吃到的饲料的价值和（记为 s）。

考虑每次操作后，f,r 数组和答案 s 会怎么改变；不妨设改变的坐标为 (x,y)，且路标是由“向下”改为“向右”（“向右”变“向下”同理）：

• 对于 f 数组：首先 f_{x,y} 要从 f_{x+1,y} 变为 f_{x,y+1}。其次吃饲料必须经过 (x,y) 的所有奶牛的 f 的值也需要相应的改变，可以通过一次 dfs 实现；

• 对于 c 数组：可以看出必须经过 (x+1,y) 的奶牛减少了 c_{x,y} 头，必须经过 (x,y+1) 的奶牛增加了 c_{x,y} 头，同时它们的后继、后继的后继……的 c 的值也要更新，同样可以通过 dfs 实现；

• 对于答案 s：因为必须经过 (x,y) 的奶牛有 c_{x,y} 头，而这些奶牛坐标的 f 的值都由 f_{x+1,y} 变为了 f_{x,y+1}，所以 s\leftarrow s+c_{x,y}(f_{x,y+1}-f_{x+1,y})；每次操作后输出 s 即可。

放代码：

/*
ID: CrowMatrix
TASK: Following Directions
LANG: C++
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1502][1502],f[1502][1502],r[1502][1502];
void dfs(int x,int y,int u){
  f[x][y]=u; r[x][y]=1;
  if(x&&a[x-1][y]==-1)dfs(x-1,y,u),r[x][y]+=r[x-1][y];
  if(y&&a[x][y-1]==-2)dfs(x,y-1,u),r[x][y]+=r[x][y-1];
}
void update1(int x,int y,int u){
  f[x][y]=u;
  if(a[x-1][y]==-1)update1(x-1,y,u);
  if(a[x][y-1]==-2)update1(x,y-1,u);
}
void update2(int x,int y,int u){
  r[x][y]+=u;
  if(a[x][y]==-1)update2(x+1,y,u);
  if(a[x][y]==-2)update2(x,y+1,u);
}
main(){
  ios::sync_with_stdio(false);
  int n,s=0; cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      char c; cin>>c;
      if(c=='D')a[i][j]=-1;
      else a[i][j]=-2;
    }
    cin>>a[i][n+1];
  }
  for(int i=1;i<=n;i++)cin>>a[n+1][i];
  for(int i=1;i<=n;i++)dfs(i,n+1,a[i][n+1]),dfs(n+1,i,a[n+1][i]);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)s+=f[i][j];
  cout<<s<<endl;
  int q; cin>>q;
  while(q--){
    int x,y; cin>>x>>y;
    if(a[x][y]==-1){
      s+=(f[x][y+1]-f[x+1][y])*r[x][y];
      a[x][y]=-2; update1(x,y,f[x][y+1]);
      update2(x+1,y,-r[x][y]); update2(x,y+1,r[x][y]);
    }
    else{
      s+=(f[x+1][y]-f[x][y+1])*r[x][y];
      a[x][y]=-1; update1(x,y,f[x+1][y]);
      update2(x,y+1,-r[x][y]); update2(x+1,y,r[x][y]);
    }
    cout<<s<<endl;
  }
  return 0;
}