2018牛客网暑期ACM多校训练营第二场 I - car（脑洞）

题目链接 https://www.nowcoder.com/acm/contest/140#question

【题目描述】
White Cloud has a square of n*n from (1,1) to (n,n).
White Rabbit wants to put in several cars. Each car will start moving at the same time and move from one side of one row or one line to the other. All cars have the same speed. If two cars arrive at the same time and the same position in a grid or meet in a straight line, both cars will be damaged.
White Cloud will destroy the square m times. In each step White Cloud will destroy one grid of the square(It will break all m grids before cars start).Any car will break when it enters a damaged grid.
White Rabbit wants to know the maximum number of cars that can be put into to ensure that there is a way that allows all cars to perform their entire journey without damage.
(update: all cars should start at the edge of the square and go towards another side, cars which start at the corner can choose either of the two directions)

For example, in a 5*5 square

legal

illegal（These two cars will collide at (4,4)）

illegal (One car will go into a damaged grid)

【输入格式】
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的矩形的边界上*干辆车，所有车从同一时刻出发，以同样的速度，从某一列的一侧开到另一侧或者从某一行的一侧开到另一侧。问最多放多少量车使得存在一种方式，这些车在行驶的过程中互不相撞。（车可以视为质点）
同时还会有若干个格子被损坏车辆不能开进被损坏的格子。
注意：车只能在边界上放置，且方向必须开往对面。

【思路】
先考虑所有格子全部完好的情况，通过爆搜/脑洞，我是画了好多个图才发现答案就是2n-(n mod 2)。或者说n为奇数时答案就是(n/2)×4+1，n为偶数时答案是(n/2)×4。
之后再去考虑有损坏的格子的情况，依然还是分n为奇数和n为偶数两种情况讨论，当n为偶数的时候比较简单，如果有一个损坏的格子，那么这个格子一定挡住最优解中的两辆车，这也是画了好多图找到的规律。当然会有重复的情况，所以要计算的就是这些损坏的格子占用了多少个不同行和不同列，然后用最优解剪掉这个数就是答案。
当n为偶数的时候，如果损坏的格子不在中间那行或那列，就和偶数的情况是一样的，如果在中心的哪一行或列上但不在最中间哪一格的话会挡住至少一辆车。所以这里要算除了最中心的那个点以外所有的损坏点有多少不同行不同列（这里中心行和列不算在内），如果损坏点同时占用了中心行列，那么中心行列上就不能放车了，否则还可以放一辆车，所以要根据这个判断答案是否还要减1.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100050;

int n,m;
int x[maxn],y[maxn];
bool used[maxn];
bool r,c;

int main(){
    while(scanf("%d%d",&n,&m)==2){
        if(n&1){
            r=c=false;
            ll ans=(n/2)*4+1;
            int mid=n/2+1;
            for(int i=1;i<=m;++i){
                scanf("%d%d",&x[i],&y[i]);
                if(x[i]==mid) r=true;
                if(y[i]==mid) c=true;
            }

            int cnt=0;
            memset(used,0,sizeof(used));
            for(int i=1;i<=m;++i){
                if(x[i]==mid && y[i]==mid) continue;
                if(!used[x[i]]) {
                    used[x[i]]=1;
                    if(x[i]!=mid) ++cnt;
                }
            }
            ans-=cnt;
            cnt=0;
            memset(used,0,sizeof(used));
            for(int i=1;i<=m;++i){
                if(x[i]==mid && y[i]==mid) continue;
                if(!used[y[i]]){
                    used[y[i]]=1;
                    if(y[i]!=mid) ++cnt;
                }
            }
            ans-=cnt;
            if(r&&c) --ans;
            printf("%lld\n",ans);
        }
        else{
            ll ans=(n/2)*4;
            for(int i=1;i<=m;++i){
                scanf("%d%d",&x[i],&y[i]);
            }

            int cnt=0;
            memset(used,0,sizeof(used));
            for(int i=1;i<=m;++i){
                if(!used[x[i]]) {
                    used[x[i]]=1;
                    ++cnt;
                }
            }
            ans-=cnt;
            cnt=0;
            memset(used,0,sizeof(used));
            for(int i=1;i<=m;++i){
                if(!used[y[i]]){
                    used[y[i]]=1;
                    ++cnt;
                }
            }
            ans-=cnt;
            printf("%lld\n",ans);
        }
    }
    return 0;
}