2009年12月25日星期五.sgu179
找一個合法的括號序列的下一個合法next_permutation
我打了個表，標(biāo)*的為正確的排列。
我們發(fā)現(xiàn)在()()()()之后的都是非法序列,合法序列只占開始的一小部分。
然后我就用next_permutation水了一下，就過了
WindyWinter還介紹了一個找規(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