专栏文章

题解：P13789 「CZOI-R6」游戏

SSA_forever
P13789题解参与者 7已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mio6ux3q
此快照首次捕获于
2025/12/02 14:20
3 个月前
此快照最后确认于
2025/12/02 14:20
3 个月前
查看原文

P13789 「CZOI-R6」游戏 题解

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

  • 题意：

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

  • 思路：

首先，这个题目的难点在于 qq 的范围十分的大，如何快速地解决 qq 场游戏成了要解决的问题。
那我们就能想到将 qq 个基准点放进一个图里面，同时算最大值。
由于当前点的最大值一定是由其周围的点推过来的，所以我们可以通过递推实现求最大值。
但这个时候又产生了许多棘手的问题，例如怎么知道当前点的最大值是由哪个基准点推过来的？周围点的最大基准点或许并不是当前点的最大基准点等等问题。

  • 解决方案：

既然不知道基准点是从哪里推过来的，那么我们不妨设立一个方向，使得只能顺着这个方向推，此时就没有以上的那些问题了。
在设立一个方向后，只需要用 BFS 跑一遍求最大值即可。
那么我们对于方向为左上，左下，右上，右下的情况分别跑 BFS 后，一个点的最大值就是四种情况中该点值的最大值了。

  • 实现：

在一个 n×mn \times m 的表上，将 qq 个基准点标记后，从各个方向的起始位置（例如左上方向的起始位置是表格的右下角）开始 BFS 即可（注意要动态维护最大值）。
以第二个样例为例
初始表格：
11−∞-\infty−∞-\infty−∞-\infty
−∞-\infty33−∞-\infty−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
−∞-\infty−∞-\infty77−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
右上方：
11335577
−∞-\infty335577
−∞-\infty−∞-\infty4466
−∞-\infty−∞-\infty7799
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
右下方：
11335577
−2-2335577
−5-5002244
−8-8−3-37799
−11-11−6-64466
左上方：
2200−2-2−∞-\infty
553311−∞-\infty
886644−∞-\infty
11119977−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
左下方：
11−∞-\infty−∞-\infty−∞-\infty
5533−∞-\infty−∞-\infty
2200−∞-\infty−∞-\infty
11119977−∞-\infty
886644−∞-\infty

  • 代码：

CPP
#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;
}

  • 第二种解法：

在第一种解法的基础上，我们会发现斜向维护不仅难理解还难打，于是我们可以先左右递推，再上下递推，此时只需要分别维护一下最大值即可
以第二个样例为例
初始表格：
11−∞-\infty−∞-\infty−∞-\infty
−∞-\infty33−∞-\infty−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
−∞-\infty−∞-\infty77−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
右方：
11335577
−∞-\infty335577
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
−∞-\infty−∞-\infty7799
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
左方：
11−∞-\infty−∞-\infty−∞-\infty
5533−∞-\infty−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
11119977−∞-\infty
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
这个时候的表格变为：
11335577
55335577
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
1111997799
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
上方：
55335577
77555577
99775577
1111997799
−∞-\infty−∞-\infty−∞-\infty−∞-\infty
下方：
11335577
55335577
33113355
1111997799
99775577

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

CPP
#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;
}
后记（如果你不知道为什么错了，请看这里）
由于基准点的位置可能相同，所以需要在输入基准点的时候维护最大值。
由于代码实现中会出现负数，所以 unsigned long long 最好只给需要取模的值用。
由于点的最大值最小能取到很小，所以设的初始值最好为 −0x7f7f7f7f7f7f7f7f-0x7f7f7f7f7f7f7f7f。
记得使用 BFS，因为 DFS 在部分情况下会出错。
对于不同的方向跑 BFS 时，记得初始化数组。
visivis_i 记录的是 ii 有没有进过队列，而不是有没有访问过，不然会重复进队。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...