计算机科学论坛--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/


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	124.023ms