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

题目大意

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

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

解题思路

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

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

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

难受。

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

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

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

多出来就删掉。

关键是需要字典序最小。

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

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

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

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

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

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

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

完整代码

#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;
}