2009年12月25日星期五.sgu179
找一個(gè)合法的括號(hào)序列的下一個(gè)合法next_permutation
我打了個(gè)表，標(biāo)*的為正確的排列。
我們發(fā)現(xiàn)在()()()()之后的都是非法序列,合法序列只占開始的一小部分。
然后我就用next_permutation水了一下，就過了
WindyWinter還介紹了一個(gè)找規(guī)律的方法: http://www.briefdream.com/sgu-179/
http://www.shnenglu.com/schindlerlee/
/*
00001111 (((()))) *
00010111 ((()())) *
00011011 ((())()) *
00011101 ((()))() *
00011110 ((())))(
00100111 (()(())) *
00101011 (()()()) *
00101101 (()())() *
00101110 (()()))(
00110011 (())(()) *
00110101 (())()() *
00110110 (())())(
00111001 (()))(()
00111010 (()))()(
00111100 (())))((
01000111 ()((())) *
01001011 ()(()()) *
01001101 ()(())() *
01001110 ()(()))(
01010011 ()()(()) *
01010101 ()()()() *
01010110 ()()())(
01011001 ()())(()
01011010 ()())()(
01011100 ()()))((
01100011 ())((())
01100101 ())(()()
01100110 ())(())(
01101001 ())()(()
01101010 ())()()(
01101100 ())())((
01110001 ()))((()
01110010 ()))(()(
01110100 ()))()((
01111000 ())))(((
10000111 )(((()))
10001011 )((()())
10001101 )((())()
10001110 )((()))(
10010011 )(()(())
10010101 )(()()()
10010110 )(()())(
10011001 )(())(()
10011010 )(())()(
10011100 )(()))((
10100011 )()((())
10100101 )()(()()
10100110 )()(())(
10101001 )()()(()
10101010 )()()()(
10101100 )()())((
10110001 )())((()
10110010 )())(()(
10110100 )())()((
10111000 )()))(((
11000011 ))(((())
11000101 ))((()()
11000110 ))((())(
11001001 ))(()(()
11001010 ))(()()(
11001100 ))(())((
11010001 ))()((()
11010010 ))()(()(
11010100 ))()()((
11011000 ))())(((
11100001 )))(((()
11100010 )))((()(
11100100 )))(()((
11101000 )))()(((
11110000 ))))((((
*/
1 /*
2 * SOUR:sgu179
3 * ALGO:math
4 * DATE: 2009年 12月 25日 星期五 16:22:44 CST
5 * COMM:3 http://www.shnenglu.com/schindlerlee/
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 typedef long long LL;
14 const int maxint = 0x7fffffff;
15 const long long max64 = 0x7fffffffffffffffll;
16
17 const int N = 10010;
18 char s[N], last[N];
19 int len;
20
21 int judge()
22 //1 right 0 false -1 exceed
23 {
24 int i;
25 for(i = 0;i < len ;i++) {
26 if(last[i] > s[i]) {
27 break;
28 }else if(last[i] < s[i]) {
29 return -1;
30 }
31 }
32 int top = 0;
33 for(int i = 0;i < len;i++) {
34 if(s[i] == '(') {
35 top ++;
36 }else {
37 if(top > 0)
38 top --;
39 else {
40 return 0;
41 }
42 }
43 }
44 return (top == 0);
45 }
46
47 int main()
48 {
49 int i,j,k;
50 scanf("%s",s);
51 len = strlen(s);
52 for(i = 0;i < len;i++) {
53 if(i & 1) {
54 last[i] = ')';
55 }else {
56 last[i] = '(';
57 }
58 }
59
60 next_permutation(s,s + len);
61 while(1) {
62 int r = judge();
63 if(r == 0) {
64 next_permutation(s,s + len);
65 }else if(r == 1) {
66 for(i = 0;i < len;i++) {
67 putchar(s[i]);
68 }
69 putchar(10);
70 break;
71 }else {
72 printf("No solution\n");
73 break;
74 }
75 }
76 return 0;
77 }
78
79
80