學長小清新題表之UOJ 31.豬豬俠再戰括弧序列

2020 年 8 月 15 日
筆記
基礎--貪心, 思維題

學長小清新題表之UOJ 31.豬豬俠再戰括弧序列

題目描述

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

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

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

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

有一個由 $n$個左括弧「(」和 n 個右括弧「)」組成的序列。每次操作時可以選定兩個數 $l,r$，然後把第 $l $到第 $r$ 個括弧的順序翻轉（括弧的朝向保持不變）。例如將「()((()(」翻轉第 $3$ 到第 $7$個括弧後的結果為「()()(((」。

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

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

$()$ 是合法括弧序列；
如果 $A$ 是合法括弧序列，則 $(A)$是合法括弧序列；
如果 $A，B $是合法括弧序列，則$ AB $是合法括弧序列。

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

輸入格式

一行一個長度為 $2n$的非空字元串表示初始序列。保證字元串只包含左括弧和右括弧，且左右括弧的個數均為 $n$。

輸出格式

對於給出的字元串，輸出調整成合法的括弧序列的方案。如果不存在這樣的方案輸出一行一個整數 $−1$。

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

接下來 $m$行每行兩個整數 $l$,$r$ 表示要翻轉區間 $[l,r]$

內的括弧順序。翻轉操作會按你輸出的順序執行。

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

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

樣例一

input

)))()(((

output

2
1 6
5 8

explanation

第一次操作後序列變為「()()))((」。

第二次操作後序列變為「()()(())」。

限制與約定

測試點編號	n的規模
1	$n≤4$
2、3、4、5	$n≤100$
6、7、8、9、10	$n≤100000$

時間限制：$1s$

空間限制：$256MB$

分析

我們從左到右掃一遍序列，如果是左括弧，就把總價值加一，否則就減一

如果當前的總價值變為負數，我們用頭指針記錄一下當前的位置，同時尾指針一直向後掃

當價值恰好變為$0$時，停止掃描，將頭、尾指針所形成的序列反轉

程式碼

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int jlx[maxn],jly[maxn];
char s[maxn];
int main() {
	scanf("%s",s+1);
	int len=strlen(s+1);
	int m=0,cnt=0;
	for(int i=1;i<=len;i++){
		if(s[i]=='(') cnt++;
		else cnt--;
		if(cnt<0){
			jlx[++m]=i;
			while(cnt!=0){
				i++;
				if(s[i]=='(') cnt+=1;
				else cnt+=-1;
			}
			cnt=0;
			jly[m]=i;
		}
	}
	printf("%d\n",m);
	for(int i=1;i<=m;i++){
		printf("%d %d\n",jlx[i],jly[i]);
	}
	return 0;
}

Tags: 基礎--貪心思維題