題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)字符串，只由 ' ( ' , ' ) ' 和 ' - ' 組成，初始時(shí)給出一個(gè)空串 s，三種字符所代表的操作如下：

' ( ' ：在 s 后添加一個(gè)左括號(hào)

' ) ' ：在 s 后添加一個(gè)右括號(hào)

' - ' ：刪除掉 s 最后的那個(gè)括號(hào)

每次操作后問(wèn)有多少個(gè)合法的括號(hào)序列，合法的括號(hào)序列如下：

()

X 是一個(gè)合法的括號(hào)序列，那么 ( X ) 也算

X 和 Y 都是合法的括號(hào)序列，那么 XY 也算

題目分析：最煩寫這種題目了，需要維護(hù)很多互相有關(guān)聯(lián)的變量，訓(xùn)練的時(shí)候沒(méi)插手這個(gè)題，然鵝xy哥和羊駝哥最終還是沒(méi)能調(diào)出這個(gè)惡心人的題目

考慮用失配的左括號(hào)分塊，記錄有多少個(gè)情況三的個(gè)數(shù)，用題解的圖片加以說(shuō)明，比如字符串已經(jīng)維護(hù)到了下面的程度：

數(shù)字代表的只是以情況 3 計(jì)數(shù)的答案，紅色的左括號(hào)是失配的左括號(hào)，將整個(gè)序列分成了互不干擾的好幾塊，接下來(lái)考慮三種操作會(huì)造成什么影響

第一種就是在末尾加上一個(gè)左括號(hào)

當(dāng)前這個(gè)新的左括號(hào)將前面的字符串隔離開(kāi)來(lái)，所以只需要新加上一塊，然后繼續(xù)維護(hù)即可，此時(shí)新塊中的計(jì)數(shù)歸零

第二種是在末尾加上一個(gè)右括號(hào)

考慮兩種情況，第一種情況是，這個(gè)右括號(hào)可以找到一個(gè)與之相匹配的左括號(hào)，那么在匹配之后，之前失配的左括號(hào)的這一整塊都消失掉了，并且與前面的那一塊進(jìn)行了合并，造成的貢獻(xiàn)就是，前面的那一塊的計(jì)數(shù)加一，最終的貢獻(xiàn)會(huì)因?yàn)閮蓚€(gè)區(qū)塊的合并，加上 合并后的塊的計(jì)數(shù)

再考慮另一種情況，也就是右括號(hào)無(wú)法匹配，這就說(shuō)明了前面的所有左括號(hào)都得到了匹配，此時(shí)這個(gè)右括號(hào)將前后隔離開(kāi)來(lái)，且此時(shí)左括號(hào)所維護(hù)的分塊個(gè)數(shù)也是為 1 ，如果在后續(xù)還有操作的話，那么只需要將左括號(hào)這僅有的這個(gè)分塊的計(jì)數(shù)歸零即可

第三種也就是刪除操作了，其實(shí)刪除操作換句話說(shuō)也是一種撤銷操作，只需要將狀態(tài)恢復(fù)到上一個(gè)狀態(tài)即可，題解圖示如下：

所以我們需要在合并相鄰兩個(gè)分塊的時(shí)候額外維護(hù)一些值用于恢復(fù)，這里我選擇用用了一個(gè)對(duì)頂棧來(lái)維護(hù)分塊合并與撤銷的信息，用了一個(gè)普通的棧維護(hù)括號(hào)序列

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;stack<LL>st1,st2;//對(duì)頂棧維護(hù)分塊信息stack<char>st;//普通棧維護(hù)括號(hào)序列char s[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%s",s+1);int n=strlen(s+1);LL ans=0;st1.push(0);//初始時(shí)自帶一塊for(int i=1;i<=n;i++){if(s[i]=='(')//如果是左括號(hào)，額外加一個(gè)分塊{st1.push(0);st.push(s[i]);}else if(s[i]==')')//如果是右括號(hào){if(st1.size()==1)//如果匹配失敗{st2.push(st1.top());//記錄一下需要撤銷的值st1.top()=0;//將st1唯一的塊歸零st.push('*');//打一個(gè)特殊標(biāo)記}else{st2.push(st1.top());st1.pop();//相鄰兩個(gè)塊的合并st1.top()++;//倒數(shù)第二個(gè)塊的總數(shù)需要加一ans+=st1.top();//更新答案st.push(s[i]);}}else//如果是刪除操作{if(st.top()=='(')//左括號(hào)直接刪除即可{st1.pop();}else if(st.top()=='*')//如果是特殊標(biāo)記的右括號(hào)，直接恢復(fù)即可，不影響答案{st1.top()=st2.top();st2.pop();}else//如果刪掉這個(gè)右括號(hào)后會(huì)影響答案，按照添加時(shí)的順序倒序更新即可{ans-=st1.top();st1.top()--;st1.push(st2.top());st2.pop();}st.pop();}printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Aizu - 1407 Parentheses Editor(对顶栈+模拟)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。