链接：https://www.nowcoder.com/acm/contest/140/I
来源：牛客网
The first line of input contains two integers n and m(n <= 100000,m <= 100000)
For the next m lines,each line contains two integers x,y(1 <= x,y <= n), denoting the grid which is damaged by White Cloud.
Print a number,denoting the maximum number of cars White Rabbit can put into.
分析：首先看没有陷阱的时候，n*n最多可以在边界上放几辆车，然后再思考加每个陷阱被影响到的行和列。
通过爆搜或者手写所有情况找规律，我们很容易得出n*n的时候边界放的车的奇数的情况为：(n/2)*4+1，偶数的情况为：2*n
每次加陷阱会影响到陷阱所在的行和列，我们分别用两个vis数组保存起来被影响到的行和列。
首先看n为偶数
图为n是偶数的时候，此时n为4，最多可以放车子八辆，八辆车的情况我们可以变成图中这种情况（比如(2,2)我可以直接横移到(2,1)边界处就满足了条件）
然后我们可以发现陷阱处于此图中任何位置都会影响到两辆车，所以n为偶数时候陷阱的位置行和列都将受到影响，我们记录下来就好
接着是n为奇数
图为n为5的时候，最多可以放九辆车，如上面一样可以画成这样的形式。然后我们很容易看出来除了陷阱位于中心点，在其他点都可以影响到两辆车，中心点影响到一辆车。
下面是我的实现代码
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 10000007;
typedef long long ll;
int vis1[maxn] ;
int vis2[maxn] ;
struct node{
int x ;
int y ;
friend bool operator < ( node a , node b ) {
if(a.x != b.x)
return a.x <= b.x ;
return a.y <= b.y ;
}
}e[maxn];
int n , m ;
int main(){
while( scanf("%d %d",&n,&m) != EOF) {
memset(vis1,0,sizeof(vis1)) ;
memset(vis2,0,sizeof(vis2)) ;
long long int sum = n%2 == 0 ? 2*n : (n/2)*4 + 1 ;
for( int i = 1 ; i <= m ; i ++ ){
scanf("%d %d",&e[i].x,&e[i].y) ;
vis1[e[i].x] = 1 ; vis2[e[i].y] = 1 ;
}
long long ans = 0 ;
for(int i = 1 ; i <= n ; i ++) {
if(vis1[i]) ans ++ ;
if(vis2[i]) ans ++ ;
}
if( n%2 && ( vis1[(n + 1)/2] || vis2[(n + 1)/2] ) ) {
ans -- ;
}
printf("%lld\n",sum - ans) ;
}
return 0 ;
}
原文：https://www.cnblogs.com/l609929321/p/9347909.html