【NOIP练习赛】T2、开车

Description

老司机小 Q 要在一个十字路口指挥车队开车，这个十字路口可以描述为一个 n*n 的矩阵，其中第 2 行到第 n-1 行都各有一道横向车道，第 2 列到第 n-1 列都各有一条纵向车道。飙车开始前，小 Q 可以在每条车道的两端（横向车道为从左到右第 1 格和第 n 格，纵向车道为从上到下的第 1 格和第 n 格）安置一辆大卡车。安置结束后，小 Q 可以下令让所有大卡车同时向车道的另一端行驶，所有的卡车速度都相同。小 Q 要合理安排这些卡车，使得它们在行驶过程中不会相撞；另外一些格子上有小 C 放置的巨石，这些格子不能通过卡车。小 Q 希望安置的卡车最多，请你求出最多的卡车数。

Input

第一行两个非负整数 n 和 m，分别表示十字路口大小和巨石数量。接下来 m 行，每行两个正整数 xi,yi，表示在第 xi 行第 yi 列有一个巨石。

对于 20%的数据，n<=5；

对于 40%的数据，n<=10；

对于 70%的数据，n<=1000；

对于 100%的数据，3<=n<=200000，m<=200000。

Output

输出一个整数，表示答案。

Sample Input

4 3

3 1

3 2

3 3

Sample Output

Solution

这本来是道水题的...可是我居然想太多了，唉，菜得不行啊...

首先，我们来分析一下题目...能限制某行某列的车的情况，只有路上有一块石头，或者说当一辆车开到某一时刻时，另一辆车也刚好和它亲密接触

可以用一张图来解释

当这8个位置中有一个位置放了一辆车时，可能互相影响的位置只有图中1,2,3,4,5,6,7.8这8个相对位置

对于每一对这样的8个点，都可以取到如1,5,8,4这样的4个点使得这8个点所在的行列都被取到

那么我们推广一下，其实每行每列只要没有石头，那么都可以放一辆卡车

除了一种特殊情况，就是当n为奇数时，当n/2+1行和n/2+1列都没有石子时，这行这列只能放一辆车，这只须特判一下即可（不懂可以对上面那图yy一下）

讲完了，继续难受去，老司机翻车

 #include<cstdio>

 int count,n,m;

 bool h[],l[];

 int main(){

     int xi,yi;

     scanf("%d%d",&n,&m);

     for (int i=;i<=m;i++) {

         scanf("%d%d",&xi,&yi);

         if (xi!=&&xi!=n) h[xi]=;

         if (yi!=&&yi!=n) l[yi]=;

     }

     for (int i=;i<=n-;i++) if (!h[i]) count++;

     for (int i=;i<=n-;i++) if (!l[i]) count++;

     if (n%==&&!h[n/+]&&!l[n/+]) count--;

     printf("%d",count);

 }

巴特西

【NOIP练习赛】开车