题解：P13789 「CZOI-R6」游戏

SA_forever · 2025-08-22 16:57:32 · 题解

P13789 「CZOI-R6」游戏 题解

修改日志：2025.10.31：在给Levi_Ack讲题的时候，Levi_Ack问我为什么不能用另一种解法，我一想觉得没问题，新解法不仅好理解还好打，于是我似乎拿了个最短解？

• 题意：

  每一场游戏设置一个基准点，并以基准点为中心向四周扩散，在扩散时若是横向，则加 k1，若是纵向，则加 k2。求在 q 场游戏中各个点的最大权值。

• 思路：

  首先，这个题目的难点在于 q 的范围十分的大，如何快速地解决 q 场游戏成了要解决的问题。

那我们就能想到将 q 个基准点放进一个图里面，同时算最大值。

由于当前点的最大值一定是由其周围的点推过来的，所以我们可以通过递推实现求最大值。

但这个时候又产生了许多棘手的问题，例如怎么知道当前点的最大值是由哪个基准点推过来的？周围点的最大基准点或许并不是当前点的最大基准点等等问题。

• 解决方案：

  既然不知道基准点是从哪里推过来的，那么我们不妨设立一个方向，使得只能顺着这个方向推，此时就没有以上的那些问题了。

在设立一个方向后，只需要用 BFS 跑一遍求最大值即可。

那么我们对于方向为左上，左下，右上，右下的情况分别跑 BFS 后，一个点的最大值就是四种情况中该点值的最大值了。

• 实现：

  在一个 n \times m 的表上，将 q 个基准点标记后，从各个方向的起始位置（例如左上方向的起始位置是表格的右下角）开始 BFS 即可（注意要动态维护最大值）。

::::

• 代码：

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  const int N=3e3+5;
  int n,m,q,k1,k2,ans[N][N],a[N][N],s[N][N],vis[N][N];
  int quick_pow(int y){
  unsigned long long res=1,x=131;
  while(y){
      if(y&1)
          res*=x;
      x*=x,y>>=1;
  }
  return res;
  }
  void work(int nx,int ny,int dx,int dy){
  queue<pair<int,int>> q;q.push(make_pair(nx,ny));vis[nx][ny]=1;
  while(!q.empty()){
      pair<int,int> now=q.front();q.pop();int x=now.first,y=now.second;
      if(x-dx>=1&&x-dx<=n)
          s[x][y]=max(s[x][y],s[x-dx][y]+k1);
      if(y-dy>=1&&y-dy<=m)
          s[x][y]=max(s[x][y],s[x][y-dy]+k2);
      ans[x][y]=max(ans[x][y],s[x][y]);
      if(!vis[x+dx][y]&&x+dx>=1&&x+dx<=n)
          q.push(make_pair(x+dx,y)),vis[x+dx][y]=1;
      if(!vis[x][y+dy]&&y+dy>=1&&y+dy<=m)
          q.push(make_pair(x,y+dy)),vis[x][y+dy]=1;
  }
  }
  void solve(int nx,int ny,int dx,int dy){
  for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          s[i][j]=a[i][j],vis[i][j]=0;
  work(nx,ny,dx,dy);
  }
  signed main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m>>q>>k1>>k2;
  for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          ans[i][j]=a[i][j]=-0x7f7f7f7f7f7f7f7f;
  for(int i=1,x,y,z;i<=q;i++)
      cin>>x>>y>>z,a[x][y]=max(a[x][y],z);
  solve(1,1,1,1);solve(1,m,1,-1);solve(n,1,-1,1);solve(n,m,-1,-1);//分别为右上、右下、左上、左下
  unsigned long long num=0;
  for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          num+=ans[i][j]*quick_pow((i-1)*m+j);
  cout<<num;
  return 0;
  }

• 第二种解法：

在第一种解法的基础上，我们会发现斜向维护不仅难理解还难打，于是我们可以先左右递推，再上下递推，此时只需要分别维护一下最大值即可

::::

• 代码（写得比较抽象，见谅）：

  #include<bits/stdc++.h>
  #define int long long
  #define F(i,n) for(int i=1;i<=n;i++)
  #define rF(i,n) for(int i=n;i>=1;i--)
  using namespace std;
  int n,m,q,k1,k2,f[3010][3010],a[3010][3010];
  signed main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m>>q>>k1>>k2;
  for(int i=0;i<=n+1;i++)
      for(int j=0;j<=m+1;j++)
          a[i][j]=-0x7f7f7f7f7f7f7f7f;
  F(i,q){
      int x,y,z;cin>>x>>y>>z;
      a[x][y]=max(a[x][y],z);
  }
  for(int i=0;i<=n+1;i++)
      for(int j=0;j<=m+1;j++)
          f[i][j]=a[i][j];
  F(i,n)F(j,m)
      f[i][j]=max(f[i][j],f[i][j-1]+k2);
  F(i,n)rF(j,m)
      a[i][j]=max(a[i][j],a[i][j+1]+k2);
  F(i,n)F(j,m)
      a[i][j]=f[i][j]=max(a[i][j],f[i][j]);
  F(j,m)F(i,n)
      f[i][j]=max(f[i][j],f[i-1][j]+k1);
  F(j,m)rF(i,n)
      a[i][j]=max(a[i][j],a[i+1][j]+k1);
  unsigned int num=0,res=1;
  F(i,n)F(j,m)
      res*=131,num+=max(a[i][j],f[i][j])*res;
  return cout<<num,0;
  }

::::info[后记（如果你不知道为什么错了，请看这里）]

由于基准点的位置可能相同，所以需要在输入基准点的时候维护最大值。

由于代码实现中会出现负数，所以 unsigned long long 最好只给需要取模的值用。

由于点的最大值最小能取到很小，所以设的初始值最好为 -0x7f7f7f7f7f7f7f7f。

记得使用 BFS，因为 DFS 在部分情况下会出错。

对于不同的方向跑 BFS 时，记得初始化数组。