欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018暑期牛客网多校第二场签到题---思维(规律题)

程序员文章站 2023-12-23 15:40:10
...

这道题,有点意思,比赛解束2分钟后,队友把这道题AC了。照他的说法是我的题意没解释清楚,但是题目上的题意就是那样,我也很尴尬。

题意,给你n*n的矩阵,代表停车场,你只能往边界上放车,你在上边界放车,车就会向下走,你在下边界放车,车就会向上走,左边界和右边界,同样如此。边界如何处理呢?

看一张图片

2018暑期牛客网多校第二场签到题---思维(规律题)

2表示n,后面的0表示会有0个陷阱,接下来会给出陷阱的坐标。陷阱的意思是,车走到这里会GG,还有一种GG的方式是两个车相撞了。问最多能放多少辆车。n <= 100000

 

题解:我们不难发现一个陷阱的位置虽然能挡住这一行和这一列的汽车排放,但是我们可以对称一下,就相当于换个位置放车,一样的。

上代码吧。

#include<assert.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define File(S) freopen(S".in","r",stdin);freopen(S".out","w",stdout);
using namespace std;

typedef long long LL;

const int INF=2147483647;

LL getint()
{
    LL res=0,p=1;
    char ch=getchar();
    while ((ch<'0'||ch>'9') && ch!='-') ch=getchar();
    if (ch=='-') p=-1,ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*p;
}

int n,m,ans;
bool S1[100050],S2[100050];

int main()
{
    n=getint();
    m=getint();
	assert(1<=n&&n<=1e5);
	assert(0<=m&&m<=1e5);
    ans=n*2;
    int x,y;
    while (m--) {
        x=getint();
        y=getint();
        if (!S1[x]) {
            S1[x]=1;
            ans--;
        }
        if (!S2[y]) {
            S2[y]=1;
            ans--;
        }
    }
    if (n&1 && !S1[n/2+1] && !S2[n/2+1]) ans--;
    printf("%d\n",ans);
    return 0;
}

 

上一篇:

下一篇: