-- 作者:fantasyorg
-- 发布时间:3/24/2010 10:44:00 PM
-- 2010年PKUCS复试上机总结
零、写在前面 大约一年前,我在王道上看到了kaluzny学长的PKUCS考研总结,很受激励,走上了PKU的考研之路,本来想考完之后也写一篇总结,可惜自己考的实在太挫,我写的总结估计会给学弟学妹们起到副作用。所以我就不写考研的总结了,我写一个复试上机的总结吧。 准备11年考研的同学,不必这个时候准备上机,毕竟初试过不了是没有机会上机的。 一、题目列表: http://poj.grids.cn/contest/1779/ 比赛最终结果(点击Standing): http://poj.grids.cn/contest/1779/standing/ 如果大家想看某个同学A题的整个过程,点击Status,然后在User Name中输入这个同学的id。 二、解题报告: A题: A题是送分题 B题: B题机试时我看到数据量比较小(100),就暴力了一个。枚举所有的子串,看看这个子串在给出的串中的出现次数, 把超过一次的子串存储起来,然后排序输出。 C题: C题枚举A-L中的硬币为轻或者重,看看是否符合题目给出的条件。 D题: 用unsigned short存储数据,看二进制形式最高位为1就左移,然后+1;如果最高位为零,就左移。 这样完成了一个循环左移的过程,循环16次,看看能不能使给出的两个数字相等。 E题: 0-1背包 F题: 数据结构课上都做过这个作业吧。。。 G题: 最小生成树,prim代码比较短,我用了prim 三、参考代码: 机试的时候主要是为了用最快的速度AC,所以不怎么讲究代码的可读性,也有冗余的地方,写的很挫,见笑。 下面是我在机试时写的代码(一个字符也没改过呀)。 A: #include<iostream> using namespace std; int main() { double cur, sum = 0; for( int i = 0; i < 12; i ++ ) { scanf( "%lf", &cur ); sum += cur; } cout << "$" << sum / 12 << endl; } B: #include<iostream> #include<cstdlib> #include<cstring> using namespace std; const int MAX = 105; char buffer[ MAX ]; struct Node { char str[ MAX ]; int cnt; }nList[ MAX * 10 ]; int nLstCnt; bool inList( char *str ) { for( int i = 0; i < nLstCnt; i ++ ) if ( strcmp( nList[ i ].str, str ) == 0 ) return true; return false; } int strSearch( char *dst, int lend, char *src, int lens ) { int i, j; int cnt = 0; for( i = 0; i <= lend - lens; i ++ ) if ( dst[ i ] == src[ 0 ] ) { for( j = 1; j < lens; j ++ ) if ( dst[ i + j ] != src[ j ] ) break; if ( j == lens ) cnt ++; } return cnt; } void solve() { int i, j; char cur[ MAX ]; int len = strlen( buffer ); int curCnt; nLstCnt = 0; for( i = 0; i < len; i ++ ) { int index = 0; for( j = i; j < len; j ++ ) { cur[ index ++ ] = buffer[ j ]; cur[ index ] = '\0'; if ( !inList( cur ) ) { curCnt = strSearch( buffer, len, cur, index ); if ( curCnt > 1 ) { nList[ nLstCnt ].cnt = curCnt; strcpy( nList[ nLstCnt ].str, cur ); nLstCnt ++; } } } } } int cmp( const void *a, const void *b ) { return strcmp( ((Node*)a)->str, ((Node*)b)->str ); } void print() { qsort( nList, nLstCnt, sizeof( Node ), cmp ); for( int i = 0; i < nLstCnt; i ++ ) printf( "%s %d\n", nList[i].str, nList[i].cnt ); } int main() { while( scanf( "%s", buffer ) != EOF ) { solve(); print(); } return 0; } C: #include<iostream> #include<cstring> using namespace std; const int MAX = 15; int N; enum Type{ Up, Down, Even }; char test[3][2][ MAX ]; int result[3]; void read() { int i; char buffer[ 100 ]; for( i = 0; i < 3; i ++ ) { scanf( "%s %s %s", test[i][0], test[i][1], buffer); if ( strcmp( buffer, "up" ) == 0 ) result[ i ] = Up; else if ( strcmp( buffer, "down" ) == 0 ) result[ i ] = Down; else result[ i ] = Even; } } bool inStr( char *dst, char ch ) { for( int i = 0; dst[ i ] != '\0'; i ++ ) if ( ch == dst[ i ] ) return true; return false; } void solve() { int i, j, k; char cur; for( i = 0; i < 12; i ++ ) for( j = 0; j < 2; j ++ ) { cur = char( 'A' + i ); for( k = 0; k < 3; k ++ ) { int l = 0, r = 0; if ( inStr( test[k][0], cur ) ) if ( j ) l = 1; else l = -1; if ( inStr( test[k][1], cur ) ) if ( j ) r = 1; else r = -1; if ( result[k] == Up ) if (!( l > r ) ) break; if ( result[k] == Down ) if ( !( l < r) ) break; if ( result[k] == Even ) if ( !( l == r ) ) break; } if ( k == 3 ) { if ( j == 0 ) printf( "%c is the counterfeit coin and it is light.\n", char(i + 'A') ); else printf( "%c is the counterfeit coin and it is heavy.\n", char(i + 'A') ); return; } } } int main() { scanf( "%d", &N ); while( N -- ) { read(); solve(); } return 0; } D: #include<iostream> using namespace std; const unsigned short BASE = 0x8000; const unsigned short BASE1 = 0x7fff; int N; unsigned short a, b; unsigned short cycleLeft( unsigned short x ) { if ( x & BASE ) { x = x & BASE1; x = x * 2 + unsigned short(1); } else { x = x * 2; } return x; } bool solve() { for( int i = 0; i < 16; i ++ ) { if ( a == b ) return true; else a = cycleLeft( a ); } return false; } int main() { scanf( "%d", &N ); for( int i = 0; i < N; i ++ ) { cin >> a >> b; if ( solve() ) puts( "YES" ); else puts( "NO" ); } return 0; } E: #include<iostream> using namespace std; const int MAXN = 105; const int MAXC = 1005; int p[ MAXN ], sc[ MAXN ]; int N, C; int d[ MAXN ][ MAXC ]; inline int max2( int a, int b ) { return a > b ? a : b; } void read() { int i; for( i = 1; i <= N; i ++ ) { scanf( "%d %d", &p[i], &sc[i] ); } } int pkg() { int i, j; for( i = 0; i <= C; i ++ ) d[0][i] = 0; for( i = 1; i <= N; i ++ ) for( j = 0; j <= C; j ++ ) { if ( j < p[i] ) d[ i ][ j ] = d[ i - 1 ][ j ]; else { d[ i ][ j ] = max2( d[ i - 1 ][ j ], d[ i - 1 ][ j - p[ i ] ] + sc[ i ] ); } } return d[ N ][ C ]; } int main() { while( scanf( "%d %d", &C, &N ) != EOF ) { read(); printf( "%d\n", pkg() ); } return 0; } F: #include<iostream> using namespace std; const int MAXN = 105; char buffer[ MAXN ]; int eList[ MAXN ]; struct Node { int type; // 0, zuokuohao, 1, youkuohao int pos; }; template<typename Comparable> class Stack { public: void init() {top = -1;} void push( const Comparable &x ) { a[ ++top ] = x; } Comparable pop() { return a[top--]; } bool isEmpty() { return top == -1; } private: Comparable a[ MAXN * 2 ]; int top; }; Stack<Node> stack; void solve() { stack.init(); int i; for( i = 0; i < MAXN; i ++ ) eList[ i ] = -1; Node x, t; for( i = 0; buffer[ i ] != '\0'; i ++ ) { if ( buffer[ i ] == '(' ) { x.pos = i; x.type = 0; stack.push( x ); } else if ( buffer[ i ] == ')' ) { x.pos = i; x.type = 1; if ( !stack.isEmpty() ) { t = stack.pop(); if ( t.type == 1 ) eList[ t.pos ] = 1; } else { eList[ i ] = 1; } } } while( !stack.isEmpty() ) { x = stack.pop(); eList[ x.pos ] = 0; } puts( buffer ); for( i = 0; buffer[ i ] != '\0'; i ++ ) { if ( eList[ i ] == 0 ) putchar( '$' ); else if ( eList[ i ] == 1 ) putchar( '?' ); else putchar( ' ' ); } putchar( '\n' ); } int main() { while( gets( buffer ) ) { solve(); } return 0; } G: #include<iostream> using namespace std; const int INF = 123456789; const int MAXN = 50; int N; int g[ MAXN ][ MAXN ]; int dist[ MAXN ]; bool visited[ MAXN ]; void read() { int i, j; for( i = 0; i < N; i ++ ) for( j = 0; j < N; j ++ ) g[ i ][ j ] = 0; char u, v; int w, num; for( j = 0; j < N - 1; j ++ ) { cin >> u >> num; for( i = 0; i < num; i ++ ) { cin >> v >> w; g[ u - 'A' ][ v - 'A' ] = w; g[ v - 'A' ][ u - 'A' ] = w; } } } int prim( int begin ) { int i; int res = 0; for( i = 0; i < N; i ++ ) { dist[ i ] = INF; visited[ i ] = false; } dist[ begin ] = 0; while( true ) { int minn = INF, mini = -1; for( i = 0; i < N; i ++ ) if ( !visited[ i ] && dist[ i ] < minn ) { minn = dist[ i ]; mini = i; } if ( mini == - 1 ) break; visited[ mini ] = true; res += dist[ mini ]; for( i = 0; i < N; i ++ ) if ( g[ mini ][ i ] ) { if ( !visited[ i ] && dist[ i ] > g[ mini ][ i ] ) { dist[ i ] = g[ mini ][ i ]; } } } return res; } int main() { while( cin >> N && N ) { read(); printf( "%d\n", prim( 0 ) ); } return 0; } 四、一些可能有用的信息 初试结束后,大家一定要练习机试,不要眼高手低,以为自己把算法或者别人的代码看懂了,就万事大吉了,一定要动手,不然你会在机试的当天很郁闷(牛人除外)。机试成绩一定和你的代码量是成正比的。 此外,2010年的机试用的电脑上貌似编译器有vc6(这个一定有,我就用这个写的)和vs2005(我看到了一个图标,貌似是有),其他的没怎么注意。建议大家使用vc6练习。这次考试的用户名是ss+你准考证号的后8位。 练习机试时,大家可以在acm.pku.edu.cn或者poj.grids.cn(考试用的系统)上练习。 此外,机试在复试中有什么样的地位我不是很清楚,我只知道怎么去把机试准备好。 附件中还有两个我认为比较好的题目分类(acm.pku.edu.cn上的)和一些代码,希望对大家有帮助。 一些可能和考研复试相近的测试 http://poj.grids.cn/contest/1749/ http://poj.grids.cn/contest/1748/ http://poj.grids.cn/contest/1747/ http://poj.grids.cn/contest/1661/ http://poj.grids.cn/contest/1608/ http://poj.grids.cn/contest/1607/
|