IT博客-苍月流影

ZOJ 2711 Regular Words

杜仲当归 — Tue, 04 Mar 2008 13:28:00 GMT

2770323

2008-03-04 21:15:46

Accepted

2711

C++

00:00.21

20388K

C.D.=.=

考虑当前有a个A，b个B，c个C时的情况为f(a,b,c)，得到f(a,b,c)= f(a-1,b,c)+f(a,b-1,c)+f(a,b,c-1)。注意边界以及限定情况。值得注意的是此题用int数组时会越界。

  1#include <cstdio>
  2#include <string>
  3
  4int N;
  5char f[61][61][61][90];
  6
  7void dp ();
  8void print ( int, int, int );
  9
10int main ()
11{
12    //freopen ( "in.txt", "r", stdin );
13    dp ();
14    while ( scanf ( "%d", &N ) == 1 )
15    {
16        //printf ( "%0.0f\n", f[N][N][N] );
17        print ( N, N, N );
18        printf ( "\n" );
19    }
20    return 0;
21}
22
23void print ( int a, int b, int c )
24{
25    int i;
26    for ( i = 89; i >= 0; i -- )
27    {
28        if ( f[a][b][c][i] )
29            break;
30    }
31    if ( i == -1 )
32        printf ( "0\n" );
33    else
34    {
35        for ( ; i >= 0; i -- )
36            printf ( "%d", f[a][b][c][i] );
37        printf ( "\n" );
38    }
39}
40
41void dp ()
42{
43    int a, b, c, l, i, ac = 0;
44    memset ( f, 0, sizeof ( f ) );
45    f[1][0][0][0] = 1;
46    for ( l = 2; l <= 180; l ++ )
47    {
48        for ( a = 0; a <= l && a <= 60; a ++ )
49        {
50            for ( b = 0; b <= a && b <= 60; b ++ )
51            {
52                c = l - a - b;
53                if ( c > b )
54                    continue;
55                if ( c < 0 )
56                    break;
57                if ( a > 0 )
58                {
59                    //f[a][b][c] += f[a - 1][b][c];
60                    ac = 0;
61                    for ( i = 0; i < 90; i ++ )
62                    {
63                        f[a][b][c][i] += f[a - 1][b][c][i] + ac;
64                        if ( f[a][b][c][i] >= 10 )
65                            ac = 1, f[a][b][c][i] -= 10;
66                        else
67                            ac = 0;
68                    }
69                }
70                if ( b > 0 )
71                {
72                    //f[a][b][c] += f[a][b - 1][c];
73                    ac = 0;
74                    for ( i = 0; i < 90; i ++ )
75                    {
76                        f[a][b][c][i] += f[a][b - 1][c][i] + ac;
77                        if ( f[a][b][c][i] >= 10 )
78                            ac = 1, f[a][b][c][i] -= 10;
79                        else
80                            ac = 0;
81                    }
82                }
83                if ( c > 0 )
84                {
85                    //f[a][b][c] += f[a][b][c - 1];
86                    ac = 0;
87                    for ( i = 0; i < 90; i ++ )
88                    {
89                        f[a][b][c][i] += f[a][b][c - 1][i] + ac;
90                        if ( f[a][b][c][i] >= 10 )
91                            ac = 1, f[a][b][c][i] -= 10;
92                        else
93                            ac = 0;
94                    }
95                }
96            }
97        }
98    }
99}
100
101

杜仲当归 2008-03-04 21:28 发表评论

ZOJ 1463 Brackets Sequence

杜仲当归 — Wed, 27 Feb 2008 05:02:00 GMT

几乎和Folding是一样的题目，区别是这更简单一点。LRJ黑书里拿做动态规划例题的第一道。

  1#include <cstdio>
  2#include <string>
  3
  4#define min(x,y) ( x < y ? x : y )
  5
  6int T, m[101][101], L, ch[101][101];
  7char str[101];
  8
  9void dp ();
