牛客训练赛19之托米专场

托米的简单表示法

题目描述

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

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

几何表示的定义：

1. 对于一个括号序列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的高度的较大值。其中+指的是字符串的连接符。

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

输入描述:

1
2
3

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

输出描述:

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

示例1

输入

复制

2

((()))

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

输出

复制

1
2

10
20

说明

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

备注:

1 2	1≤T≤10 一个合法括号序列长度≤4 x 105

题解

这道题提交了好多次，一直WA。后来改成long long就过了。原理很简单，就是遇见左括号入栈，遇见右括号出栈。在入栈出栈时执行操作。先入栈的高度比后入栈的最高高度要高1，初始宽度为1，每执行一次出栈操作，出栈元素前一个元素的宽度等于他自身宽度加上出栈元素宽度再加1。而出栈元素的面积等于宽乘高减去包含元素的面积。就这样，每次出栈时，前一个元素宽度加上该元素宽度加1，前元素将要减去的面积area等于出栈元素的面积minu。而出栈元素的面积area等于高乘宽减去将要减去的面积minu。最终由于0位置没有面积，就是全域，那他的minu即将要减去的面积就是总面积。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200010;
char str[maxn*2];
ll high[maxn],wed[maxn],area[maxn],minu[maxn],mystack[maxn];
ll fun(){
    int cnt = 1,head = 1,tail = 1,len = strlen(str);
    memset(high,0,sizeof(high));
    memset(wed,0,sizeof(wed));
    memset(minu,0,sizeof(minu));
    memset(mystack,0,sizeof(mystack));
    for(int i = 0;i < len;i++){
        if(str[i] == '('){
            mystack[tail++]=cnt++;
            high[mystack[tail - 1]]++;
            wed[mystack[tail - 1]] = 1;
            if(high[mystack[tail - 2]] <= high[mystack[tail - 1]])
                high[mystack[tail - 2]] = high[mystack[tail - 1]] + 1;
        }
        else if(str[i] == ')'){
            if(tail > 1){
                if(high[mystack[tail-2]] <= high[mystack[tail-1]])
                    high[mystack[tail-2]] = high[mystack[tail-1]] + 1;
                tail--;
                wed[mystack[tail - 1]] += wed[mystack[tail]] + 1;
                area[mystack[tail]] = wed[mystack[tail]] * high[mystack[tail]] - minu[mystack[tail]];
                minu[mystack[tail - 1]] += area[mystack[tail]];
            }
        }
    }
    return minu[0];
}
int main(){
    int T;
    cin >> T;
    while(T--){
        scanf("%s",str);
        cout << fun() << endl;
    }
    return 0;
}

托米的饮料

题目描述

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

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

但他不小心把开盖的工具弄丢了,所以他只能利用饮料瓶来开盖.

已知第i个瓶子的品牌为a

,且其能打开b

品牌的瓶子.

问有几瓶饮料托米无法喝到.

被用于打开饮料瓶的瓶子不一定需要被打开.

一个瓶子不能打开其本身.

输入描述:

1 2	第一行一个整数n,表示饮料的瓶数. 接下来n行,每行两个整数ai,bi.

输出描述:

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

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

备注:

1 2	1≤n≤100 1≤ ai,bi≤ 1000

题解

本题坑人之处在于理解题意。因为没理解题意导致提交了好多次才提交成功。本题实质很简单，就是每个瓶子对应有一个编号b，可以开这个编号b除了自己以外的所有的瓶子。但仅限于该瓶子，其他瓶子也只能执行自己的编号b。首先输入完成时记录下所有编号的瓶子个数，把n赋给瓶子个数cnt，因为一开始n个瓶子都没打开。接着对b按顺序进行遍历，如果对应编号的瓶子不存在，则不执行操作，否则接着判断，如果a和b不同，则cnt减去该瓶子的数量，然后数量置零，因为该类瓶子已经打开完了，之后不需要再打开，否则执行完操作后再加1，因为不能打开自己。最后cnt就是剩下没打开的数量。

代码

#include<bits/stdc++.h>
using namespace std;
int vis[1010]={0},a[1010],b[1010];
int main(){
    int n;
    cin>>n;
    int cnt = n;
    for(int i = 1;i<=n;i++){
        cin>>a[i]>>b[i];
        vis[a[i]]++;
    }
    for(int i = 1;i<=n;i++){
        if(vis[b[i]]){
            cnt-=vis[b[i]];
            vis[b[i]]=0;
            if(a[i]==b[i]){
                cnt++;
                vis[b[i]]=1;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

托米搭积木

题目描述

小托米真的很可爱呀(>_<)

这天,可爱的小托米得到了n堆积木,且第i堆积木初始时有ai块积木.

输入描述:

第一行两个整数n,m.
第二行n个整数,第i个整数代表ai的值.
接下来m行,每行代表一个操作:
第一个整数t代表操作的类型
若t=1,则接下来两个整数v,x,代表操作1.
若t=2,则接下来一个整数y,代表操作2.
若t=3,则接下来一个整数q,代表操作3.

输出描述:

1	对于每个操作3,输出其对应的答案.

示例1

输入

复制

10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9

输出

复制

备注:

1≤n,m≤ 105
1≤ai≤109
1≤t≤3
1≤v≤ n,1≤ x≤109
1≤y≤104
1≤q≤n

题解

很简单的一道题，3种操作，第1操作是把第i位置的数该为另一个数x，第2个操作是所有数加v，第3个操作是查询某一位置的数。首先分析，第1种操作和第3种操作时间复杂度都是O(1),第2中操作如果每位加v的话时间复杂度O(n)。所以优化在于第2操作。不过对于此操作我们可以降维优化，因为是所有数都加v，那么我们只需把v记录下来，每次查询时对查询的数直接加v就行了。这样就又遇到了一个问题，就是假如所有的数现在的状态是加v，而i位置元素现在变成了x，这样就会造成所有元素相加不一致。解决也很简单，只需每次变成x后，给x减去v就行了，这样查询时再加上v结果并没变。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,n;
int a[100010], cnt;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int t,x,y;
    cnt=0;
    while(m--){
        cin>>t;
        if(t==3){
            cin>>x;
            cout<<a[x]+cnt<<endl;
        }
        else if(t==2){
            cin>>x;
            cnt+=x;
        }
        else if(t==1){
            cin>>x>>y;
            a[x]=y;
            a[x]-=cnt;
        }
    }
    return 0;
}