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); } |
May 23, 2024 06:05:36 PM
The travel addict inside you is craving for new adventure? things to do post will suggest you the new destination for your next journey with all the best spots around the world.