湘潭大学湘大 XTU OJ 1271 Color 题解（非常详细）-Toy模板网

这篇具有很好参考价值的文章主要介绍了湘潭大学湘大 XTU OJ 1271 Color 题解（非常详细）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接

1271

题面

题目描述

Alice在玩一个游戏，她在一个m×n的格子里，随机涂黑k个格子。然后她每次可以把一行或者一列的格子染成红色，但是这一行中不能有黑色的格子。请问她最多能把多少个格子涂成红色？

输入

第一行是一个整数T(T≤100)，表示样例的个数。每个样例的第一行是m(1≤m≤100),n(1≤n≤100),k(0≤k≤m×n)。以后的k行,每行两个整数x(1≤x≤m),y(1≤y≤n)，表示(x,y)为黑色格子。

输出

每行输出一个样例的结果。

样例输入

样例输出

代码

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
	int t;
	scanf("%d",&t);
	
	while(t--)
	{
		int m,n,k;
		scanf("%d%d%d",&m,&n,&k);
		
		int arr1[110],arr2[110];
		memset(arr1,0,sizeof(arr1));
		memset(arr2,0,sizeof(arr2));
		int a,b;
		for(int i=1;i<=k;i++)
		{
			scanf("%d%d",&a,&b);
			arr1[a]=1,arr2[b]=1;
		}
		
		int cnt1=0,cnt2=0;
		for(int i=1;i<=m;i++)	if(!arr1[i])	cnt1++;
		for(int i=1;i<=n;i++)	if(!arr2[i])	cnt2++;
		
		printf("%d\n",cnt1*n+cnt2*m-cnt1*cnt2);
	}
	
	return 0;
}

总结

1.把没有黑色格子的行和列的数目统计出来，求一个和，然后减去重合的部分即可

2.for循环可以从0开始计数，也可以从1开始计数，有时候从1开始计数方便一些，所以这道题目从1开始计数的，因为我们表示格子的坐标，由题意可以知道是从（1，1）开始的

3.使用两个一维数组来存放横坐标和纵坐标，把输入的数字作为数组下标（注意为了防止发生边界错误，把数组稍微开大一些），相应的数值标记为1

4.在标记之前把数组初始化为0了。遍历行和列，把没有被标记的数目求出来

5.按照1的公式输出答案

参考

2022年C语⾔作业8题解

湘潭大学湘大 XTU OJ 1271 Color 题解（非常详细）,算法竞赛,湘大 XTU OJ,算法,c++,开发语言