牛客练习赛19 A - 托米的简单表示法

打完比赛...
突然就想水篇文了......

1.png

官方题解给的是DFS或者树形DP...
比赛的时候突然想到的是递归
或者说是模拟栈....Emmm

将问题转化一下 每次计算矩形面积的时候 记录当前矩形"完整的"面积 然后做加和
这样就会得到白色矩形和黑色矩形的面积 做差即可得出最后的图形面积

定义递归体
传入参数为当前矩形的颜色
返回的是当前矩形的长度与宽度
如果当前是最内层的一对括号返回1
否则返回当前括号内的所有括号的长度加和加上当前递归匹配到括号的个数(两个矩形中的间隔),高度为当前递归内最高高度+1

注意下数据范围...当时用Int类型爆了...
改着改着递归就乱了...

Accepted 16ms 5460KB C++

/**
 * @author  Moe_Sakiya      i@tun.moe
 * @date    2018-06-01 20:19:54
 *
 */
  
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
  
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
  
using namespace std;
  
struct Area {
    unsigned long long int width;
    unsigned long long int height;
    Area(void) {
        width = height = 0;
    }
};
  
unsigned long long int blackArea;
unsigned long long int whiteArea;
char str[400005];
unsigned long long int strPtr;
  
Area calArea(unsigned long long int pre) {
    //pre==0 Black else White
    //cout << strPtr << endl;
    Area ret, tmp;
    unsigned long long int blockCnt = 0;
    unsigned long long int width = 0, maxHeight = 0;
    strPtr++;
    while(str[strPtr] != ')') {
        tmp = calArea((pre + 1) % 2);
        if(pre == 0)
            whiteArea += tmp.height * tmp.width;
        else
            blackArea += tmp.height * tmp.width;
        maxHeight = max(maxHeight, tmp.height);
        width += tmp.width;
        blockCnt++;
    }
    if(str[strPtr - 1] == '(') {
        ret.width = 1;
        ret.height = 1;
    } else {
        ret.width = width + 2;
        ret.height = maxHeight + 1;
        if(blockCnt >= 2)
            ret.width += blockCnt - 1;
    }
    strPtr++;
    return ret;
}
  
 int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned long long int n;
    Area ret;
    scanf("%llu", &n);
    getchar();
    while(n--) {
        gets(str);
        gets(str);
        //INIT
        strPtr = 0;
        blackArea = whiteArea = 0;
        while(str[strPtr] != '\0') {
            ret = calArea(0);
            blackArea += ret.height * ret.width;
        }
        printf("%llu\n", blackArea - whiteArea);
    }
    return 0;
}

添加新评论

captcha
请输入验证码