题目链接:
http://acm.hust.edu.cn:8080/judge/contest/viewContest.action?cid=1465A - Number Sequence
模式匹配,KMP 算法。
1
#include <iostream>
2
#include <cstdio>
3
4
using namespace std;
5
6
template<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
}
15
template<class T>
16
int 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
25
const int N = 1000009;
26
const int M = 10009;
27
28
int a[ N ], b[ M ], link[ M ], n, m;
29
30
int 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
4
using namespace std;
5
6
const int L = 1009;
7
8
char s[ L ];
9
10
int 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
5
using namespace std;
6
7
const int N = 209;
8
const int INF = 0x3f3f3f3f;
9
const int QL = N;
10
11
int n, a, b, k[ N ];
12
13
int 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
55
int 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
4
using namespace std;
5
6
typedef long long Lint;
7
8
Lint cross( Lint ax, Lint ay, Lint bx, Lint by )
{
9
return ax*by - ay*bx;
10
}
11
12
int 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
16
int 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
26
double ix, iy;
27
28
int 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
39
int 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
6
using namespace std;
7
8
int 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
4
using namespace std;
5
6
int 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
6
using namespace std;
7
8
const int N = 10009;
9
const int M = 509;
10
const int INF = 0x2f2f2f2f;
11
12
int disA[ M ], disB[ M ], disC[ M ];
13
int preA[ M ], preB[ M ], preC[ M ];
14
15
int w[ M ][ M ], m, n, t[ N ];
16
17
int 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
39
void 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
68
int 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
81
int 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
5
using namespace std;
6
7
const int L = 109;
8
9
int 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
比赛时间仓促,自己的做法并非最优。。。