题解
贪心大水题，然后比赛的时候就被疯狂hack，至少现在下面的策略是能过的。
- 首先n要是偶数才有解
- 最左边是左括号，最右边是右括号（如果是问号直接变成对应的括号）
- 如果有解，肯定是左括号数目=右括号数目的，于是扫一遍字符串计数，当左括号没满足数目上限的时候一直填左括号
就这样~
代码
|
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 |
#include<bits/stdc++.h> using namespace std; string s; int l,r,n; bool check(){ int zhan=0; for(int i=1;i<=n-2;i++){ if(s[i]=='(')zhan++; else { zhan--; if(zhan<0)return 0; } } if(zhan==0)return 1; return 0; } int main(){ cin>>n;cin>>s; if(n%2!=0){ printf(":(");return 0; } if(s[0]=='?')s[0]='('; if(s[n-1]=='?')s[n-1]=')'; if(s[0]!='('||s[n-1]!=')'){ printf(":(");return 0; } if(n==2){cout<<s<<endl;return 0;} for(int i=1;i<n-1;i++){ if(s[i]=='(')l++; if(s[i]==')')r++; } if(l>=(n>>1)||r>=(n>>1)){ printf(":(");return 0; } for(int i=1;i<=n-2;i++){ if(s[i]=='?'){ if(l+2<=(n>>1)){l++;s[i]='(';} else {r++;s[i]=')';} } } if(check())cout<<s<<endl; else printf(":("); return 0; } |