【c++百日刷题计划】 ———— DAY18，刷题百天，养成刷题好习惯

第一题 括号序列

题目描述

定义如下规则序列(字符串)：

1．空序列是规则序列；

2．如果S是规则序列，那么(S)和[S]也是规则序列；

3．如果A和B都是规则序列，那么AB也是规则序列。

例如，下面的字符串都是规则序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是补全该括号序列，即扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。

输入格式

输入文件仅一行，全部由‘(’，‘)’，‘[’，‘]’组成，没有其他字符，长度不超过100。

输出格式

输出文件也仅有一行，全部由‘(’，‘)’，‘[’，‘]’组成，没有其他字符，把你补全后的规则序列输出即可。

样例 #1

样例输入 #1

([()
1

样例输出 #1

()[]()
1

提示

将前两个左括号补全即可。

解题思路

• 1）遍历字符串，找到右括号时停止，向左遍历找到一个没被标记成功匹配的左括号。若匹配成功，进行标记。
• 2）按照标记输出。

参考代码

#include 
using namespace std;

int a[105]; 
int main()
{
    string s;
    cin >> s;
    for (int i=0; i<s.size(); i++) {
        if (s[i] == ')') 
        { 
            for (int j=i-1; j>=0; j--) {
                if (s[j] == '(' and a[j] == 0) 
                { 
                    a[i] = a[j] = 1;
                    break;
                }
                else if (s[j] == '[' and a[j] == 0) break; 
            }
        }
        else if (s[i] == ']')
        {
            for (int j=i-1; j>=0; j--) 
            {
                if (s[j] == '[' and a[j] == 0)
                {
                    a[i] = a[j] = 1;
                    break;
                }
                else if (s[j] == '(' and a[j] == 0) break;
            }
        }
    }
    for (int i=0; i<s.length(); i++) 
    {
        if (a[i] == 0)
        { 
            if (s[i] == '(' or s[i] == ')') cout << "()";
            else cout << "[]";
        }
        else cout << s[i];
    }
    return 0;
}
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
43
44

第二题【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le 100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

样例 #1

样例输入 #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3
1
2
3
4
5
6
7

样例输出 #1

Yes
No
1
2

解题思路

• 1）按照题目要求用栈模拟。

参考代码

#include
using namespace std;
int main()
{
	int q;
	cin>>q;
	while(q--)
	{
		int n;
		int a[100050],b[100050];
		stack<int >s;
		cin>>n;
		for(int i=1;i<=n;i++)
		    cin>>a[i];
		for(int i=1;i<=n;i++)
		    cin>>b[i];
		int head=1;
		for(int i=1;i<=n;i++)
		{
			s.push(a[i]);
			while(s.top()==b[head])
			{
				s.pop();
				head++;
				if(s.empty())
				    break;
			}
		}
		if(s.empty())
		cout<<"Yes"<<endl;
		else 
		cout<<"No"<<endl;
	}
	return 0;
}
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

第三题 [USACO09OCT]Bessie’s Weight Problem G

题目描述

Bessie像她的诸多姊妹一样，因为从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置于一个及其严格的节食计划之中。她每天不能吃多过H (5 <= H <= 45,000)公斤的干草。 Bessie只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N (1 <= N <= 500)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。 给定一个列表表示每捆干草的重量S_i (1 <= S_i <= H), 求Bessie不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

输入格式

* 第一行: 两个由空格隔开的整数: H 和 N * 第2到第N+1行: 第i+1行是一个单独的整数，表示第i捆干草的重量S_i。

输出格式

* 第一行: 一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的干草。

样例 #1

样例输入 #1

56 4
15
19
20
21
1
2
3
4
5

样例输出 #1

56
1

提示

输入说明:

有四捆草，重量分别是15, 19, 20和21。Bessie在56公斤的限制范围内想要吃多少就可以吃多少。

输出说明:

Bessie可以吃3捆干草（重量分别为15, 20, 21）。恰好达到她的56公斤的限制。

解题思路

• 1）简单的01背包问题。

参考代码

#include
using namespace std;
int dp[105000];
int main()
{
	int H,N;
	cin>>H>>N;
	for(int i=1;i<=N;i++)
	{
		int s;
		cin>>s;
		for(int j=H;j>=s;j--)
		{
			dp[j]=max(dp[j],dp[j-s]+s);
		}
	}
	cout<<dp[H];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第四题 [HNOI2002]营业额统计

题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

我们定义，一天的最小波动值 = min ⁡ { ∣ 该天以前某一天的营业额 − 该天营业额 ∣ } \min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\} min{∣该天以前某一天的营业额−该天营业额∣}。

特别地，第一天的最小波动值为第一天的营业额。

输入格式

第一行为正整数 $n$（$n\le 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$（$|a_i|\le 10^6$) ，表示第 $i$ 天公司的营业额，可能存在负数。

输出格式

输出一个正整数，即每一天最小波动值的和，保证结果小于 $2^{31}$。

样例 #1

样例输入 #1

6
5
1
2
5
4
6
1
2
3
4
5
6
7

样例输出 #1

12
1

提示

结果说明：$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$

解题思路

• 1）递推问题
• 2）所以当 i 为奇数时f[i]=f[i-1]。
• 3）当 i 为偶数时f[i]=f[i-1]+f[i/2]。

参考代码

#include
using namespace std;
int n;
int a[1001];
int main()
{
    int n;
    cin>>n;
    a[1]=1;
    for(int i=2;i<=n;i++)
    {
        a[i]=a[i-1];
        if(i%2==0)
            a[i]+=a[i/2];
    }
    cout<<a[n];
    
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19