Jan.16th
注：黑粗体为超链接
一开始看了题目还以为是DP……后来想了想没有想到O（n）的
然后就应该是贪心
怎么贪呢？我们先把所有的 ? 都改成 )
为什么是 ) 而不是 ( 呢？
因为改成 ( 的话就不知道后面有没有要改的
改成 ) 就能知道前面有没有要改的
记录一下当前左括号比右括号多几个
然后用个堆维护一下 每次右括号比左括号多的时候
把花费最少的 ) 改成 ( 就行了
C++ Code
|
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 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct Qmark{ int pos,val; bool operator <(const Qmark&w)const{return val>w.val;} }; priority_queue<Qmark>a; char s[50005]; int main(){ gets(s); ll Ans=0; int Left=0,len=strlen(s); Rep(i,0,len-1){ if (s[i]=='(') Left++; else if (s[i]==')'||s[i]=='?') Left--; if (s[i]=='?'){ int l=IN(),r=IN(); Ans+=r; a.push(Qmark{i,l-r}); s[i]=')'; } if (Left<0){ if (a.empty()) return puts("-1"),0; else{ Ans+=a.top().val; s[a.top().pos]='('; a.pop(); Left+=2; } } } if (Left!=0) return puts("-1"),0; else{ printf("%I64d\n",Ans); puts(s); } } |
一道比较常见的字符串处理题 不多说
也是一道比较常见的字符串处理题 不多说
md这种题都要做这么久果然是人变弱了吗
开个数组存一下到某个右括号时，
以这个右括号为最后一个字符的合法括号序列的最长长度
开个栈存一下左括号的位置
然后每次O(1)转移就行
C++ Code
|
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 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define zero 1000005 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int S[1000005],Max=0,num=1,top=0,l[1000005]; char s[1000005]; int main(){ gets(s+1); int len=strlen(s+1); Rep(i,1,len){ if (s[i]=='(') S[++top]=i; else{ if (!top) continue; if (!S[top]) l[i]=i; else l[i]=l[S[top]-1]+i-S[top]+1; if (l[i]>Max) Max=l[i],num=1; else if (l[i]==Max) num++; top--; } } printf("%d %d\n",Max,num); } |
评论 (0)
