cf里好像经常出 这些题,一般贪心是搞不了的。。
918C 问有多少子段[l,r]满足合法括号
先从左往右扫,如果问号+‘(' 数量 >= ')' 说明这段区间的 ) 是满足条件的
然后再从右往左扫,如果问号+’)‘数量 >= '(' 说明这段区间的 ’(‘是满足条件的
这就是一个区间合法的充要条件
#include<bits/stdc++.h> using namespace std; #define maxn 5005 int mp[maxn][maxn]; int len; char s[maxn]; int main(){ cin>>s; len=strlen(s); for(int i=0;i<len;i++){ int a=0,b=0; for(int j=i;j<len;j++){ if(s[j]==')')b++; else a++; if(a>=b)mp[i][j]++; else break; } } for(int i=len-1;i>=0;i--){ int a=0,b=0; for(int j=i;j>=0;j--){ if(s[j]=='(')b++; else a++; if(a>=b)mp[j][i]++; else break; } } int ans=0; for(int i=0;i<len;i++) for(int j=i;j<len;j++) if(mp[i][j]==2 && (j-i)%2) ans++; cout<<ans<<endl; }
1153C 去掉开头末尾的括号匹配问题
问一个区间的[l,r]是否合法。。傻逼贪心明显错的啊
但是很傻比的题啊为什么我写不出来,
除了用上面那种扫两次的做法,还有一种做法是从左往右扫描,先凑出n/2个’(',然后模拟栈来匹配括号即可
#include<bits/stdc++.h> using namespace std; char s[300005]; int n; int main(){ cin>>n>>s; int cnt=0,flag=0,tot=0; if(s[0]==')' || s[n-1]=='(')flag=1; if(n<2)flag=1; if(flag){puts(":(");return 0;} s[0]='(',s[n-1]=')'; for(int i=1;i<n-1;i++) if(s[i]=='(')cnt++; for(int i=1;i<n-1;i++) if(s[i]=='?'){ if(cnt<(n-2)/2)s[i]='(',cnt++; else s[i]=')'; } cnt=0; for(int i=1;i<n-1;i++) if(s[i]=='(')cnt++; else { if(cnt)cnt--; else flag=1; } if(flag || cnt){puts(":(");return 0;} cout<<s; }