引言

这个题一开始走了弯路，所以尝试的次数是所有题目中最多的，特此记录一下各种尝试的过程。

题目描述

N X N的国际象棋棋盘上有K个车,第i个车位于第Ri行，第Ci列。求至少被一个车攻击的格子数量。
车可以攻击所有同一行或者同一列的地方。

第一次尝试 暴力枚举

这道题我最先想到的就是 暴力枚举
声明一个char二维数组，输入棋子的位置，把棋子的位置标记成'*'，把棋子能攻击的位置全部改成'y'，再遍历数组，统计'y'的个数，然后输出。

#include<iostream>
using namespace std;

char a[10005][10005] = {0};

int main()
{
	long long sum = 0;
	int n = 0, k = 0, x = 0, y = 0;
	
	cin >> n >> k;
	
	for(int i = 0; i < k; i++)
	{
		cin >> x >> y;
		a[x - 1][y - 1] = '*';//把棋子标记为“*”
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(a[i][j] == '*')
			{
				for(int q = 0; q < n; q++)
				{
					if(a[i][q] != '*')
					{
						a[i][q] = 'y';//棋子可以攻击到的地方就标记为“y”(yes)
					}
				}
				for(int q = 0; q < n; q++)
				{
					if(a[q][j] != '*')
					{
						a[q][j] = 'y';
					}
				}
			}
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(a[i][j] == 'y' || a[i][j] == '*')
			{
				sum++;//统计
			}
		}
	}
	
	cout << sum;
	
	return 0;
}

对了3个，剩下全是Runtime Error，检查了一下发现原因是数组越界，而10000*10000的二维数组已经是极限，再大就会报错，所以这种方法不行

第二次尝试

既然暴力不成，那就要想数学方法：
先只看行，只要一行内有棋子，那么无论有几颗棋子，他们的攻击范围都是一行；
列也类似，只要避免不要和行重复就行了。
再通过桶标记，用N乘true的个数再输出就行了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;

bool jx[1000000010] = {0}, jy[1000000010] = {0};

int main()
{
	long long n = 0, k = 0, x = 0, y = 0, sum = 0, cnt = 0;
	
	cin >> n >> k;
	
	for(long long i = 0; i < k; i++)
	{
		scanf("%lld%lld", &x, &y);
		jx[x] = 1;
		jy[y] = 1;//桶标记
	}
	
	for(long long i = 1; i <= n; i++)
	{
		if(jx[i] != 0)
		{
			sum = sum + n;
			cnt++;//行的攻击范围
		}
	}
	
	for(long long i = 1; i <= n; i++)
	{
		if(jy[i] != 0)
		{
			sum = sum + n - cnt;//列的攻击范围，为了不与行重复所以使用cnt
		}
	}
	
	cout << sum;
	
	return 0;
}

改好后对了7个，剩下3个内存超限。
同上个做法一样，10^9太大，所以125兆的内存也抗不住用，这个方法还是不行

第三次尝试

继上一个数学方法后第二种数学方法
上一个直接在计算列的时候就进行了去重，这次是在把攻击范围全部计算好之后再去重。
总攻击范围(不去重)应该就是：xcnt(x轴总边数) * n + ycnt(y轴总边数) * n（n是棋盘边长）
而假设棋盘边长为5，有两枚棋子，分别在（1，1）和（5，5），那么我们是这样计算攻击的：

第一步：

第二步：

（深蓝为重复攻击处）
重复攻击处的个数好像就是 xcnt * ycnt 啊！
那么只需要用 xcnt * n + ycnt * n - xcnt * ycnt 就行了。

具体细节（去重，统计）见代码：

#include<iostream>
#include<cstdio>
using namespace std;

long long jx[1000005] = {0}, jy[1000005] = {0};

bool find(long long a[], long long i, long long x);

int main()
{
	long long n = 0, k = 0, sum = 0, xcnt = 0, ycnt = 0, x = 0, y = 0;
	
	cin >> n >> k;
	
	for(long long i = 0; i < k; i++)
	{
		scanf("%lld%lld", &x, &y);
		if(i == 0)
		{
			jx[i] = x;
			jy[i] = y;
		}
		else//寻找前面有没有和当前的重复的，没有再放进数组（其实就是去重）
		{
			if(find(jx, i, x))
				jx[i] = x;
			if(find(jy, i, y))
				jy[i] = y;
		}
	}
	
	for(int i = 0; i < k; i++)
	{
		if(jx[i] != 0)
		{
			xcnt++;//统计行
		}
		if(jy[i] != 0)
		{
			ycnt++;//统计列
		}
	}
	
	sum = xcnt * n + ycnt * n - xcnt * ycnt;//用公式计算
	
	cout << sum; 
	
	return 0;
}

bool find(long long a[], long long i, long long x)
{
	bool rt = false;
	int j = 0;
	while(j < i)
	{
		if(x == a[j])
		{
			break;
		}
		j++;
	}
	if(j == i)
	{
		rt = true;
	}
	
	return rt;
}
这个终于AC了