题目描述

建筑商波奇刚刚完成了她的最新作品：一条精美的巷道。

此巷道由两排瓷砖组成，每排都恰好包含 C
个边长为 1
的白色等边三角形瓷砖。

其中，上排左起第一个三角形瓷砖指向上方，每对相邻三角形瓷砖（即包含公共边的三角形瓷砖）的指向都相反（可参照图例）。

不幸的是，她不小心打翻了一桶黑色油漆，使得其中一些三角形瓷砖被染黑了。

由于被染黑的瓷砖油漆未干，她计划使用胶带将所有染黑区域的边缘围住，以防别人误踩。

请你计算，她需要使用多少米的胶带。

算法1

(枚举) $O(n)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];
int main()
{
    // 数据输入
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i ++)
    {
        cin >> b[i];
    }

    int ans = 0;//存储答案

    for(int i = 1; i <= n; i ++)
    {
        if(a[i])ans += 3;//如果这个位置上被墨水沾到先加上3
        if(i % 2 && a[i])//观察图形，如果是奇数位置上的砖块和他下面，前面，后面的砖块的情况都有关系
        {
            if(a[i - 1])ans --;//和钱面的砖块有一条公共边
            if(a[i + 1])ans --;//和后面的砖块有一条公关边
            if(b[i])ans --;//和下面的砖块有一条
        }
        else if(i % 2 == 0 && a[i])//如果是偶数位置并且有墨水
        {
            if(a[i - 1])ans --;//但是偶数位置上的情况只和她旁边的砖块有联系，左边
            if(a[i + 1])ans --;//右边
        }
    }

    for(int i = 1; i <= n; i ++)//同理同上
    {
        if(b[i])ans += 3;
        if(i % 2 && b[i])
        {
            if(b[i - 1])ans --;
            if(b[i + 1])ans --;
            if(a[i])ans --;
        }
        else if(b[i] && i % 2 == 0)
        {
            if(b[i - 1])ans --;
            if(b[i + 1])ans --;
        }
    }
    cout << ans << endl;
    return 0;
}

```