打卡信奥刷题（2985）用C++实现信奥题 P6070 『MdOI R1』Decrease

P6070 『MdOI R1』Decrease

题目描述

给定一个n×nn \times nn×n的矩阵，你可以进行若干次操作。

每次操作，你可以将一个k×kk \times kk×k的连续子矩阵里的所有数全都加上111或者全都减去111。

初始时，矩阵中有mmm个位置上的数不为000，其它位置上的数均为000。

请你求出至少需要多少次操作，可以将矩形中所有数都变为000。

输入格式

第一行三个整数n,m,kn,m,kn,m,k，分别表示矩阵大小，非000格数和每次修改的连续子矩阵大小。

接下来mmm行，每行三个整数x,y,zx,y,zx,y,z，表示初始时矩阵的第xxx行第yyy列上的数为zzz。

输出格式

一行一个整数，表示最少操作次数。

特别地，如果无法使矩阵中所有数都变为000，输出-1。

输入输出样例 #1

输入 #1

4 14 3 1 1 1 1 2 1 1 3 1 2 1 1 2 2 3 2 3 3 2 4 2 3 1 1 3 2 3 3 3 3 3 4 2 4 2 2 4 3 2 4 4 2

输出 #1

3

输入输出样例 #2

输入 #2

3 1 2 1 1 1

输出 #2

-1

输入输出样例 #3

输入 #3

4 5 1 1 1 5 2 2 -3 2 3 -4 3 3 1 4 4 2

输出 #3

15

说明/提示

【样例 1 解释】:

给出的矩阵为：

1 1 1 0 1 3 3 2 1 3 3 2 0 2 2 2

具体步骤：

先将以第一行第一列为左上角的连续子矩阵执行减 1 操作一次；

再将以第二行第二列为左上角的连续子矩阵执行减 1 操作两次。

总共三次。

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0 1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0 0 2 2 2 0 2 2 2 0 1 1 1 0 0 0 0

【样例 2 解释】：

给出的矩阵为：

1 0 0 0 0 0 0 0 0

只通过2×22\times 22×2的连续子矩阵操作不可能使得所有格子上的数都变为000。

【数据范围】

本题采用捆绑测试。

对于所有数据，1≤n≤5×1031\leq n\leq 5\times 10^31≤n≤5×103，1≤m≤min⁡(n2,5×105)1\leq m\leq \min(n^2,5\times 10^5)1≤m≤min(n2,5×105)，1≤k≤min⁡(n,103)1\leq k\leq \min(n,10^3)1≤k≤min(n,103)，1≤x,y≤n1\leq x,y\leq n1≤x,y≤n，每对(x,y)(x,y)(x,y)至多出现一次，1≤∣z∣≤1091 \le |z| \leq 10^91≤∣z∣≤109。

数据保证如果有解，答案不超过263−12^{63}-1263−1。

【提示】

本题读入量较大，建议使用较快的读入方式。

C++实现

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,k,ans;//记得一定要开 long long。longlonga[5005][5005],d[5005][5005];voidf(intx,inty,intc){if(x+k>n+1||y+k>n+1){cout<<"-1";exit(0);}//特判，这个相当于是题目中说的无法修改完。d[x][y]-=c;//差分大纲。d[x+k][y]+=c;d[x][y+k]+=c;d[x+k][y+k]-=c;}intmain(){cin>>n>>m>>k;for(inti=1;i<=m;i++){intx,y,z;scanf("%d%d%d",&x,&y,&z);a[x][y]=z;}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+d[i][j];//前缀和longlongt=d[i][j]+a[i][j];if(t){ans+=abs(t);f(i,j,t);}}}cout<<ans;//完美结束~return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容