牛客训练赛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的高度的较大值。 其中+指的是字符串的连接符。

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

img

输入描述:

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

输出描述:

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

示例1

输入

复制

1
2
3
4
5
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即将要减去的面积就是总面积。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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

i

,且其能打开b

i

品牌的瓶子.

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

复制

1
2
3
4
5
4
1 1
2 2
3 3
4 4

输出

复制

1
4

示例2

输入

复制

1
2
3
4
5
4
1 2
2 3
3 4
4 1

输出

复制

1
0

备注:

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

题解

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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块积木.

输入描述:

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

输出描述:

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

示例1

输入

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
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
2
3
4
5
6
7
2
9
11
20
30
40
39

备注:

1
2
3
4
5
6
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结果并没变。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!