【c++差分数组】P9583涂色

本文涉及知识点

C++差分数组

P9583涂色

n行m列方格纸，初始是白色(0层)。共涂色q次，每次选择一行或一列，将这行或列涂一层颜色。如果某次涂色后，某个单格是k层颜色，则涂为白色(0层）。求最后被涂色的单格数量。color[i] = {typei,xi},typei为1，给xi行涂色。typei为2，给xi列涂色。xi从1开始。
1 <=m,n <=2e5 1 <= k <= q <=5e5

差分数组

rcnt[i]记录，按行涂i次的行数。i $\in$ [0,n]。
ccnt[i]记录，按列涂i次的列数。i $\in$ [0,m]。
计算rcnt的过程
rtmp[i]记录，第i行被涂的次数。i $\in$ [0,n)。
计算ccnt类似。
每次涂色后，将k层颜色涂成0层。等同于结束后，将k的倍数层颜色涂成0层。故只需要记录被涂次数%k。

分类讨论

某行按行涂0次，则本行符合条件的单格数：ccnt[1…m]-cnt[k]
令某行被涂 x次，x > 0 则当前行符合单格数：
$\begin{cases} m - cnt[k-x] && k-x >=0 \\ m && other\\ \end{cases}$

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>#include <bitset>
using namespace std;class Solution {public:long long Cal(const int R, const int C, const int K, vector<vector<int>>& color) {vector<int> rtmp(R), ctmp(C);for (const auto& v : color) {if (1 == v[0]) {rtmp[v[1] - 1]++;}else {ctmp[v[1] - 1]++;}}auto ToCnt = [&](const vector<int>& tmp) {vector<int> ret(K);for (const auto& n : tmp) {ret[n % K]++;};return ret;};auto rcnt = ToCnt(rtmp);auto ccnt = ToCnt(ctmp);long long ret =0;//按行涂0次for (int i = 0; i < rcnt.size(); i++) {ret += ((long long)C - ccnt[(K - i) % K]) * rcnt[i];}return ret;}};int main() {//freopen("./a.in", "r", stdin);//freopen("./output.txt", "a", stdout);int R,C,Q1,K;scanf("%d%d%d%d", &R, &C, &Q1, &K);vector<vector<int>> color(Q1,vector<int>(2) );	for (int i = 0; i < Q1; i++) {scanf("%d%d", &color[i][0],&color[i][1]);}	auto res = Solution().Cal(R, C, K, color);printf("%lld", res);return 0;
}

单元测试

int R, C, K;vector<vector<int>> color;TEST_METHOD(TestMethod1){R = 2, C = 3, K = 2, color = { {1,1},{1,2},{1,1} };auto res = Solution().Cal(R,C,K,color);AssertEx(3LL, res);}TEST_METHOD(TestMethod2){R = 2, C = 3, K = 2, color = { {1,1},{2,1} };auto res = Solution().Cal(R, C, K, color);AssertEx(3LL, res);}TEST_METHOD(TestMethod3){R = 2, C = 3, K = 2, color = { {2,1},{2,2},{2,3} };auto res = Solution().Cal(R, C, K, color);AssertEx(6LL, res);}TEST_METHOD(TestMethod11){R = 3, C = 4, K = 3, color = { {1, 3}, { 2,4 }, { 1,2 }, { 1,3 }, { 2,2 } };auto res = Solution().Cal(R, C, K, color);AssertEx(8LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功