杭电多校第三场 1009 Parentheses Matching 题解

题目大意

给你一个只含有$*,(,)$三种字符的字符串。

你可以将*变成空字符串或者左右括号,你需要使左右括号匹配,并且使这个字符串字典序最小,输出最后的字符串。

解题思路

我是真的不是很会写字符串。

比赛发现自己一身都是弱点。。

之前打cf时也差不多,只要碰上字符串的题目,稍微难一点就不会写了。

难受。

其实只是单纯的匹配到还挺简单的,只需要按照可以统计左括号的数量,每遇到一个右括号,就使左括号的数量减一,并且统计之前的*数量。

如果匹配到右括号发现左括号没了,就可以让*变成左括号。

如果匹配到最后,发现左括号多了,就可以让*变成右括号。

多出来就删掉。

关键是需要字典序最小。

这里可以使用贪心,尽可能在最左边变成左括号,在最右边变成右括号。

最后需要判断是否满足匹配的字符串即可。

可以用pos数组来记录一下*的位置,优先使用最前面的。

这里记录一下,本来都过了的,因为用了memset,导致超时了,还特别严重。

ac代码400+ms,用了memset2sT了。

查了一下,发现memset效率和for循环差不多。

下次还是按照题目大小来用for吧。

完整代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int pos[N];
char s[N];

int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
//string s;
while (t--) {
scanf("%s", s);
int l = strlen(s);
int cnt = 0, pre = 0, now = 0;
//memset(pos, -1, sizeof(pos));
for (int i = 0; i <= l; i++) pos[i] = -1;
for (int i = 0; i < l; i++) {
if (s[i] == '(') cnt++;
else if (s[i] == ')') {
cnt--;
if (cnt < 0) {
if (pos[now]==-1) break;
now = pos[now];
s[now - 1] = '(';
cnt = 0;
}
}
else pos[pre] = i+1, pre = i+1;
}
if (cnt > 0) {
for (int i = l - 1; i>=0 && cnt; i--) {
if (s[i] == '*') cnt--,s[i] = ')';
}
}
cnt = 0;
for (int i = 0; i < l; i++) {
if (s[i] == '(') cnt++;
else if (s[i] == ')') {
cnt--;
if (cnt < 0) break;
}
}
if (cnt!=0) cout << "No solution!" << endl;
else {
for (int i = 0; i < l; i++) {
if (s[i] != '*') cout << s[i];
}
cout << endl;
}
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信