coreBugZJ

此 blog 已弃。

ECNU 2011 Contest Three For Beginners,我的解题报告

题目链接:http://acm.hust.edu.cn:8080/judge/contest/viewContest.action?cid=1465


A - Number Sequence

模式匹配,KMP 算法。

 1#include <iostream>
 2#include <cstdio>
 3
 4using namespace std;
 5
 6template<class T>
 7void KMPinit( const T * pat, int patLen, int * flink ){
 8        int j, k;   flink[ 0 ] = -1;
 9        for( j = 1; j < patLen; ++j ){
10                k = flink[ j - 1 ];
11                while( ( k != -1 ) && ( pat[ j - 1 ] != pat[ k ] ) ){ k = flink[ k ];  }
12                flink[ j ] = k + 1;
13        }

14}

15template<class T>
16int KMPmatch( const T * txt, int txtLen, const T * pat, int patLen, const int * flink, int matBegin = 0 ){
17        int i = matBegin, j = 0;
18        while( ( i < txtLen ) && ( j < patLen ) ){
19                while( ( j != -1 ) && ( txt[ i ] != pat[ j ] ) ){ j = flink[ j ];  }
20                ++j;  ++i;
21        }

22        return ( j >= patLen ? i - patLen : -1 );
23}

24
25const int N = 1000009;
26const int M = 10009;
27
28int a[ N ], b[ M ], link[ M ], n, m;
29
30int main() {
31        int td, i;
32        scanf( "%d"&td );
33        while ( td-- > 0 ) {
34                scanf( "%d%d"&n, &m );
35                for ( i = 0; i < n; ++i )
36                        scanf( "%d", a+i );
37                for ( i = 0; i < m; ++i ) 
38                        scanf( "%d", b+i );
39                KMPinit( b, m, link );
40                i = KMPmatch( a, n, b, m, link, 0 );
41                printf( "%d\n", ( (i==(-1)) ? (-1) : (i+1) ) );
42        }

43        return 0;
44}

45




B - Big Number

模拟手工笔算就好了,不需要高精度。

 1#include <iostream>
 2#include <cstdio>
 3
 4using namespace std;
 5
 6const int L = 1009;
 7
 8char s[ L ];
 9
10int main() {
11        int a, b;
12        char *p;
13        while ( scanf( "%s%d", s, &b ) == 2 ) {
14                a = 0;
15                for ( p = s; *p; ++p ) {
16                        a = ( a*10 + (*p) - '0' ) % b;
17                }

18                printf( "%d\n", a );
19        }

20        return 0;
21}

22




C - A strange lift

最短路径,宽度优先搜索,动态规划, 都可以。

我的最短路径 SPFA 算法。

 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4
 5using namespace std;
 6
 7const int N   = 209;
 8const int INF = 0x3f3f3f3f;
 9const int QL  = N;
10
11int n, a, b, k[ N ];
12
13int solve() {
14        int que[ QL ], inq[ N ], qh, qt, f[ N ], i, j;
15        if ( a == b ) {
16                return 0;
17        }

18        qh = 0;
19        qt = 1;
20        memset( inq, 0sizeof(inq) );
21        que[ qh ] = a;
22        inq[ a ] = 1;
23        memset( f, 0x3fsizeof(f) );
24        f[ a ] = 0;
25        while ( qh != qt ) {
26                i = que[ qh ];
27                qh = ( qh + 1 ) % QL;
28                inq[ i ] = 0;
29                j = i + k[ i ];
30                if ( j <= n ) {
31                        if ( f[ i ] + 1 < f[ j ] ) {
32                                f[ j ] = f[ i ] + 1;
33                                if ( !inq[ j ] ) {
34                                        inq[ j ] = 1;
35                                        que[ qt ] = j;
36                                        qt = ( qt + 1 ) % QL;
37                                }

38                        }

39                }

40                j = i - k[ i ];
41                if ( j >= 1 ) {
42                        if ( f[ i ] + 1 < f[ j ] ) {
43                                f[ j ] = f[ i ] + 1;
44                                if ( !inq[ j ] ) {
45                                        inq[ j ] = 1;
46                                        que[ qt ] = j;
47                                        qt = ( qt + 1 ) % QL;
48                                }

49                        }

50                }

51        }

52        return ( (f[ b ] == INF) ? (-1) : f[ b ] );
53}

