【阶段2】【学校测试】【逆向思维】棋盘

棋盘

(board.cpp/c)

【问题描述】

有一个n*m的棋盘，在初始时刻，棋盘上的每个位置都放有一个白色的棋子。

接下来有q次操作，每次会将某一行或者某一列的棋子染成白色或者黑色。

在所有操作做完后询问这个棋盘上最终有多少个黑色棋子。

【输入格式】

    输入文件名为board.in。

第一行两个整数n,m,q表示棋盘的行数，列数，与操作数。

第二到第q+1行每行三个整数 x,y,z。若x=0则表示对第y行进行操作，若x=1则表示对第y列进行操作。若z=0则表示将该行（列）的棋子都染成白色，若z=1则表示染成黑色。

【输出格式】

    输出文件名为board.out。

    输出文件只有一行，一个整数表示答案。

【输入输出样例】

【数据规模与约定】

对于30% 的数据，满足n,m,q≤1e3。

对于另外30% 的数据，满足 m,q≤1e5,n≤10。

对于100% 的数据，满足n,m,q≤1e6。

对于此类覆盖问题最好的方法是离线操作，从后往前就可以直接解题。

而且想清楚几个要点：

1.若当前行/列在后面也有操作，那么这一次的操作相当于作废。

2.对于行的有效操作，相当于让所有的列残缺了一块，对于列的有效操作，相当于让所有的行残缺了一块。每次染黑当前行/列，增加的黑子数量就是当前行/列非残缺块的格子数量

3.对于一行的操作会影响到所有的列，对于一列的操作会影响到所有的行，所以不用特别开数组去记录每一行每一列的情况，因为所有行和所有列都是同步的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll; 
inline int read()
{
	char c=getchar();int f=1,s=0;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){s=s*10+c-'0';c=getchar();}
	return f*s;
}
int n,m,q;
ll x[1000010],y[1000010],z[1000010];
bool nn[2][1000010];
ll ans;
int main()
{
//	freopen("board10.in","r",stdin);
	n=read();m=read();q=read();
	for(int i=1;i<=q;i++)x[i]=read(),y[i]=read(),z[i]=read();
	ans=0;
	for(int i=q;i>=1;i--)
	{
		if(nn[x[i]][y[i]])continue;
		nn[x[i]][y[i]]=true;
		if(z[i])ans+=x[i]==1?m:n;
		if(x[i]==0)m--;
		else n--;
	}
	printf("%lld\n",ans);
	return 0;	
}

总结本题收获：

1.有的题目（类似于覆盖类的问题）可以考虑从后往前离线操作，从而简化过程

2.思考清楚每一步对整个过程的实际影响，转化题意

3.合并简化可以不用特殊记录的量