栗子栗子

CodeForces761F 解题报告

题目

传送门

啊好久不写题目大意了

给你一个$n \times m$的字母矩阵,然后给你$k$次独立的操作,每次操作是对原矩阵的某一子矩形用给定字符覆盖

并称操作完的新矩阵为特殊矩阵

定义两个矩阵的差别值是对应位置的字母的$ASCII$码的差值绝对值之和

要找一个特殊矩阵,使其和剩余$k-1$个特殊矩阵的差别值之和最小

输出最小值

思路

考虑矩阵神器—二维前缀和

我们先预处理出每个位置被哪些字母覆盖了几次,这个可以使用二分差分,再扫一遍二维前缀和的操作实现

然后预处理出整个原矩阵和所有特殊矩阵的差别值之和

这个可以用上一个得到前缀和以及分字母讨论实现

接下来我们考虑每个位置应该有$k$个字母,分别对应$k$次独立操作之后该未知的字母

用原矩阵的字母对所有位置进行补全

然后枚举每一次操作

对于当前操作,我们可以在$O(1)$的时间内求得未被覆盖区域对其它特殊矩形的差别值之和

然后对于被覆盖矩形,我们考虑这个矩形内的字母都是一样的

然后也得到了所有特殊矩阵所有位置的情况,进行计算即可

总复杂度$O(26 \times n \times m+26 \times k)$

同时还有不小的常数,但是整体复杂度比较OK,最终$4000ms$的时限我跑了$2511ms$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
LL sum[1005][1005][27];
LL tot[1005][1005][27];
char s[1005][1005];
struct node
{
int x1,y1,x2,y2;
int c;
}a[300005];
int m,n,q;

void add(int x1,int y1,int x2,int y2,int nu)
{
tot[x1][y1][nu]++;
tot[x1][y2+1][nu]--;
tot[x2+1][y1][nu]--;
tot[x2+1][y2+1][nu]++;
}

void cal_pre_sum(LL t[1005][1005][27])
{
for(int k=1;k<=26;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
t[i][j][k]+=t[i][j-1][k];
for(int k=1;k<=26;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
t[i][j][k]+=t[i-1][j][k];

}

LL cal_area_sum(int x1,int y1,int x2,int y2,int nu)
{
if(x1>x2 || y1>y2)return 0;
x1--;y1--;
return sum[x2][y2][nu]+sum[x1][y1][nu]-sum[x1][y2][nu]-sum[x2][y1][nu];
}

LL cal_area_tot(int x1,int y1,int x2,int y2,int nu)
{
if(x1>x2 || y1>y2)return 0;
x1--;y1--;
return tot[x2][y2][nu]+tot[x1][y1][nu]-tot[x1][y2][nu]-tot[x2][y1][nu];
}

LL cal_others(int x1,int y1,int x2,int y2)
{
LL u=0;
u+=cal_area_sum(1,1,n,y1-1,0);
u+=cal_area_sum(1,y2+1,n,m,0);
u+=cal_area_sum(1,y1,x1-1,y2,0);
u+=cal_area_sum(x2+1,y1,n,y2,0);
return u;
}

int main()
{
scanf("%d%d%d\n",&n,&m,&q);
for(int i=1;i<=n;i++)gets(s[i]+1);
for(int i=1;i<=q;i++)
{
char cc;
scanf("%d %d %d %d %c",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&cc);
a[i].c=cc-96;
add(a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[i].c);
}
cal_pre_sum(tot);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=26;k++)
sum[i][j][k]=((LL)abs(s[i][j]-96-k))*tot[i][j][k];
cal_pre_sum(sum);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=26;k++)
{
sum[i][j][0]+=sum[i][j][k];
tot[i][j][0]+=tot[i][j][k];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
tot[i][j][s[i][j]-96]+=q-tot[i][j][0];
cal_pre_sum(tot);
LL daan=1e18;
for(int i=1;i<=q;i++)
{
LL ans=0;
ans+=cal_others(a[i].x1,a[i].y1,a[i].x2,a[i].y2);
for(int j=1;j<=26;j++)ans+=((LL)abs(a[i].c-j))*cal_area_tot(a[i].x1,a[i].y1,a[i].x2,a[i].y2,j);
daan=min(daan,ans);
}
printf("%lld",daan);
return 0;
}