HDU 4915 多校5 Parenthese sequence-白红宇的个人博客

HDU 4915 多校5 Parenthese sequence

发布日期：2021-08-13 19:50:57 浏览次数：6 分类：技术文章

本文共 2158 字，大约阅读时间需要 7 分钟。

比赛的时候想了一个自认为对的方法，WA到死，然后还一直敲下去，一直到晚上才想到反例

找是否存在解比较好找，这种左右括号序列，把（当成1，把）当成-1，然后从前往后扫，+1或者-1 遇到？就当初（，然后如果扫到最后中间没有出现负数说明左括号没问题

然后同样的方法从后往前扫，判断右括号那里是不是有问题即可。都没问题就有解，否则无解

当然应该要先判断下序列长度是不是偶数，奇数肯定是无解

至于为什么要像之前的处理即可判断有无解，首先只有正好走完的时候和值为0才是真正合法（因为这个时候左右括号都对应了嘛）

他是偶数个+1或者-1，扫下来的和肯定也是偶数，只要扫到最后不出现负数，（出现负数说明中间有括号找不到匹配的括号）我们只要把中间的某些括号反向，最终一定可以使序列和值为0。所以正反两遍下来即可

最难的就是判断many和unique了，想了很多方法，依然做不好这一题（嘿嘿，盗用了后会无期的台词），还是最普遍的一种最好，即，判断是否有>=2个括号，正向和方向都可以

判断是否可行的方法就是上面的那个，但是我不可能暴力枚举每个括号，然后执行上面的操作，来判断他是否可行吧。。会超时的

所以要预处理一下，弄个prefix0代表i前面是否有前缀和<=1的，suffix0代表i后面的前缀和是否有<=1的，对某个？，如果由正变反的时候，suffix0存在，则不行，由反变正，prefix0存在，也不行

为什么呢，。因为反向代表总和值-2或者+2，所以只要有<=1的和值存在，反向可能就会使其变负值，是非法的。。。所以我们这样通过预处理一遍，再一遍扫描下来，即可得出结果

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 1000000+10;char str[N];int num[N];int prefix[N],suffix[N];int pre0[N],suf0[N];int main(){    while (scanf("%s",str)!=EOF)    {        int len=strlen(str);        if (len&1){            printf("None\n");            continue;        }        memset(prefix,0,sizeof(prefix[0])*(len+2));        memset(suffix,0,sizeof(suffix[0])*(len+2));        memset(pre0,0,sizeof(pre0[0])*(len+2));        memset(suf0,0,sizeof(suf0[0])*(len+2));        for (int i=0;i
         
          =1;i--){            if (prefix[i]<=1) pre0[i]=pre0[i+1]+1;            else pre0[i]=pre0[i+1];        }        if(!flag){            printf("None\n");            continue;        }        for (int i=len;i>=1;i--){            if (num[i]!=0) suffix[i]=suffix[i+1]-num[i];            else suffix[i]=suffix[i+1]+1;            if (suffix[i]<0){                flag=0;                break;            }        }        for (int i=1;i<=len;i++){            if (suffix[i]<=1) suf0[i]=suf0[i-1]+1;            else suf0[i]=suf0[i-1];        }        if (!flag){            printf("None\n");            continue;        }        int cur=0;        for (int i=2;i
          
           =2 &&pre0[i]==0){ if (suffix[i]>=2 && suf0[i]==0) cur++; } } } if (cur>1) printf("Many\n"); else printf("Unique\n"); } return 0;}

转载于:https://www.cnblogs.com/kkrisen/p/3902951.html

转载地址：https://blog.csdn.net/weixin_30699235/article/details/99178433 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Java 学习笔记(6)——继承

下一篇：Python电影投票系统

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章