I.car
车只能从一边走到另一边,而且车和车不能相撞,车也不能走到坑里。所以直接找规律,如果没有坑,最多能放多少辆车。就会发现,关于对角线对称的两边只能放一辆车,如果是奇数个的时候,中间的行和中间的列的长度是相等的,只能在行或者列放一辆车。所以得到公式为:
奇数的时候为(n-2)*2+3=2*n-1,偶数的时候为(n-2)*2+4。
而且一般情况下,有一个坑就要减少两辆车。但是因为一行一列的只算一次就可以,所以直接标记所有的坑一共占了几行几列,然后去掉的就是行数+列数,然后奇数的时候特判一下中间的行和列就可以,占了中间的行或者列的就要少减少一辆。
比赛的时候直接嘴巴型选手,我一边说,队友一边敲的代码。
队友代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+,mod=1e9+,inf=0x3f3f3f3f;
typedef long long ll;
int main()
{
int n,m;
int ans;
while(cin>>n>>m)
{
map<int,int> c,r;
int u,v;
while(m--)
{
cin>>u>>v;
c[u]=,r[v]=;
}
if(n%==)
{
int ans=n*;
int temp=(int)c.size()+(int)r.size();
cout<<ans-temp<<endl;
}
else
{
int ans=n*-;
int temp=(int)c.size()+(int)r.size();
if(c[(n+)/]||r[(n+)/])
{
temp-=;
}
cout<<ans-temp<<endl;
} }
}