Codeforces 1153 C Serval and Parenthesis Sequence

题意：
给一个字符串 只包含 ‘(’ 、 ‘)’ 、和 ’ ?’ 要求改变 ‘?’ 为 ‘(’ 或 ‘）’ 使最终的字符串满足：从第一位开始到任意一位（非最后一位）的字符串不出现形如 ‘（ ）’的情况 如果没有情况满足 输出 ’ : ) ’

思路：
贪心，当n为奇数或s的首字符为)或s的末尾字符为(时，必定不满足题意；
也就是说s的首个字符必定是(且末尾字符必定是)，那么对于1<=i<n的所有i，必须满足[1，i]内的(的个数大于)的个数。

考虑用一个数先记录下当前字符串中”(‘的个数，然后用n/2-当前的得到还需要转化的。然后在进行遍历转化。

在转化后通过遍历字符串 统计 l 和 r 括号的数目 必须满足 在最后一位之前必须有 l > r 且不可以相等 。来检验是否合法。

AC代码：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define max 2000int n;bool check(string ss,int & l,int & r) //检验最终的字符串是否合法 {bool is_true = true;for (int i = 0; i < n; i++){if (ss[i] == '(')++l;if (ss[i] == ')')++r;//因为"(" 个数与")"相同，且最后一个为")"，那么在最后一个之前，"("个数必须大于")"if (l <= r && i != n - 1) {is_true = false;break;}}return is_true; }void show(string ss, bool is_true,int l,int r) {if (is_true){if (l == r)cout << ss << endl;elsecout << ":(" << endl;}elsecout << ":(" << endl; }int main() {string ss;while (cin >>n>> ss){if((n&1)|| ss[0] == ')' || ss[n - 1] == '(')cout << ":(" << endl;else{int count1 = 0;ss[0] = '(', ss[n - 1] = ')';for (int i = 0; i < n; i++){if (ss[i] == '(')++count1; //现在字符串中已经有的}//因为一半是“（”,s所以现在count1表示还需要转化为“（”的个数count1 = n / 2 - count1; for (int i = 0; i < n; i++){if (ss[i] == '?' && count1){ss[i] = '(';--count1;}else if (ss[i] == '?')ss[i] = ')';}int l = 0, r = 0;bool is_true = check(ss,l,r);show(ss, is_true,l,r);}}return 0;} 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的Codeforces 1153 C Serval and Parenthesis Sequence的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。