题解：CF333B Chips

原题传送门

题目大意：

有一个 $n \times n$ 的棋盘，$m$ 个格子是障碍物，然后移动芯片使它们返回到初始对边位置，不能经过障碍物、重叠或交换位置。问最多可以放置多少个芯片完成游戏。

思路：

本题直接按题意模拟即可：

1. 使用桶记录障碍，$a_i$ 代表第 $i$ 行的芯片个数，同理 $b_i$ 代表第 $i$ 列的芯片个数。

2. 如果第 $i$ 行或第 $j$ 没有芯片，$cnt+1$。

3. 如果相遇，就是 $n$ 为奇数且中间行且列有值，$cnt-1$。

下面是样例 $3$ 的解释：

	列1	列2	列3	列4
行1	无芯片	可放芯片	可放芯片	无芯片
行2	放芯片	______	______	放芯片
行3	障碍物	障碍物	障碍物	可放芯片
行4	无芯片	可放芯片	可放芯片	无芯片

行2的两个芯片可以连通，$cnt=1$。

没有相遇情况，输出 $1$。

上代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,a[100005],b[100005],cnt;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        a[x]++,b[y]++;
        //a[i] 是行，b[i] 是列。
    }
    for(int i=2;i<n;i++) cnt+=(!a[i])+(!b[i]); //不懂？看下面↓
    // a[i] 如果是空的，cnt+1。
    // b[i] 如果是空的，cnt+1。
    cout<<cnt-((n%2==1)&&!a[n/2+1]&&!b[n/2+1]);
    //如果相遇答案 -1。
    return 0;
}

括号的意思：如果括号里面的的表达式为 $true$ ，返回 $1$ ，否则返回 $0$。