P9302 三角烷

Yun_Mengxi · 2023-04-30 12:39:55 · 题解

[题目传送门]

[推销博客]

[题意分析]

显然的，单独的一个黑色三角形需要 3 米栅栏，而对于有相邻的黑色三角形的黑色三角形来说，肯定只需要把不相邻的边围上栅栏就行了，所以需要的栅栏为三条边去掉相邻的边之后剩下的边数米。

而怎么判断相邻呢？分为两种情况：

• 第一种，当前的三角形尖端朝外（也就是下标为奇数），那么就需要判断上（下）、左、右三个方向相不相邻。

• 第二种，当前的三角形尖端朝内（也就是下标为偶数），那么就需要判断左右，因为尖端是不需要围栅栏的。

• 如果当前下标为 1（或 C），不需要进行特殊处理，因为左边（或右边）默认是白色三角形，不影响答案。

直接把上下两个数组扫一遍，判断相邻就可以了，时间复杂度 \text{O(C)}。

[代码]

如下（复制可以获得尊贵的棕名和高贵的 Tag，马蜂奇特，见谅）：

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
#define endl '\n'
using namespace std;

//Int:
int c;
int a[200005];
int b[200005];
int ans=0;

//Func:
inline int read(){ //丑恶快读（
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
signed main(){
    //Code:
    c=read();
    For(i,1,c) a[i]=read();
    For(i,1,c) b[i]=read();
    For(i,1,c) //扫一遍 a 数组
    {
        if(i%2==1&&a[i]) //第一种情况
        {
            ans+=3; //假设为单独的三角形
            if(a[i-1]) //如果左边相邻
            {
                ans--;
            }
            if(a[i+1]) //如果右边相邻
            {
                ans--;
            }
            if(b[i]) //如果下面相邻
            {
                ans--;
            }
        }
        if(i%2==0&&a[i]) //第二种情况
        {
            ans+=3;
            if(a[i-1]) //左边不相邻
            {
                ans--;
            }
            if(a[i+1]) //右边不相邻
            {
                ans--;
            }
        }
    }
    For(i,1,c) //扫一遍 b 数组
    {
        if(i%2==1&&b[i]) //第一种情况
        {
            ans+=3;
            if(b[i-1]) //如果左边相邻
            {
                ans--;
            }
            if(b[i+1]) //如果右边相邻
            {
                ans--;
            }
            if(a[i]) //如果下面相邻
            {
                ans--;
            }
        }
        if(i%2==0&&b[i]) //第二种情况
        {
            ans+=3;
            if(b[i-1]) //左边相邻
            {
                ans--;
            }
            if(b[i+1]) //右边相邻
            {
                ans--;
            }
        }
    }
    cout<<ans<<endl; //输出答案
    return 0;
}

[AC 记录]