題目鏈接：
http://acm.hust.edu.cn:8080/judge/contest/viewContest.action?cid=1465A - Number Sequence
模式匹配，KMP 算法。
1
#include <iostream>
2#include <cstdio>
3
4using namespace std;
5
6template<class T>
7
void 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, 0, sizeof(inq) );
21 que[ qh ] = a;
22 inq[ a ] = 1;
23 memset( f, 0x3f, sizeof(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 *y = (double)(c*e-a*g) / (a*f-b*e);
18 *x = (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< int, int > cnt;
19 map< int, int >::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, 0x2f, sizeof(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, 0x2f, sizeof(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, 0x3f, sizeof(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
比賽時間倉促，自己的做法并非最優。。。