uva 11988 链表 OR 块状链表

链表写法：新增加一个头结点来使插入操作统一。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 100001;
 7 char text[N];
 8 char str[N];
 9 int next[N];
10 int cur, last, bl;
11 
12 int main ()
13 {
14     while ( gets(text) )
15     {
16         int len = strlen(text);
17         cur = last = 0;
18         bl = 1;
19         memset( next, -1, sizeof(next) );
20         for ( int i = 0; i < len; i++ )
21         {
22             if ( text[i] == '[' )
23             {
24                 cur = 0;
25             }
26             else if ( text[i] == ']' )
27             {
28                 cur = last;
29             }
30             else
31             {
32                 int tmp = next[cur];
33                 int ncur = next[cur] = bl++;
34                 next[ncur] = tmp;
35                 str[ncur] = text[i];
36                 if ( cur == last )
37                 {
38                     last = ncur;
39                 }
40                 cur = ncur;
41             }
42         }
43         for ( int i = next[0]; i != -1; i = next[i] )
44         {
45             putchar( str[i] );
46         }
47         putchar('
');
48     }
49     return 0;
50 }

分析了一下感觉块链也可以过，就套模板试了一下，果然没有让我失望，看来我写的块链还是不错的，哈哈。

块链写法：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int M = 100001;
 7 const int N = 500;
 8 char text[M];
 9 char b[N][N];
10 int sz[N];
11 int next[N];
12 int ps, bl;
13 
14 void init()
15 {
16     bl = 1;
17     ps = 400;
18     memset( sz, 0, sizeof(sz) );
19     memset( next, -1, sizeof(next) );
20 }
21 
22 void spilt( int cur )
23 {
24     int tmp = next[cur];
25     int ncur = next[cur] = bl++;
26     next[ncur] = tmp;
27     for ( int i = sz[cur] / 2; i < sz[cur]; i++ )
28     {
29         b[ncur][sz[ncur]++] = b[cur][i];
30     }
31     sz[cur] = sz[cur] / 2;
32 }
33 
34 void insert( int pos, char val )
35 {
36     int cur = 0, p = sz[cur];
37     while ( p < pos + 1 && next[cur] != -1 )
38     {
39         cur = next[cur];
40         p += sz[cur];
41     }
42     if ( p < pos + 1 )
43     {
44         b[cur][sz[cur]++] = val;
45     }
46     else
47     {
48         p -= sz[cur];
49         pos -= p;
50         for ( int j = sz[cur] - 1; j >= pos; j-- )
51         {
52             b[cur][j + 1] = b[cur][j];
53         }
54         b[cur][pos] = val;
55         sz[cur]++;
56     }
57     if ( sz[cur] > ps ) spilt(cur);
58 }
59 
60 int main ()
61 {
62     while ( gets(text) )
63     {
64         init();
65         int ptr = 0, tot = 0;
66         for ( int i = 0; text[i] != ''; i++ )
67         {
68             if ( text[i] == '[' ) 
69             {
70                 ptr = 0;
71             }
72             else if ( text[i] == ']' )
73             {
74                 ptr = tot;
75             }
76             else
77             {
78                 insert( ptr++, text[i] );
79                 tot++;
80             }
81         }
82            for ( int i = 0; i != -1; i = next[i] )
83            {
84                for ( int j = 0; j < sz[i]; j++ )
85                {
86                    putchar( b[i][j] );
87                }
88            }
89            putchar('
');
90     }
91     return 0;
92 }