POJ 3690 星座

文章发布时间:2009/8/12/8/34

今天不知是没睡好,还是心情不好...上午黑压压的乌云叫人喘不上气,被星座折腾了一上午....

可能真的是晕了,粗粗看过题目,发现是个基本的串匹配问题,于是马上动手,C++了一个位比较的KMP,提交....超时...我晕,看看题目要求3s,不会这么慢吧?看看状态,第一200+ms,C语言,代码也很短,估计是牛人用汇编了....
于是乎,改,改,改,用点空间换时间,一次比较一行,老把戏,位运算,提交,又超时~~我晕....RP爆发了,最后试一试,把代码改成C的,算法没变,提交, Wrong Answer 我靠~~彻底崩溃了.....怎么会Wrong呢?经过我摸爬滚打,终于发现了,题目的意思是匹配星座,星座天上应该是一对一,一个模式匹配一个,要么没有,要么就一个,我的算法默认匹配多个,加个break,再提交.....崩溃了,AC,1061ms,还排到了41名.原来POJ给的测试数据有问题阿,就是说一片天空不止有一模式的星座,难怪我的程序总超时,1000*1000的天空,里面有机个重复不就相当于自己多算了几遍? 看来POJ出题人自己也有粗心的时候 ...

另外一个郁闷地方就是编译器生成的C与C++代码,在算法完全相同的情况下差距怎么这么大呢?我在本地看了下生成的程序的汇编代码,觉得除了C++模型的代码g++和gcc生成的目标代码基本一致,那些附加代码基本没有复杂运算,所以我推测,可能是POJ自己的沙盒在统计时有问题....只能这样臆断了....
上代码:
C的,AC, 1061ms 还排到了41,C++的,提交就超时.....

 
  /*
  *@summery:  POJ problem id : 3690
  *@author: antmanler
  *2009.08.11
  */
  #include <stdio.h>
  #define MAX_MAP_SIZE (1000)
  #define MAX_TEP_SIZE (50)
  long long map[MAX_MAP_SIZE][MAX_MAP_SIZE] ;
  long long tep[MAX_MAP_SIZE] ;
  long long masks[MAX_TEP_SIZE] ;
  

  int main(){
  int m = 1;
  int case_cnt = 0 ;
  int i = 0, j = 0, k = 0, p = 0, ti = 0, tj = 0;
  int N = 0, M = 0, T = 0, P = 0, Q = 0 ;
  char input ;
  int validate = 0 ;
  int tc = 0;
  int rwo_uval = 0, col_uval = 0;
  int row = 0;
  int col = 0;
  masks[0] = 1 ;
  

  for(; m < MAX_TEP_SIZE; m++) masks[m] = (masks[m-1]<<1)|1 ;
  scanf("%d %d %d %d %d", &N, &M, &T, &P, &Q);
  while(!(0==N && 0==M)) {
  getchar();
  for (i = 0; i < N; i++) {
  map[i][0] = 0 ;
  for (j = 0; j < Q; j++){
  input = getchar();
  map[i][0] <<= 1;
  map[i][0] |= ('*'==input) ;
  }
  for (k = 1; j < M; j++, k++ ) {
  input = getchar() ;
  map[i][k] = (map[i][k-1]<<1|('*'==input))&masks[Q-1] ;
  
  }
  getchar();
  }
  

  validate = 0 ;
  for (tc = 0; tc < T; tc++ ) {
  input = getchar();
  for (ti = 0; ti < P; ti++) {
  tep[ti] = 0 ;
  

  for (tj = 0; tj < Q; tj++ ) {
  input = getchar();
  tep[ti] <<= 1;
  tep[ti] |= ('*'==input);
  }
  getchar();
  }
  if( P > N || Q > M ) continue ;
  

  rwo_uval = N-P+1 ;
  col_uval = M-Q+1 ;
  for ( row = 0; row < rwo_uval; row++ ) {
  for ( col = 0; col < col_uval; col++ ) {
  for ( p = 0; p < P; p++ ) {
  if (!(map[row+p][col]&tep[p])) goto _next_ ;
  }
  validate++;
  goto _find_next_;
  _next_:
  continue;
  

  }
  

  }
  _find_next_:
  continue;
  }
  printf("Case %d: %d\n", ++case_cnt, validate);
  scanf("%d %d %d %d %d", &N, &M, &T, &P, &Q);
  }
  return 0;
  }
 

C++ 的,算法一模一样

 
  /*
  *@summery:  POJ problem id : 3690
  *@author: antmanler
  *2009.08.11
  */
  #include <iostream>
  #define MAX_MAP_SIZE (1000)

  #define MAX_TEP_SIZE (50)
 
  long long map[MAX_MAP_SIZE][MAX_MAP_SIZE] ;
  
  long long tep[MAX_MAP_SIZE] ;
 
  long long masks[MAX_TEP_SIZE] ;

  int main(){
  
  using namespace std;

  masks[0] = 1 ;

  for(int m = 1; m < MAX_TEP_SIZE; m++) masks[m] = (masks[m-1]<<1)|1 ;
  int case_cnt = 0 ;
  
  int N = 0, M = 0, T = 0, P = 0, Q = 0 ;
  
  cin >> N >> M >> T >> P >> Q ;
  while(!(0==N && 0 == M)) {
  char input ;
  for ( int i = 0; i < N; i++) {
  int j = 0;
 
  map[i][0] = 0 ;
  for (; j < Q; j++){
  cin >> input ;
  map[i][0]<<=1;
  map[i][0]|= ('*'==input) ;
  }
  
  for (int k = 1; j < M; j++, k++ ) {
  cin >> input ;
  
  map[i][k] = (map[i][k-1]<<1|('*'==input))&masks[Q-1] ;
  }
  }
  
  int validate = 0 ;
  for (int tc = 0; tc < T; tc++ ) {
  char input = 0;
  
  for ( int i = 0; i < P; i++) {
  tep[i] = 0 ;
  for ( int j = 0; j < Q; j++ ) {
  cin>>input ;
  
  tep[i]<<=1;
  tep[i]|=('*'==input);
  }
  

  }
  

  if( P > N || Q > M ) continue ;
  int rwo_uval = N-P+1,
  col_uval = M-Q+1;
  for ( int row = 0; row < rwo_uval; row++ ) {
  for ( int col = 0; col < col_uval; col++ ) {
  for (int p = 0; p < P; p++) {
  
  if ( map[row+p][col] != tep[p] ) goto _next_ ;
  }
  validate++;
  goto _find_more_;
  _next_:
  continue;
  

  }
  }
  
  _find_more_:
  continue;
  }
  
  cout << "Case " << ++case_cnt <<" : " << validate << endl ;
  cin >> N >> M >> T >> P >> Q ;
  
  }
  return 0;
 
 }