uva127 ``Accordian'' Patience ——链表模拟题

May 13, 2013
Uva

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=63 题目大意：神牛讲的很清楚~http://blog.csdn.net/camelwombat/article/details/5949508 感觉还是首先要读懂题目意思，这个也是有难度的题目思路：　　用数组模拟链表，考的是代码能力，关键是逻辑关系搞清楚，然后再敲，再就是细节问题，代码有一点小错就需要调很久。参考这位神牛的思路写的……http://blog.csdn.net/goomaple/article/details/7802686


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
typedef struct node{
  int len; char rank[54], suit[54];
}node;
node card[54];
void eachmove(int pos, int step) {
  int Len = card[pos-step].len, len = card[pos].len;
  card[pos-step].suit[Len] = card[pos].suit[len-1];
  card[pos-step].rank[Len] = card[pos].rank[len-1];
  card[pos-step].len++; card[pos].len--;
}
void moveremain(int pos) {
  int i, j;
  for (i = pos; card[i+1].len!=0; ++i) {
    for (j = 0; j < card[i+1].len; ++j) {
      card[i].suit[j] = card[i+1].suit[j];
      card[i].rank[j] = card[i+1].rank[j];
    }
    card[i].len = card[i+1].len;
  }
}
int solve() {
  int i, cnt =52, len, Len;
  char suit, rank;
  bool mrk, flag;
  while (1) {
    flag = false;
    for (i= 1; i < cnt;++i) {
      len = card[i].len; 
      suit = card[i].suit[len-1]; 
      rank = card[i].rank[len-1]; 
      mrk = false;
      if (i >= 3)  {
        Len = card[i-3].len;
        if (suit == card[i-3].suit[Len-1] || rank== \
            card[i-3].rank[Len-1]) {
          eachmove(i, 3);
          if (card[i].len==0) {
            moveremain(i);
            cnt--; card[cnt].len = 0;
          }
          mrk = flag = true;
        }
      }
      if (!mrk && i >= 1) {
        Len = card[i-1].len;
        if (suit == card[i-1].suit[Len-1] || rank== \
            card[i-1].rank[Len-1]) {
          eachmove(i, 1);
          if (card[i].len==0) {
            moveremain(i); 
            cnt--; card[cnt].len = 0;
          }
          flag = true;
        }
      }
      if (flag) break;
    }
    if (!flag) break;
  }
  return cnt;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("uva127.in", "r", stdin);
#endif
  int i, j;
  while (1) {
    scanf("%c", &card[0].rank[0]);
    if (card[0].rank[0] == '#') break;
    scanf("%c", &card[0].suit[0]);
    card[0].len = 1;
    for (i = 1; i < 52; ++i) {
      getchar();
      scanf("%c%c", &card[i].rank[0], &card[i].suit[0]);
      card[i].len = 1;
    }
    card[52].len = 0;
    int cnt = solve();
    if (cnt > 1) printf("%d piles remaining:", cnt);
    else printf("%d pile remaining:", cnt);
    for (j = 0; j < cnt; ++j) printf(" %d", card[j].len);
    printf("\n");
    getchar();
  }

  return 0;
}

这种题目，非常锻炼代码的准确度什么的……

Read more