54
55int main() {
56        int i;
57        for ( ; ; ) {
58                scanf( "%d"&n );
59                if ( n == 0 ) {
60                        break;
61                }

62                scanf( "%d%d"&a, &b );
63                for ( i = 1; i <= n; ++i ) {
64                        scanf( "%d", k+i );
65                }

66                printf( "%d\n", solve() );
67        }

68        return 0;
69}

70




D - Intersecting Lines

计算几何入门题,用向量叉积判断直线关系,对于交点,我是用向量推出二元一次方程组,解得交点。

 1#include <iostream>
 2#include <iomanip>
 3
 4using namespace std;
 5
 6typedef long long Lint;
 7
 8Lint cross( Lint ax, Lint ay, Lint bx, Lint by ) {
 9        return ax*by - ay*bx;
10}

11
12int point_in_line( Lint px, Lint py, Lint ax, Lint ay, Lint bx, Lint by ) {
13        return ( cross( ax-bx, ay-by, px-bx, py-by ) == 0 );
14}

15
16int solve( Lint a, Lint b, Lint c, Lint e, Lint f, Lint g, double *x, double *y ) {
17        *= (double)(c*e-a*g) / (a*f-b*e);
18        *= (double)(c*f-b*g) / (b*e-a*f);
19        return 1;
20}

21
22#define  LINE_ONE  0
23#define  LINE_PAR  1
24#define  LINE_INS  2
25
26double ix, iy;
27
28int type( Lint ax, Lint ay, Lint bx, Lint by, Lint cx, Lint cy, Lint dx, Lint dy ) {
29        if ( point_in_line(ax,ay,cx,cy,dx,dy) && point_in_line(bx,by,cx,cy,dx,dy) ) {
30                return LINE_ONE;
31        }

32        if ( cross( ax-bx, ay-by, cx-dx, cy-dy ) == 0 ) {
33                return LINE_PAR;
34        }

35        solve( by-ay, ax-bx, ay*(bx-ax)-ax*(by-ay), dy-cy, cx-dx, cy*(dx-cx)-cx*(dy-cy), &ix, &iy );
36        return LINE_INS;
37}

