NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2007國中組決賽
 [C++] 2007 NPSC 國中組決賽 C. 國家寶藏

作者 主題: [C++] 2007 NPSC 國中組決賽 C. 國家寶藏  (閱讀 2439 次)

bleed1979

  • 初級會員
  • **
  • 文章數: 28
    • 檢視個人資料
[C++] 2007 NPSC 國中組決賽 C. 國家寶藏
« 於: 七月 21, 2010, 05:51:20 am »

本題同ZJ的b082。

題目目的︰每張骨牌前後各有一個數字,和骨牌所代表的字元,給定最初的骨牌,依照骨牌前面數字串接骨牌後面數字的方式,將所有代表字元輸出。

解題技巧︰如果把所有骨牌資料都以陣列或vector形式儲存起來,在測資不多的情況下,直接查找就可以了。

代碼: [選擇]
// C++, NPSC 2007 junior second C., ZJ b082

#include <cstdio>
#include <vector>

using namespace std;

struct Domino
{
  Domino ( int f, char c, int b ) : front ( f ), back ( b ), alphabet ( c ) {}
  int front, back;
  char alphabet;
};

int main ()
{
  int cases, r;
 
  r = scanf ( "%d", &cases );
 
  while ( cases-- )
  {
    int N;
   
    r = scanf ( "%d", &N );
   
    vector< Domino > vec;
    vec.clear ();
   
    int x, y, start;
    char c;
   
    r = scanf ( "%d %c %d", &x, &c, &y );
    Domino d ( x, c, y );
    vec.push_back ( d );
    start = x;
   
    for ( int i = 1; i != N; ++i )
    {
      r = scanf ( "%d %c %d", &x, &c, &y );
       
      Domino d ( x, c, y );
      vec.push_back ( d );
    }
   
    int size = vec.size ();
    for ( x = 0; x != size; ++x )
      if ( vec[ x ].front == start )
        break;
   
    putchar ( vec[ x ].alphabet );
   
    y = vec[ x ].back;
   
    for ( int i = 1; i != size; ++i )
    {
      for ( x = 0; x != size; ++x )
        if ( vec[ x ].front == y )
          break;
         
      putchar ( vec[ x ].alphabet );
     
      y = vec[ x ].back;
    }
   
    puts ( "" );
  }
 
  return ( 0 );
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: [C++] 2007 NPSC 國中組決賽 C. 國家寶藏
« 回覆 #1 於: 十二月 21, 2011, 10:01:46 am »

直接查找是O(N^2)的做法,這裡提供O(N)的做法給大家參考,
宣告一個大小為256的陣列,有點類似以陣列模擬Linked-List的做法,
每格記錄該號碼存放的字元以及下一個元素的號碼,
只要記住第一個元素的號碼,接下來用一層的迴圈即可完成。

代碼: [選擇]
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int next[256], n, m, s, i, a;
    char ch[256], c;
    cin >> n;
    while (n--)
    {
        cin >> m;
        cin >> s;
        cin >> ch[s] >> next[s];
        for (i=1; i<m; i++)
        {
            cin >> a;
            cin >> ch[a] >> next[a];
        }
        for (i=0, a=s; i<m; i++, a=next[a])
            cout << ch[a];
        cout << endl;
    }
    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2007國中組決賽
 [C++] 2007 NPSC 國中組決賽 C. 國家寶藏