首页 > 代码库 > hdu4915
hdu4915
思路：就是先把不合格的序列除掉。然后枚举，如果遇到一个问号，先把它变成左括号，判断这样变化整个序列是否合格，然后再变成右括号，再判断整个序列是否合格，如果都合格，那么肯定是多种，如果都不合格，那么就是没有，否则就把它变成唯一合格的那个括号，继续往下判断--
反思：我的思路一直是这样的，但是在比赛的时候没有将它a掉？逗b了，我是用if语句，根据前后左括号，右括号、问号的数量来判断是否合格--果断是错的
唉，必须跑一个for循环，来判断是否可以合格。
#include<iostream>#include<vector>#include<cstring>#include<queue>#include<cstdio>using namespace std;const int inf=1100006;char ch[inf];struct node{ int pzkh,pykh,pwh; int hzkh,hykh,hwh;} s[inf],t[inf];bool deal(int pos,int tos,int num){ int n=strlen(ch); for(int i=num; i<n; i++) { int tmp=s[i].pzkh+pos-(s[i].pykh+tos)+(s[i].pwh-pos-tos); int tmp1=s[i].hzkh-s[i].hykh-s[i].hwh; if(tmp<0||tmp1>0) { return false; } } int ans=s[n-1].pzkh+pos-(s[n-1].pykh+1+tos); int sum=(s[n-1].pwh-pos-tos); if(ans>sum) return false; else if(ans==sum) return true; else { int xx=ans+sum; if(xx<0) return false; if(xx%2==0) return true; else return false; }}int main(){ while(scanf("%s",ch)>0) { int len=strlen(ch); if(len%2) { printf("None\n"); continue; } bool flg=true; int pos=0,tos=0; int r=0; if(ch[len-1]==‘(‘) flg=false; if(ch[0]==‘)‘) flg=false; if(ch[0]==‘?‘) { ch[0]=‘(‘; } if(ch[len-1]==‘?‘) { ch[len-1]=‘)‘; } if(flg==false) { printf("None\n"); continue; } pos=1,tos=0,r=0; if(ch[0]==‘?‘) ch[0]=‘(‘; if(ch[len-1]==‘?‘) ch[len-1]=‘)‘; for(int i=1; i<len; i++) { s[i].pzkh=pos; s[i].pykh=tos; s[i].pwh=r; if(ch[i]==‘(‘) pos++; if(ch[i]==‘)‘) tos++; if(ch[i]==‘?‘) r++; } pos=0,tos=1; r=0; for(int i=len-2; i>=0; i--) { s[i].hzkh=pos; s[i].hykh=tos; s[i].hwh=r; if(ch[i]==‘(‘) pos++; if(ch[i]==‘)‘) tos++; if(ch[i]==‘?‘) r++; } r=pos=tos=0; for(int i=0; i<len; i++) { int tmp=s[i].pzkh-s[i].pykh+s[i].pwh; int tmp1=s[i].hzkh-s[i].hykh-s[i].hwh; if(tmp<0||tmp1>0) { flg=false; break; } } if(flg==false) { printf("None\n"); continue; } pos=tos=0; r=0; bool w=true; for(int i=0; i<len; i++) { s[i].pzkh+=pos; s[i].pykh+=tos; if(1) { int tmp=s[i].pzkh-s[i].pykh+s[i].pwh; int tmp1=s[i].hzkh-s[i].hykh-s[i].hwh; if(tmp<0||tmp1>0) { flg=false; break; } } if(ch[i]==‘?‘) { if(1) { int tmp=s[i].pzkh-s[i].pykh+s[i].pwh; int tmp1=s[i].hzkh-s[i].hykh-s[i].hwh; if(tmp<0||tmp1>0) { flg=false; break; } } bool k=false,k1=false; if(deal(pos,tos+1,i+1)) { k=true; } if(deal(pos+1,tos,i+1)) { k1=true; } if(k&&k1) { w=false; break; } else if(k) { tos++; ch[i]=‘)‘; } else if(k1) { pos++; ch[i]=‘(‘; } else { flg=false; break; } } } if(flg==false) { printf("None\n"); continue; } if(w) printf("Unique\n"); else printf("Many\n"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。