列表

详情

NC25118. 291045 / 克洛涅的照片

描述

孩子当中出了一个内奸。这怎么办呢？Sister 偷偷给了艾玛一张照片，而这张照片上的人就是内奸。
可是，这张照片被模糊了。形式化地，我们将这张照片划分为一个 n 行 m 列的网格，其中行从上到下标号为 1 至 n ，列从左到右编号为 1 至 m 。其中有 k 个格子被模糊了。由于信息被分散在每一个格子中，艾玛他们必须要通过一些操作最终使这张照片上没有任何一个格子被模糊时才能知晓内奸的真面目。可行的操作是：将这张照片上的某一行或某一列中的所有格子，把模糊的变为不模糊的，把不模糊的变为模糊的。
换句话说，如果让令 表示照片上格子 (i, j) 的状态，其中如果这个格子被模糊，那么 ；否则 。每次操作就是选择一行或一列做取反操作。
艾玛想知道，对于一张给出的照片，最少几次操作可以使所有格子都变成不模糊的？
活泼好动的艾玛对这个问题很感兴趣。所以她还想知道，如果对这张照片进行修改，那么得到的新照片的答案又是多少？
具体来说，艾玛会对照片进行 q 次修改。每次修改会选择一行或一列做取反操作。每次修改结束后，你都需要输出一个答案。
数据保证始终有解。

输入描述

第一行包含四个整数 n, m, k, q 。意义见题面描述。
接下去 k 行，每行包含两个正整数  ，表示被模糊的格子坐标。保证 k 个坐标两两不同。
再接下去 q 行，每行两个整数  ，表示一次修改。当 op=0 时，取反第 x 行；当 op=1 时，取反第 x 列。

输出描述

输出共包含 q+1 行。每行一个整数。第一行表示未进行修改时的答案；之后 q 行每行对应一次操作后的答案。

示例1

输入: 

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

输出: 

2
3
2

说明:

初始时，照片状态为 \begin{array}{|c|c|c|} \hline 0 & 0 & 1 \\ \hline 1 & 1 & 0 \\ \hline 0 & 0 & 1 \\ \hline \end{array} ，此时取反第 2 行再取反第 3 列即可。答案为 2 。
第一次修改是取反第 1 行。之后照片变为 \begin{array}{|c|c|c|} \hline 1 & 1 & 0 \\ \hline 1 & 1 & 0 \\ \hline 0 & 0 & 1 \\ \hline \end{array} ，此时依次取反第 1 行、第 2 行以及第 3 列即可。答案为 3 。
第二次修改是取反第 3 行，之后照片变为 \begin{array}{|c|c|c|} \hline 1 & 1 & 0 \\ \hline 1 & 1 & 0 \\ \hline 1 & 1 & 0 \\ \hline \end{array} ，此时只需要取反第 1 列和第 2 列即可。答案为 2 。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 74ms, 内存消耗: 9548K, 提交时间: 2019-05-23 20:00:34 

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=1e6+5;
int n,m,k,q,a[N],b[N],A,B,rev;
int main(){
	n=gi();m=gi();k=gi();q=gi();
	for(int i=1;i<=k;++i){
		int x=gi(),y=gi();
		if(x==1)b[y]=1,++B;
		if(y==1)a[x]=1;
	}
	for(int i=1;i<=n;++i)A+=a[i]^a[1];
	printf("%d\n",min(A+B,n+m-A-B));
	while(q--){
		int x=gi(),y=gi();
		if(x&1)B-=b[y]^rev,b[y]^=1,B+=b[y]^rev;
		else if(y==1)a[1]^=1,B=m-B,rev^=1,A=n-1-A;
		else A-=a[y]^a[1],a[y]^=1,A+=a[y]^a[1];
		printf("%d\n",min(A+B,n+m-A-B));
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 112ms, 内存消耗: 9836K, 提交时间: 2019-05-10 22:19:06 

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
typedef long long ll;
using namespace std;   // lyt
int a,b,c,N,M,K,Q,ans,qx[1000007],qy[1000007];
int main ()
{
	scanf("%d%d%d%d",&N,&M,&K,&Q);
	rep(i,1,K){
		scanf("%d%d",&a,&b);
		if (b==1) qx[a]^=1;
		if (a==1){
			qy[b]^=1;
			if (b==1) rep(j,1,N) qx[j]^=1;
		}
	}
	rep(i,1,N) if (qx[i]) ans++;
	rep(j,1,M) if (qy[j]) ans++;
	c=1;
	if (N+M-ans<ans) ans=N+M-ans,c=-c;
	printf("%d\n",ans);
	rep(i,1,Q){
		scanf("%d%d",&a,&b);
		if (a==0){
			if (!qx[b]) ans+=c,qx[b]=1;
			else ans-=c,qx[b]=0;
		}
		else{
			if (!qy[b]) ans+=c,qy[b]=1;
			else ans-=c,qy[b]=0;
		}
		if (N+M-ans<ans) ans=N+M-ans,c=-c;
		printf("%d\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com