推斷一個序列是否是有效是簡單的。
可是推斷序列是不是有多個解會出問題。
那么從i=0 ~l
假設讀到問號,推斷該問號成為(能否有效,該問號為)是否有效。
假設都有效,則必有多個解。
假設都無效,則無解。
假設一個有效,則把問號改成有效的括號。
代碼實現例如以下
#include<stdio.h> #include<string.h> char s[1000005],tp[1000005]; int l; int pd() { int zuo,you,num,i; num=0; zuo=0; you=0; for(i=0;i<l;i++) { num++; if(num==1) { if(tp[i]=='?') tp[i]='('; } if(tp[i]=='(') zuo++; if(tp[i]==')') you++; if(you>num/2) { return 0; } if(num%2==0) { if(you==num/2) { zuo=0; you=0; num=0; } } } if(zuo>num/2) return 0; num=0; zuo=0; you=0; for(i=l-1;i>=0;i--) { num++; if(num==1) { if(tp[i]=='?') tp[i]=')'; } if(tp[i]=='(') zuo++; if(tp[i]==')') you++; if(zuo>num/2) { return 0; } if(num%2==0) { if(zuo==num/2) { zuo=0; you=0; num=0; } } } if(you>num/2) return 0; return 1; } int main() { int zuo,you,x,y,i; while(scanf("%s",s)!=EOF) { l=strlen(s); if(l%2==1) { printf("None\n"); continue; } else { strcpy(tp,s); x=pd(); if(x==0) { printf("None\n"); continue; } for(i=0;i<l;i++) { if(s[i]=='?') { strcpy(tp,s); tp[i]=')'; x=pd(); strcpy(tp,s); tp[i]='('; y=pd(); if(x+y==2) {printf("Many\n"); break; } if(x+y==0) { printf("None\n"); break; } if(x==1) s[i]=')'; else s[i]='('; } } if(i==l) { printf("Unique\n"); } } } return 0; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