10int get ( int, int );
11void init ();
12void print ( int, int );
13
14int main ()
15{
16    //freopen ( "bracket.in", "r", stdin );
17    scanf ( "%d", &T );
18    gets ( str );
19    int i;
20    for ( i = 0; i < T; i ++ )
21    {
22        if ( i )
23            printf ( "\n" );
24        init ();
25        dp ();
26        //printf ( "%d\n", ch[0][L - 1] );
27        print ( 0, L - 1 );
28        printf ( "\n" );
29        //pt ();
30    }
31    return 0;
32}
33
34void init ()
35{
36    gets ( str );
37    gets ( str );
38    L = strlen ( str );
39    memset ( m, 0, sizeof ( m ) );
40    memset ( ch, 0xff, sizeof ( ch ) );
41}
42
43void dp ()
44{
45    int i, j, p, k, t;
46    for ( i = 0; i < L; i ++ )
47        m[i][i] = 1;
48    for ( p = 1; p <= L; p ++ )
49    {
50        for ( i = 0; i + p < L; i ++ )
51        {
52            int ans = 101;
53            j = i + p;
54            if ( str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']' )
55            {
56                t = m[i + 1][j - 1];
57                if ( ans > t )
58                    ch[i][j] = -2, ans = t;
59            }
60            if ( str[i] == '(' || str[i] == '[' )
61            {
62                t = m[i + 1][j] + 1;
63                if ( ans > t )
64                    ch[i][j] = i, ans = t;
65            }
66            if ( str[j] == ')' || str[j] == ']' )
67            {
68                t = m[i][j - 1] + 1;
69                if ( ans > t )
70                    ch[i][j] = j, ans = t;
71            }
72            for ( k = i; k < j; k ++ )
73            {
74                t = m[i][k] + m[k + 1][j];
75                if ( ans > t )
76                    ch[i][j] = k, ans = t;
77            }
78            m[i][j] = ans;
79        }
80    }
81}
82
83void print ( int i, int j )
84{
85    if ( i > j )
86        return;
87    if ( i == j )
88    {
89        if ( str[i] == '(' || str[i] == ')' )
90            printf ( "()" );
91        else
92            printf ( "[]" );
93        return;
94    }
95    else if ( ch[i][j] == -2 )
96    {
97        printf ( "%c", str[i] );
98        print ( i + 1, j - 1 );
99        printf ( "%c", str[j] );
100    }
101    else if ( ch[i][j] == j )
102    {
103        print ( i, j - 1 );
104        print ( j, j );
105    }
106    else
107    {
108        print ( i, ch[i][j] );
109        print ( ch[i][j] + 1, j );
110    }
111}
112
113

杜仲当归 2008-02-27 13:02 发表评论

ZOJ 1505 Solitaire

杜仲当归 — Tue, 26 Feb 2008 06:20:00 GMT

摘要: 2761550 2008-02-26 14:10:05 Accepted 1505 C++ 00:00.11 3480K C.D.=.= ... 阅读全文

杜仲当归 2008-02-26 14:20 发表评论

ZOJ 1554 Folding

杜仲当归 — Mon, 25 Feb 2008 07:21:00 GMT

摘要: 2760648 2008-02-25 15:11:56 Accepted 1554 C++ 00:00.56 980K C.D.=.= ... 阅读全文

杜仲当归 2008-02-25 15:21 发表评论

ZOJ 2330 A^B == B^A?

杜仲当归 — Mon, 11 Feb 2008 06:18:00 GMT

菜题。即便是这样我还是写了三遍……步长开的太大，结果精度不高。

把A^B == B^A两边求对数，很容易得到ln(x)/x的函数。求导，此函数在e两侧单调。故可用二分。

1/*
2    二分逼近ln(x)/x = ln(a)/a
3*/
4
5#include <cstdio>
6#include <cmath>
7
8#define ZERO 1e-14
9#define E exp(1.0f)
10
11double A;
12
13int main ()
14{
15    //freopen ( "in.txt", "r", stdin );
16    while ( scanf ( "%lf", &A ) != EOF )
17    {
18        if ( A - E > ZERO )
19            printf ( "-1\n" );
20        else
21        {
22            double high, low, mid, d;
23            high = 45, low = E;
24            while ( high - low >= ZERO )
25            {
26                mid = ( high + low ) / 2;
27                d = log ( mid ) / mid - log ( A ) / A;
28                if ( d < ZERO && d > -ZERO )
29                    break;
30                else if ( d > ZERO )
31                {
32                    low = mid + 0.0000001;
33                }
34                else if ( d < -ZERO )
35                {
36                    high = mid - 0.0000001;
37                }
38            }
39            printf ( "%0.5f\n", mid );
40            d = fabs ( log ( mid ) / mid - log ( A ) / A );
41            //printf ( "error %0.8f\n", d );
42        }
43    }
44    return 0;
45}

杜仲当归 2008-02-11 14:18 发表评论

ZOJ 2281 Way to Freedom

