专栏文章

题解：CF761F Dasha and Photos

llyh0217
CF761F题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miniiita
此快照首次捕获于
2025/12/02 02:58
3 个月前
此快照最后确认于
2025/12/02 02:58
3 个月前
查看原文
题目传送门
O(k2)\mathcal{O}(k^2) 是简单的，只用暴力选 22 个矩阵后容斥即可。考虑到对于矩阵处理不是很好优化，考虑对于每个格子进行计算。
我们设 aa 为原矩阵，fi,j,kf_{i,j,k} 表示将 (i,j)(i,j) 改为 kk 时产生的距离贡献，f2i,jf2_{i,j} 表示所有矩阵和原矩阵产生的贡献，我们令 cnti,j,kcnt_{i,j,k} 表示有几个矩阵将 (i,j)(i,j) 改为了 kk，cnt2i,jcnt2_{i,j} 表示有几个矩阵覆盖了 (i,j)(i,j)，则：
fi,j,k=∣ai,j−k∣×(k−cnt2i,j)+∑col=126∣col−k∣×cnti,j,colf_{i,j,k}=\left|a_{i,j}-k\right|\times (k-cnt2_{i,j})+\sum_{col=1}^{26}\left|col-k\right|\times cnt_{i,j,col}
f2i,j=∑col=126cnti,j,col×∣ai,j−col∣f2_{i,j}=\sum_{col=1}^{26} cnt_{i,j,col}\times \left|a_{i,j}-col\right|
显然 cntcnt 和 cnt2cnt2 都可以差分处理，再考虑每个的答案为多少。
对于第 ii 个方格，设其修改矩阵的左上角的坐标为 (x1i,y1i)(x1_i,y1_i)，右下角的坐标为 (x2i,y2i)(x2_i,y2_i)，修改的颜色为 pip_i。
  • 对于被矩阵覆盖了的部分，答案为 ∑j=x1ix2i∑k=y1iy2ifj,k,pi\sum\limits_{j=x1_i}^{x2_i}\sum\limits_{k=y1_i}^{y2_i}f_{j,k,p_i}
  • 对于没有被矩阵覆盖的部分，答案为 ∑j=1n∑k=1nf2j,k−∑j=x1ix2i∑k=y1iy2if2j,k\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}f2_{j,k}-\sum\limits_{j=x1_i}^{x2_i}\sum\limits_{k=y1_i}^{y2_i}f2_{j,k}
ff，f2f2 都可以前缀和处理，可是 ff 的递推式的时间复杂度是 O(V2nm)\mathcal{O}(V^2nm) 的（其中 VV 表示字符集大小），似乎无法通过这道题。
注意到绝对值是可以动态维护的，所以我们可以正着反着扫一遍，然后处理即可，时间复杂度 O(Vnm)\mathcal{O}(Vnm)（VV 含义同上），具体实现详见代码。
CPP
#include<bits/stdc++.h>
using namespace std;
long long qzh[1005][1005][27],qzh1[1005][1005];
int qzh2[1005][1005][27];
int xx[300005],yy[300005],xxx[300005],yyy[300005],c[300005],a[1005][1005];
long long sum(int x,int y,int u,int v,int col)
{
	return qzh[u][v][col]-qzh[u][y-1][col]-qzh[x-1][v][col]+qzh[x-1][y-1][col];
}
long long sum2(int x,int y,int u,int v)
{
	return qzh1[u][v]-qzh1[u][y-1]-qzh1[x-1][v]+qzh1[x-1][y-1];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char ch;
			cin>>ch;
			a[i][j]=ch-'a'+1;
		}
	}
	for(int i=1;i<=k;i++)
	{
		cin>>xx[i]>>yy[i]>>xxx[i]>>yyy[i];
		char ch;
		cin>>ch;
		c[i]=ch-'a'+1;
		qzh2[xx[i]][yy[i]][c[i]]++;
		qzh2[xxx[i]+1][yyy[i]+1][c[i]]++;
		qzh2[xxx[i]+1][yy[i]][c[i]]--;
		qzh2[xx[i]][yyy[i]+1][c[i]]--;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int p=1;p<=26;p++)
				qzh2[i][j][p]+=qzh2[i-1][j][p]+qzh2[i][j-1][p]-qzh2[i-1][j-1][p];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			long long summ=0,tot=0;//tot记录前面或后面有多少个数，summ记录贡献
			for(int p=1;p<=26;p++)
			{
				qzh[i][j][p]+=summ;
				summ=summ+qzh2[i][j][p]+tot;
				tot+=qzh2[i][j][p];
			}
			summ=0;
			tot=0;
			for(int p=26;p>=1;p--)
			{
				qzh[i][j][p]+=summ;
				summ=summ+qzh2[i][j][p]+tot;
				tot+=qzh2[i][j][p];
			}
			for(int p=1;p<=26;p++)
			{
				qzh[i][j][p]+=(k-tot)*abs(a[i][j]-p);
				qzh1[i][j]+=qzh2[i][j][p]*abs(a[i][j]-p);//记录当前矩阵外的答案的前缀和
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int p=1;p<=26;p++)
				qzh[i][j][p]+=qzh[i-1][j][p]+qzh[i][j-1][p]-qzh[i-1][j-1][p];
			qzh1[i][j]+=qzh1[i-1][j]+qzh1[i][j-1]-qzh1[i-1][j-1];
		}
	}
	long long minn=(long long)1e18,y=0;
	for(int i=1;i<=k;i++)
	{
		long long sum=sum(xx[i],yy[i],xxx[i],yyy[i],c[i])+qzh1[n][m]-sum2(xx[i],yy[i],xxx[i],yyy[i]);
		if(minn>sum)
		{
			minn=sum;
			y=i;
		}
	}
	cout<<minn;
	return 0;
}
记录

评论

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

正在加载评论...