38
39int main() {
40        int td;
41        Lint ax, ay, bx, by, cx, cy, dx, dy;
42        cout << "INTERSECTING LINES OUTPUT\n";
43        cin >> td;
44        while ( td-- > 0 ) {
45                cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
46                switch ( type( ax, ay, bx, by, cx, cy, dx, dy ) ) {
47                case LINE_ONE : 
48                        cout << "LINE\n";
49                        break;
50                case LINE_PAR : 
51                        cout << "NONE\n";
52                        break;
53                case LINE_INS : 
54                        cout << fixed << setprecision(2<< "POINT " << ix << " " << iy << "\n";
55                        break;
56                }

57        }

58        cout << "END OF OUTPUT\n";
59        return 0;
60}

61




E - Hat’s Words

字符串查找,可以字典树,可以 map 等等。

 1#include <iostream>
 2#include <string>
 3#include <set>
 4#include <list>
 5
 6using namespace std;
 7
 8int main() {
 9        set< string >  dict;
10        list< string > book;
11        string word;
12        int i;
13        while ( cin >> word ) {
14                book.push_back( word );
15                dict.insert( word );
16        }

17        for ( list< string >::const_iterator  ite = book.begin();  ite != book.end(); ++ite ) {
18                word = (*ite);
19                for ( i = 1; i+1 < word.length(); ++i ) {
20                        if ( (dict.find(word.substr(0,i))!=dict.end()) && (dict.find(word.substr(i))!=dict.end()) ) {
21                                cout << word << "\n";
22                                break;
23                        }

24                }

25        }

26        // system( "pause" );
27        return 0;
28}

29




F - KILLER

HUST Monthly 2011.04.09的B题,我比赛时没做出来的水题,wbw 告诉我的解法,想想群的知识。

 1#include <iostream>
 2#include <cstdio>
 3
 4using namespace std;
 5
 6int main() {
 7        int td, a, b, n, ans;
 8        scanf( "%d"&td );
 9        while ( td-- > 0 ) {
10                scanf( "%d"&n );
11                ans = n;
12                while ( n-- > 0 ) {
13                        scanf( "%d%d"&a, &b );
14                        if ( a == b ) {
15                                --ans;
16                        }

17                }

18                printf( "%d\n", ans );
19        }

20        return 0;
21}

22




G - Conference Call

连接三点的路径中必有一点为三岔口(也许为三点之一),若以此三岔口与三点的最近距离的和为此三岔口的价值,枚举所有三岔口,找出最大的价值,即为答案。补充:赛后和CY讨论,知道枚举所有点即可,不必为三岔口,因为若此点不是三岔口,则价值必定不是最小。

  1#include <iostream>
  2#include <cstdio>
  3#include <cstring>
  4#include <map>
  5
  6using namespace std;
  7
  8const int N   = 10009;
  9const int M   = 509;
 10const int INF = 0x2f2f2f2f;
 11
 12int disA[ M ], disB[ M ], disC[ M ];
 13int preA[ M ], preB[ M ], preC[ M ];
 14
 15int w[ M ][ M ], m, n, t[ N ];
 16
 17int nosame( int v ) {
 18        map< intint > cnt;
 19        map< intint >::const_iterator  ite;
 20        int i;
 21        cnt[ v ] = 1;
 22        for ( i = preA[ v ]; i && preA[ i ]; i = preA[ i ] ) {
 23                ++cnt[ i ];
 24        }

 25        for ( i = preB[ v ]; i && preB[ i ]; i = preB[ i ] ) {
 26                ++cnt[ i ];
 27        }

 28        for ( i = preC[ v ]; i && preC[ i ]; i = preC[ i ] ) {
 29                ++cnt[ i ];
 30        }

 31        for ( ite = cnt.begin(); ite != cnt.end(); ++ite ) {
 32                if ( ite->second > 1 ) {
 33                        return 0;
 34                }

 35        }

 36        return 1;
 37}

 38
 39void spfa( int s, int dis[], int pre[] ) {
 40        const int QL = M;
 41        int que[ QL ], inq[ M ], qh = 0, qt = 1, i, j;
 42
 43        memset( dis, 0x2fsizeof(int)*M );
 44        memset( pre, 0,    sizeof(int)*M );
 45        memset( inq, 0,    sizeof(inq)   );
 46        dis[ s ] = 0;
 47        que[ qh ] = s;
 48        inq[ s ] = 1;
 49        while ( qh != qt ) {
 50                i = que[ qh ];
 51                qh = ( qh + 1 ) % QL;
 52                inq[ i ] = 0;
 53                for ( j = 1; j <= m; ++j ) {
 54                        if ( dis[ i ] + w[ i ][ j ] < dis[ j ] ) {
 55                                dis[ j ] = dis[ i ] + w[ i ][ j ];
 56                                pre[ j ] = i;
 57                                if ( ! inq[ j ] ) {
 58                                        inq[ j ] = 1;
 59                                        que[ qt ] = j;
 60                                        qt = ( qt + 1 ) % QL;
 61                                }

 62                        }

 63                }

 64        }

 65}

 66
 67// INF <==> no answer
 68int solve( int a, int b, int c ) {
 69        int i, ans = INF;
 70        spfa( a, disA, preA );
 71        spfa( b, disB, preB );
 72        spfa( c, disC, preC );
 73        for ( i = 1; i <= m; ++i ) {
 74                if ( nosame(i) && (disA[i]+disB[i]+disC[i]<ans) ) {
 75                        ans = disA[ i ] + disB[ i ] + disC[ i ];
 76                }

 77        }

 78        return ans;
 79}

 80
 81int main() {
 82        int lw, i, j, k, a, b, c, cc = 0, cl, ans;
 83        while ( scanf( "%d%d%d"&n, &m, &lw ) == 3 ) {
 84                printf( "Case #%d\n"++cc );
 85                memset( w, 0x2fsizeof(w) );
 86                for ( i = 1; i <= n; ++i ) {
 87                        scanf( "%d", t+i );
 88                }

 89                while ( lw-- > 0 ) {
 90                        scanf( "%d%d%d"&i, &j, &k );
 91                        if ( w[ i ][ j ] > k ) {
 92                                w[ j ][ i ] = w[ i ][ j ] = k;
 93                        }

 94                }

 95                for ( i = 1; i <= m; ++i ) {
 96                        w[ i ][ i ] = 0;
 97                }

 98                scanf( "%d"&lw );
 99                cl = 0;
100                while ( lw-- > 0 ) {
101                        scanf( "%d%d%d"&a, &b, &c );
102                        ans = solve( t[a], t[b], t[c] );
103                        if ( ans == INF ) {
104                                printf( "Line %d: Impossible to connect!\n"++cl );
105                        }

106                        else {
107                                printf( "Line %d: The minimum cost for this line is %d.\n"++cl, ans );
108                        }

109                }

110        }

111        return 0;
112}

113




H - How to Type

动态规划,f[ 0 ][ i ] 表示输入前 i  个字符后没有大写锁定的最少击键次数,
f[ 1 ][ i ] 表示输入前 i 个字符后大写锁定的最少击键次数。

 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4
 5using namespace std;
 6
 7const int L = 109;
 8
 9int main() {
10        char str[ L ];
11        int td, f[ 2 ][ L ], i, tmp;
12        scanf( "%d"&td );
13        while ( td-- > 0 ) {
14                scanf( "%s", str+1 );
15                memset( f, 0x3fsizeof(f) );
16                f[ 0 ][ 0 ] = 0;
17                for ( i = 1; str[i]; ++i ) {
18                        if ( ('a'<=str[i])&&(str[i]<='z') ) {
19                                tmp = 1 + f[ 0 ][ i - 1 ];
20                                if ( tmp < f[ 0 ][ i ] )  f[ 0 ][ i ] = tmp;
21
22                                tmp = 2 + f[ 1 ][ i - 1 ];
23                                if ( tmp < f[ 0 ][ i ] )  f[ 0 ][ i ] = tmp;
24
25                                tmp = 2 + f[ 0 ][ i - 1 ];
26                                if ( tmp < f[ 1 ][ i ] )  f[ 1 ][ i ] = tmp;
27
28                                tmp = 2 + f[ 1 ][ i - 1 ];
29                                if ( tmp < f[ 1 ][ i ] )  f[ 1 ][ i ] = tmp;
30                        }

31                        else {
32                                tmp = 2 + f[ 0 ][ i - 1 ];
33                                if ( tmp < f[ 0 ][ i ] )  f[ 0 ][ i ] = tmp;
34
35                                tmp = 2 + f[ 1 ][ i - 1 ];
36                                if ( tmp < f[ 0 ][ i ] )  f[ 0 ][ i ] = tmp;
37
38                                tmp = 2 + f[ 0 ][ i - 1 ];
39                                if ( tmp < f[ 1 ][ i ] )  f[ 1 ][ i ] = tmp;
40
41                                tmp = 1 + f[ 1 ][ i - 1 ];
42                                if ( tmp < f[ 1 ][ i ] )  f[ 1 ][ i ] = tmp;
43                        }

44                }

45                printf( "%d\n", f[ 0 ][ i-1 ] );
46        }

47        return 0;
48}

49





比赛时间仓促,自己的做法并非最优。。。

posted on 2011-04-10 18:14 coreBugZJ 阅读(1033) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理