傳送門http://uoj.ac/problem/31

大家好我是來自百度貼吧的_叫我豬豬俠，英文名叫_CallMeGGBond。

我不曾上過大學，但這不影響我對離散數學、復雜性分析等領域的興趣；尤其是括號序列理論，一度令我沉浸其中，無法自拔。至于OI算法競賽，我年輕時確有參加，雖僅獲一枚銅牌，但我素性淡泊，毫不在意，畢竟那所謂FFT、仙人掌之類，只是些雕蟲小技罷了，登不上大雅之堂的；只有括號序列才會真正激發我的研究熱情。

我曾天真地以為，憑借我的學識與才能，足可以在這世間安身立命；然而直到淪落街頭后，我終才領悟現實的殘酷。迫于生計，我只得轉向道德與哲學的研究；但我與括號序列之間情愫依舊，難以剪斷。

理性的傳播總是不順的，研究的道路也是曲折的，但輕易放棄決不是我的風格；為了繼續實現自己的理想，現在我向大家提出一道括號序列的超級大難題。

有一個由?nn?個左括號 “(” 和?nn?個右括號 “)” 組成的序列。每次操作時可以選定兩個數?l,rl,r，然后把第?ll?到第?rr?個括號的順序翻轉（括號的朝向保持不變）。例如將 “()((()(” 翻轉第?33?到第?77?個括號后的結果為 “()()(((”。

我希望使用不超過?nn?次操作，將這個序列變為一個合法的括號序列。

眾所周知，合法括號序列的定義如下：

()?是合法括號序列；

如果?A?是合法括號序列，則?(A)?是合法括號序列；

如果?A，B?是合法括號序列，則?AB?是合法括號序列。

自從來到 UOJ 這個寶地，我的視野變得開闊了，也見識了更多富有人類智慧的人士。我相信各位一定能給我更加滿意的答案！

輸入格式

一行一個長度為?2n2n?的非空字符串表示初始序列。保證字符串只包含左括號和右括號，且左右括號的個數均為?nn。

輸出格式

對于給出的字符串，輸出調整成合法的括號序列的方案。如果不存在這樣的方案輸出一行一個整數??1?1。

否則，第一行一個整數?mm?表示要進行?mm?次翻轉操作。

接下來?mm?行每行兩個整數?l,rl,r?表示要翻轉區間?[l,r][l,r]?內的括號順序。翻轉操作會按你輸出的順序執行。

請保證?m≤nm≤n?以及?1≤l≤r≤2n1≤l≤r≤2n，否則會被判?0?分。

如果有多組方案，輸出任意一組即可。

樣例一

input

)))()(((

output

2 1 6 5 8

explanation

第一次操作后序列變為 “()()))((”。

第二次操作后序列變為 “()()(())”。

限制與約定

測試點編號nn的規模

1	n≤4n≤4
2	n≤100n≤100
3
4
5
6	n≤100000n≤100000
7
8
9
10

時間限制：1s1s

空間限制：256MB

?

掃描 構造 腦洞題

顯然最方便的結果是((()))的形式。

維護雙指針掃描，head指向第一個右括號，tail指向head后面的第一個左括號，每步將兩個位置的括號交換。

顯然是 $ O(n) $的

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 char s[200010]; 6 int ans=0,L[100010],R[100010]; 7 int main(){ 8 int i; 9 scanf("%s",s+1); 10 int n=strlen(s+1); 11 int hd=1; 12 for(i=1;i<=n;i++){ 13 if(s[i]=='('){ 14 while(hd<i && s[hd]!=')')hd++; 15 if(hd^i){ 16 swap(s[hd],s[i]); 17 ans++; 18 L[ans]=hd;R[ans]=i; 19 } 20 } 21 } 22 printf("%d\n",ans); 23 for(i=1;i<=ans;i++){ 24 printf("%d %d\n",L[i],R[i]); 25 } 26 return 0; 27 }

?

轉載于:https://www.cnblogs.com/SilverNebula/p/7061334.html

總結

以上是生活随笔為你收集整理的UOJ#31 【UR #2】猪猪侠再战括号序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。