首页 > 代码库 > hdu4915 Parenthese sequence 贪心O(n)解法

hdu4915 Parenthese sequence 贪心O(n)解法

2024-07-15 23:33:02   222人阅读

hdu4915

Parenthese sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 82    Accepted Submission(s): 25
Problem Description
bobo found an ancient string. The string contains only three charaters -- "(", ")" and "?".
bobo would like to replace each "?" with "(" or ")" so that the string is valid (defined as follows). Check if the way of replacement can be uniquely determined.
Note:
An empty string is valid. If S is valid, (S) is valid. If U,V are valid, UV is valid.
 
Input
The input consists of several tests. For each tests:
A string s1s2…sn (1≤n≤106).
 
Output
For each tests:
If there is unique valid string, print "Unique". If there are no valid strings at all, print "None". Otherwise, print "Many".
 
Sample Input
??????(??
 
Sample Output
UniqueManyNone
 
Author
Xiaoxu Guo (ftiasch)
 
Source
2014 Multi-University Training Contest 5
 
Recommend
We have carefully selected several similar problems for you:  4919 4918 4917 4916 4914

题意：问号替换成大于号或小于号，求是否有唯一可行方案、多解、无解。（括号规则：和平时运算的括号规则一致）

题解：贪心！O(n)！

我们开三个双向队列，用来记录左括号、右括号、问号的位置。

先从头开始扫，左括号和问号直接入相应队列，遇到右括号就用左括号或问号抵消掉（不入队）。优先用已记录的队列中最右边的左括号，左括号没了的话就用最左边的问号，如果也没有就说明无解。因为越左边的左括号越有用（能选择更多的括号相组合），越靠边的问号越没用（容易只有一种选择），我们先把没用的都用掉，留下比较好用的。

扫完一遍后，还会剩下一些左括号和问号，我们从最右边的左括号开始消，用最右边的问号，如果最右边的问号都比最右边的左括号小了就无解。

这一遍完了以后，就只剩下问号队列还有东西了。是奇数个的话，返回无解。0个的话，返回有唯一解。

然后就是比较难想的部分，剩下偶数个问号，肯定有解，该怎么判断有多少种解呢？

我用的是这样的方法：拿最中间那个（也就是最好用的问号），把它变成左括号，递归调用本函数判断是否有解（函数可以设一个参数，为0的时候是正常调用，为1的时候是只返回有没有解，不判断单解多解），然后再把它变成右括号，判断是否有解。都有解就是多解，只有一个有解就是单解。

这样我们这个函数只扫两次O(n)，然后递归调用两次，哇，还是O(n)，我自己都怕。

虽然正确性我也没有证明，不过AC了，这肯定是因为最中间的问号，就是这么碉！（不，大概是有多解的时候最中间的问号肯定有多解）

代码：

 1 #pragma comment(linker, "/STACK:102400000,102400000") 2  3 #include<cstdio> 4 #include<cmath> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<cmath> 9 #include<map>10 #include<set>11 #include<stack>12 #include<queue>13 using namespace std;14 #define ll __int6415 #define usint unsigned int16 #define mz(array) memset(array, 0, sizeof(array))17 #define minf(array) memset(array, 0x3f, sizeof(array))18 #define REP(i,n) for(int i=0;i<(n);i++)19 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) printf("%d\n",x);24 #define RE  freopen("D.in","r",stdin)25 #define WE  freopen("1.out","w",stdout)26 27 char s[1111111];28 int len;29 30 int farm(bool type) {///type0是要判断多解的，type1只要有解就返回131     int i,j,q;32     int l[3],r[3],b[3][1111111];33     memset(l,0,sizeof(l));34     memset(r,0,sizeof(r));35     bool cant=false;36     for(i=0; i<len; i++) {37         if(s[i]==‘(‘) q=0;38         else if(s[i]==‘)‘)q=1;39         else q=2;40         if(q==1) {41             if(r[0]-l[0]==0) {42                 if(r[2]-l[2]>0) l[2]++;43                 else {44                     return 0;45                 }46             } else r[0]--;47         } else b[q][r[q]++]=i;48     }49     while((l[2]<r[2])&&(l[0]<r[0]) && (b[2][r[2]-1])>b[0][r[0]-1]) {50         --r[2];51         r[0]--;52     }53     if(l[0]<r[0])return 0;54     if((r[2]-l[2])&1==1)return 0;55     if(l[2]==r[2])return 1;56     ///下面剩了偶数个问号存在b[2]里，这可怎么办57     if(type==1)return 1;58     int test1,test2,t=(l[2]+r[2])/2;59     s[b[2][t]]=‘(‘;60     test1=farm(1);61     s[b[2][t]]=‘)‘;62     test2=farm(1);63     //cout<<test1<<‘,‘<<test2<<endl;64     if(test1>=1 && test2>=1)return 2;65     else return 1;66 }67 68 int main() {69     int i,j,k,q,ans;70     while(scanf("%s",s)!=EOF) {71         len=strlen(s);72         ans=farm(0);73         if(ans==0) puts("None");74         else if(ans==1) puts("Unique");75         else puts("Many");76     }77     return 0;78 }
View Code

 


联系
我们