首页 > 代码库 > HDU 4915 Parenthese sequence

HDU 4915 Parenthese sequence

2024-07-16 06:32:01   214人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4915

解题报告：从前往后遍历一次，每次判断‘)‘的数目是不是满足 n < (i +1)/ 2，从后往前遍历一次，每次判断‘(‘的数目是不是满足 n <= (len - i) / 2;

这样就可以判断出这个序列是否存在匹配的序列。接下来就是判断是Many还是Unique的情况，因为数据是10的六次方，所以遇到问号改成‘(‘ 或‘)‘暴力判断是不行的，但是我们可以判断出只要(和)的数目小于等于len / 2而且有三个连续的?那句是Many，否则再进行暴力判断，这样就可以大大减小时间复杂度。

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 1000000+5; 7 char str[maxn]; 8  9 int judge(char* str)10 {11     int len = strlen(str);12     int a = 0,b = 0;13     for(int i = 0,j = len- 1;i < len,j >= 0;++i,--j)14     {15         if(str[i] == ‘)‘) a++;16         if(str[j] == ‘(‘) b++;17         if(a >  (i + 1) / 2) return 0;18         if(b > (len - j) / 2) return 0;19     }20     return 1;21 }22 int main()23 {24 //    freopen("1005.in","r",stdin);25     int T = 0;26     while(scanf("%s",str)!=EOF)27     {28         T++;29         int ans;30         ans = judge(str);31         int l = strlen(str);32         if(l & 1) ans = 0;33         if(!ans)34         {35             puts("None");36             continue;37         }38         int len =  strlen(str);39         int a = 0,b = 0,c = 0,f = 0,M = 0;40         for(int i = 0;i < len;++i)41         {42             if(str[i] == ‘(‘) a++;43             if(str[i] == ‘)‘) b++;44             if(str[i] == ‘?‘)45             {46                 f++;47                 c++;48             }49             else50             {51                 M = max(M,f);52                 f = 0;53             }54         }55         if(a >= len / 2 || b >= len / 2 || c <= 1)56         {57             puts("Unique");58             continue;59         }60         if(M >= 3)61         {62             puts("Many");63             continue;64         }65         ans = 0;66         for(int i = 0;i < len;++i)67         if(str[i] == ‘?‘)68         {69             int tt = 0;70             str[i] = ‘(‘;71             tt += judge(str);72             str[i] = ‘)‘;73             tt += judge(str);74             if(tt == 2)75             {76                 ans = 1;77                 break;78             }79             str[i] = ‘?‘;80         }81         printf(ans? "Many\n":"Unique\n");82     }83     return 0;84 }
View Code

 


联系
我们