牛客练习赛19

链接：https://www.nowcoder.com/acm/contest/111/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

作为故事主角的托米是一名老师。

一天，他正在为解析算术表达式的课程准备课件。在课程的第一部分，他只想专注于解析括号。他为他的学生发明了一个有趣的正确括号序列的几何表示，如下图所示:

几何表示的定义：

对于一个括号序列A，我们定义g(A)是A的几何表示形式,则

"()"的表示是一个1*1的方块，高度为1;

2.对于一个括号序列A，"(A)"的表示是由一个比g(A)宽2个单位高1个单位的矩形包围g(A)，它的高度为A+1;
3.对于两个括号序列A和B，A+B的几何表示形式为把g(B)放置在g(A)右边的一个单位，且高度为A和B的高度的较大值。
其中+指的是字符串的连接符。

在完成课件后，托米老师开始玩他做好的图片。他将图像的有限区域交替地涂成黑色和白色，使最外面的区域全部涂成黑色。对于上面的例子，这个着色如下所示：

现在给你一个合法的括号序列。请计算颜色为黑色的区域的面积。

输入描述:

输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由一个合法括号序列组成。每行只包含字符'('和')'。

输出描述:

对于每个测试用例，输出一行包含一个整数,表示相应几何表示的黑色部分的面积。

示例1

输入

复制

((()))

(())(()(()))

输出

复制

说明

第二个测试案例是上图中显示的案例。

备注:

1≤T≤10

一个合法括号序列长度≤4 x 10⁵

这题主要是处理三个问题一个是长方体的高度，一个长度，白色还是黑色。

首先预处理，颜色，和高度

颜色，判断是第几个奇偶就行了，第一个肯定是黑色，第二个就是白色。

注意处理的时候每匹配一个’)’ 数量就要减1；

长方体的高，用一棵树就行了，然后每个‘（’的度就是每个长方形的高度。

长度容易处理直接找到匹配的括号直接距离 -1 就是长方体长度

我用栈来保存 ‘（’的位置。

遇见’(’压入栈，遇见‘)’弹出，计算距离。如果是白色就是减去这个长方形的面积，黑色就加上。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const long long mod=1e9+7;
const int maxn=1e7+25;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int a[maxn];
int p[maxn],b[maxn];

char ch[maxn];
int n;
stack<int> s;

int main() {
    scanf("%d",&n);
    while(n--) {
        scanf("%s",ch);
        int l=strlen(ch);
        a[0]=1;
        int x=1,y=0;
        p[0]=-1;
        b[0]=1;
        int k=0;
        for(int i=1; i<l; i++) {
            if(ch[i]=='(') {
                a[i]=a[i-1]+1;
                p[i]=k;
                k=i;
                b[k]=1;
            } else {
                b[p[k]]=max(b[p[k]],b[k]+1);
                k=p[k];
                a[i]=a[i-1]-1;
            }
        }
//        for(int i=0;i<l;i++)
//            printf("%d%c",b[i],i+1==l?'\n':' ');
        long long flag=1,sum=0;
        for(int i=0; i<l; i++) {
            if(ch[i]=='(') {
                s.push(i);
            }
            else {
                int k=s.top();
                s.pop();
                if(a[k]%2==1)sum=sum+(i-k)*(b[k]);
                else sum-=(i-k)*(b[k]);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

E ：F 这两题就不废话了签到题

链接：https://www.nowcoder.com/acm/contest/111/E来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld

题目描述

好了，现在是小托米的故事啦~~~

可爱的小托米得到了n瓶饮料.

但他不小心把开盖的工具弄丢了,所以他只能利用饮料瓶来开盖. 已知第i个瓶子的品牌为a _i ,且其能打开b _i 品牌的瓶子. 问有几瓶饮料托米无法喝到. 被用于打开饮料瓶的瓶子不一定需要被打开. 一个瓶子不能打开其本身.

输入描述:

第一行一个整数n,表示饮料的瓶数.
接下来n行,每行两个整数a_i,b_i.

输出描述:

输出一行一个整数,表示小托米无法喝到的饮料瓶数.

题目描述

输入描述:

输出描述:

相关文章