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输入 #14 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输出 #13输入输出样例 #2输入 #23 1 2 1 1 1输出 #2-1输入输出样例 #3输入 #34 5 1 1 1 5 2 2 -3 2 3 -4 3 3 1 4 4 2输出 #315说明/提示【样例 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。【数据范围】本题采用捆绑测试。子任务编号n≤n\leqn≤k≤k\leqk≤分值110310^310311111220202020202014310010010010010010017410310^310310310^31033455×1035\times 10^35×10310310^310324对于所有数据1≤n≤5×1031\leq n\leq 5\times 10^31≤n≤5×1031≤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实现#includebits/stdc.husingnamespacestd;longlongn,m,k,ans;//记得一定要开 long long。longlonga[5005][5005],d[5005][5005];voidf(intx,inty,intc){if(xkn1||ykn1){cout-1;exit(0);}//特判这个相当于是题目中说的无法修改完。d[x][y]-c;//差分大纲。d[xk][y]c;d[x][yk]c;d[xk][yk]-c;}intmain(){cinnmk;for(inti1;im;i){intx,y,z;scanf(%d%d%d,x,y,z);a[x][y]z;}for(inti1;in;i){for(intj1;jn;j){d[i][j]d[i-1][j]d[i][j-1]-d[i-1][j-1]d[i][j];//前缀和longlongtd[i][j]a[i][j];if(t){ansabs(t);f(i,j,t);}}}coutans;//完美结束~return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容