杜仲当归 — Fri, 08 Feb 2008 13:29:00 GMT

摘要: 2746723 2008-02-08 20:54:30 Accepted 2281 C++ 00:01.51 25832K C.D. ... 阅读全文

杜仲当归 2008-02-08 21:29 发表评论

ZOJ 2278 Fight for Food

杜仲当归 — Thu, 07 Feb 2008 07:30:00 GMT

摘要: 2745991 2008-02-07 15:05:00 Accepted 2278 C++ 00:00.68 1708K C.D. ... 阅读全文

杜仲当归 2008-02-07 15:30 发表评论

ZOJ 2286 Sum of Divisors

杜仲当归 — Tue, 05 Feb 2008 06:19:00 GMT

好吧，这其实是一道菜题。

1#include <cstdio>
2#include <string>
3
4const int MAXN = 1000000;
5int b[2][3393000];
6
7int main ()
8{
9    memset ( b, 0, sizeof ( b ) );
10    int i, j;
11    for ( i = 2; i <= 1000000; i ++ )
12        b[0][i] = 1;
13    for ( i = 2; i <= 1000; i ++ )
14    {
15        j = MAXN / i;
16        while ( j > i )
17        {
18            b[0][i * j] += i + j;
19            j --;
20        }
21        b[0][i * i] += i;
22    }
23    for ( i = 1; i <= 1000000; i ++ )
24    {
25        b[1][b[0][i]] ++;
26    }
27    int sum = 0;
28    for ( i = 0; i < 3393000; i ++ )
29    {
30        sum += b[1][i];
31        b[0][i] = sum;
32    }
33
34    //freopen ( "in.txt", "r", stdin );
35    int N;
36    while ( scanf ( "%d", &N ) != EOF )
37    {
38        if ( N > 3392928 )
39            printf ( "1000000\n" );
40        else
41            printf ( "%d\n", b[0][N] );
42    }
43    return 0;
44}

杜仲当归 2008-02-05 14:19 发表评论

ZOJ 2284 Inversion Number

杜仲当归 — Mon, 04 Feb 2008 07:01:00 GMT

求N排列中逆序数对为K对的个数。

需要一个小技巧。一个形为{2，1，5，3，4}的5-排列，可以转化为一个{0，1，0，1，1}的排列。这里每个元素A_i表示i前逆序数的对数。易证明两者一一对应。

这样就把问题转化为求åAi=K，Ai<=i的排列个数。设F（i，j）表示前i个数之和达到j的排列个数，DP打表即得解。

1#include <cstdio>
2#include <string>
3
4const int MAXN = 20;
5
6int m[21][201][MAXN], N, K;
7
8void add ( int x1, int m1, int x2, int m2 )
9{
10    int i;
11    for ( i = 0; i < MAXN; i ++ )
12    {
13        m[x1][m1][i] += m[x2][m2][i];
14    }
15    int c = 0;
16    for ( i = 0; i < MAXN; i ++ )
17    {
18        int t = c + m[x1][m1][i];
19        c = t / 10;
20        m[x1][m1][i] = t % 10;
21    }
22}
23
24void print ( int x1, int m1 )
25{
26    //printf ( "$%d\n", m[x1][m1][1] );
27    int i;
28    for ( i = MAXN - 1; m[x1][m1][i] == 0 && i >= 0; i -- )
29        ;
30    if ( i == -1 )
31    {
32        printf ( "0" );
33    }
34    else
35    {
36        for ( ; i >= 0; i -- )
37        {
38            printf ( "%d", m[x1][m1][i] );
39        }
40    }
41}
42
43void dp ()
44{
45    memset ( m, 0, sizeof ( m ) );
46    int i, j, k;
47    m[0][0][0] = 1;
48    for ( i = 1; i < 20; i ++ )
49    {
50        for ( j = 0; j < 200; j ++ )
51        {
52            for ( k = 0; k <= i && j - k >= 0; k ++ )
53            {
54                add ( i, j, i - 1, j - k );
55            }
56        }
57    }
58    //pt ();
59}
60
61int main ()
62{
63    //freopen ( "in.txt", "r", stdin );
64    dp ();
65    while ( scanf ( "%d %d", &N, &K ) )
66    {
67        if ( N == 0 && K == 0 )
68        {
69            break;
70        }
71        print ( N - 1, K );
72        printf ( "\n" );
73    }
74    return 0;
75}

杜仲当归 2008-02-04 15:01 发表评论