NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » bleed1979 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - bleed1979

頁: [1] 2
1
本題同ZJ的b035。

題目目的︰計算所有數的平方和。

解題技巧︰依序讀入計算後輸出。

代碼: [選擇]
//  C++, NPSC 2006 junior second D., ZJ b035

#include <cstdio>

int main ()
{
  int N;
 
  while ( ~ scanf ( "%d", &N ) && N )
  {
    int square_sum = 0, num, r;
   
    for ( int i = 0; i != N; ++i )
    {
      r = scanf ( "%d", &num );
     
      square_sum += num * num;
    }
   
    printf ( "%d\n", square_sum );
  }
 
  return ( 0 );
}

2
NPSC2006國中組決賽 / [C++] 2006 NPSC 國中組決賽 C. 兩個油瓶
« 於: 七月 22, 2010, 04:04:46 am »
本題同ZJ的b034。

題目目的︰求二元一次不定方程是否有整數解。

解題技巧︰因為只需回答Yes或No,計算ax + by = c 中,a和b的最大公因數是否可以整除c即可。

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

#include <cstdio>

int GCD ( int x, int y )
{
  return ( ! y ? x : GCD( y, x % y ) );
}

int main ()
{
  int a, b, c;
 
  while ( ~ scanf ( "%d%d%d", &a, &b, &c ) && ( a + b + c ) )
  {
    int gcd = GCD ( a, b );
   
    printf ( "%s\n", ( ! ( c % gcd ) ) ? "Yes" : "No" );
  }
 
  return ( 0 );
}

3
NPSC2007國中組決賽 / [C++] 2007 NPSC 國中組決賽 G. 折方塊
« 於: 七月 21, 2010, 08:30:16 am »
本題同ZJ的b086。

題目目的︰在3 x 6的區域裡,以o代表立方體的一面,x代表沒有。輸出是否能折疊成立方體。

解題技巧︰分成4個階段判斷。
第1階段︰判斷所有o必有一個以上相鄰的o,即圖形應是連通的。
第2階段︰判斷必為(1, 4, 1) (2, 3, 1) (3, 3, 0) (2, 2, 2)的組合。此階段可以判斷出(1, 4, 1)
第3階段︰計算以row為單位,相鄰o的總和。比如(3, 3, 0)的對應總和是(5, 5, 0)。此階段可判斷出(2, 3, 1)和(3, 3, 0)。
第4階段︰針對(2, 2, 2),以column計算點數,必為1, 2, 2, 1。此階段判斷出(2, 2, 2)。至此全部已判斷。

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

#include <iostream>
#include <string>

using namespace std;

int main ()
{
  int adj[ 4 ][ 2 ] = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
  int cube[ 6 ][ 3 ] = { { 1, 4, 1 },
                         { 2, 3, 1 }, { 1, 3, 2 },
                         { 3, 3, 0 }, { 0, 3, 3 },
                         { 2, 2, 2 } };
  /*
   (2, 3, 1)
      XX
    XXX
      X
     
      XX
    XXX
     X
     
      XX
    XXX
    X
   
   (3, 3)
    XXX
      XXX

   (2, 2, 2)
       XX
      XX
     XX
  */
  int connected_sum[ 6 ][ 3 ] = { { 1, 8, 1 },
                                  { 3, 6, 1 }, { 1, 6, 3 },
                                  { 5, 5, 0 }, { 0, 5, 5 },
                                  { 3, 4, 3 } };
 
  int cases;
 
  cin >> cases;
  while ( cin.get () != '\n' )
    ;
 
  string graphic[ 3 ];
 
  while ( cases-- )
  {
    for ( int i = 0; i != 3; ++i )
      getline ( cin, graphic[ i ], '\n' );
   
    bool success = false;
    int circle[ 3 ] = { 0 }, neighbor[ 3 ] = { 0 }, column[ 6 ] = { 0 };
   
    for ( int i = 0; i != 3; ++i )
      for ( int j = 0; j != 6; ++j )
      {
        if ( graphic[ i ][ j ] == 'o' )
        {
          ++circle[ i ];
          ++column[ j ];
          bool is_connected = false;
          for ( int k = 0; k != 4; ++k )
          {
            int y = i + adj[ k ][ 0 ], x = j + adj[ k ][ 1 ];
            if ( y >= 0 && y < 3 &&
                 x >= 0 && x < 6 &&
                 graphic[ y ][ x ] == 'o' )
            {
              is_connected = true;
              ++neighbor[ i ];
            }
          }
          success = is_connected;
          if ( success == false )
            goto SEARCH_END;
        }
      }

SEARCH_END:

    if ( ! success )
      cout << "no" << endl;
    else
    {
      success = false;
      for ( int i = 0; i != 6; ++i )
      {
        int j;
        for ( j = 0; j != 3; ++j )
          if ( circle[ j ] != cube[ i ][ j ] )
            break;
        if ( j == 3 )
        {
          if ( neighbor[ 0 ] == connected_sum[ i ][ 0 ] &&
               neighbor[ 1 ] == connected_sum[ i ][ 1 ] &&
               neighbor[ 2 ] == connected_sum[ i ][ 2 ] )
          {
            if ( i != 5 )  // if not (2, 2, 2)
            {
              success = true;
              break;
            }
            else if ( ( column[ 0 ] == 1 && column[ 1 ] == 2 && column[ 2 ] == 2 && column[ 3 ] == 1 ) ||
                      ( column[ 1 ] == 1 && column[ 2 ] == 2 && column[ 3 ] == 2 && column[ 4 ] == 1 ) ||
                      ( column[ 2 ] == 1 && column[ 3 ] == 2 && column[ 4 ] == 2 && column[ 5 ] == 1 ) )
            {
              success = true;
              break;
            }
          }
        }
      }
     
      cout << ( ( success ) ? "yes" : "no" ) << endl;
    }
  }
 
  return ( 0 );
}

4
NPSC2007國中組決賽 / [C++] 2007 NPSC 國中組決賽 F. 數格子點
« 於: 七月 21, 2010, 06:14:23 am »
本題同ZJ的b085。

題目目的︰給定起點和終點座標皆在整數位置的一條直線。問此直線的整數座標點有幾個?

解題技巧︰應該都知道要計算斜率。但會有斜率0和無限大的情況,分開做即可。

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

#include <cstdio>
#include <cstdlib>
#include <cmath>

int main ()
{
  int cases, r;
 
  r = scanf ( "%d", &cases);
 
  while ( cases-- )
  {
    int x1, y1, x2, y2;
   
    r = scanf ( "%d%d%d%d", &x1, &y1, &x2, &y2 );
   
    int count = 0;
   
    if ( x1 == x2 )
    {
      if ( y1 == y2 )
        count = 1;
      else
        count = abs ( y2 - y1 ) + 1;
    }
    else if ( y1 == y2 )
    {
      count = abs ( x2 - x1 ) + 1;
    }
    else
    {
      double m = ( double )( y2 - y1 ) / ( x2 - x1 );
     
      int step = ( x2 > x1 ) ? 1 : -1;
     
      for ( int i = x1; i != x2; i += step )
      {
        double newy = ( i - x1 ) * m + y1;
       
        if ( fabs ( newy - ( int ) newy ) < 1e-9 )
          ++count;
      }
     
      ++count;  // point (x2, y2)
    }
   
    printf ( "%d\n", count );
  }
 
  return ( 0 );
}

5
NPSC2007國中組決賽 / [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 );
}

6
NPSC2007國中組決賽 / [C++] 2007 NPSC 國中組決賽 B. 友好數
« 於: 七月 20, 2010, 10:19:59 pm »
本題同ZJ的b081。

題目目的︰計算某數除了自己以外的所有因數的和,令為和1。這個和1除了自己以外的所有因數的和2等於某數。則和1和某數互為友好。

解題技巧︰計算兩次的因數分解。參考程式的方式是比較慢的,比較快的方式可以考慮dfs。

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

#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

void find_factor ( vector< int >& A, int N )
{
  int work, fact = 2;
 
  A.push_back ( 1 );
 
  if ( N != 1 )
  {
    unsigned int limit = 1;
   
    // test 2
    for ( work = N; work > 1 && ! ( work & 1 ); work >>= 1, fact <<= 1 )
      for ( unsigned int i = 0; i < limit && i != A.size (); ++i )
        A.push_back( fact * A[ i ] );
   
    // test from odd number from 3 to sqrt(N)
    double sqrt1 = sqrt ( N );
    int sqrt2 = ( int )sqrt1, odd;
   
    for ( odd = fact = 3; work > 1 && odd < sqrt2; odd += 2, fact = odd )
    {
      limit = A.size ();
      while ( ( work % odd ) == 0 )
      {
        for ( unsigned int i = 0; i < limit && i != A.size (); ++i )
            A.push_back( fact * A[ i ] );
        work /= odd;
        fact *= odd;
      }
    }
   
    if ( work > 1 )
    {
      limit = A.size ();
      for ( unsigned int i = 0; i < limit && i != A.size (); ++i )
        A.push_back( work * A[ i ] );
    }
   
    if ( sqrt1 - sqrt2 < 1e-9 )
    {
      unsigned int i;
      for ( i = 0; i != A.size (); ++i )
        if ( A[ i ] == sqrt2 )
          break;
      if ( i == A.size () )
        A.push_back ( sqrt2 );
    }
  }
}

int main ()
{
  int N;
 
  while ( ~ scanf ( "%d", &N ) && N )
  {
    vector< int > fact;
   
    find_factor( fact, N );
   
    int M = 0;
    for ( unsigned int i = 0; i != fact.size (); ++i )
      if ( fact[ i ] < N )
        M += fact[ i ];
     
    fact.clear ();
    find_factor ( fact, M );
   
    int K = 0;
    for ( unsigned int i = 0; i != fact.size (); ++i )
      if ( fact[ i ] < M )
        K += fact[ i ];
     
    if ( K == N )
    {
      if ( M == N )
        printf ( "=%d\n", N );
      else
        printf ( "%d\n", M );
    }
    else
      puts ( "0");
  }
 
  return ( 0 );
}

7
NPSC2007國中組決賽 / [C++] 2007 NPSC 國中組決賽 A. 畢氏定理
« 於: 七月 20, 2010, 09:29:02 pm »
本題同ZJ的b080。

題目目的︰給定兩個數字,判斷是否為直角三角形的其中兩邊。如果是,輸出第三邊。否則輸出Wrong。

解題技巧︰使用直角三角形的公式,檢查兩次即可。

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

#include <cstdio>
#include <cmath>

#define SWAP(t, a, b) { t c; c = a; a = b; b = c; }

int main ()
{
  int N, M;
 
  while ( ~ scanf ( "%d%d", &N, &M ) && ( N + M ) )
  {
    if ( N < M )
      SWAP(int, N, M);
     
    double K = sqrt( N * N - M * M );
   
    if ( K - ( int )K < 1e-9 )
      printf ( "%d\n", ( int )K );
    else
    {
      double K2 = sqrt( N * N + M * M );
     
      if ( K2 - ( int )K2 < 1e-9 )
        printf ( "%d\n", ( int )K2 );
      else
        printf ( "Wrong\n" );
    }
  }
 
  return ( 0 );
}

8
NPSC2007國中組初賽 / [C++] 2007 NPSC 國中組初賽 F. 鬧鐘
« 於: 七月 18, 2010, 08:46:48 am »
本題同ZJ的b079。

題目目的︰根據題目給定的數學式,計算任意n ( 最大一百萬 ) 時,數學式所求得的值。

解題技巧︰如果每次都要跑n次計算就太慢了。將所有值預先計算存在陣列裡。

代碼: [選擇]
//  C++, ZJ b079, NPSC 2007 F. junior first

#include <cstdio>

#define SIZE  1000001

int A[SIZE];

int main ()
{
  A[ 1 ] = A[ 2 ] = 1;
  for ( int i = 3; i != SIZE; ++i )
    A[ i ] = A[ i - A[ i - 1 ] ] + A[ i - 1 - A[ i - 2 ] ];
   
  int n;
 
  while ( ~ scanf ( "%d", &n ) && n )
  {
    printf ( "%d\n", A[ n ] );
  }
 
  return ( 0 );
}

9
NPSC2007國中組初賽 / [C++] 2007 NPSC 國中組初賽 E. 白飯
« 於: 七月 18, 2010, 08:37:05 am »
本題同ZJ的b078。

題目目的︰計算序列中低於平均值的數字的個數。

解題技巧︰由於都是不大於100的整數,在計算平均值時,記得轉換型態為浮點數。避免整數除法的錯誤。

代碼: [選擇]
//  C++, ZJ b078, NPSC 2007 E. junior first

#include <cstdio>

int main ()
{
  int n, r;
 
  while ( ~ scanf ( "%d", &n ) && n )
  {
    double avg;
    int grades[1000], total_grades = 0, count = 0;
   
    for ( int i = 0; i != n; ++i )
    {
      r = scanf ( "%d", &grades[i] );
      total_grades += grades[i];
    }
   
    avg = ( double ) total_grades / n;
   
    for ( int i = 0; i != n; ++i )
      count += ( grades[i] < avg );
   
    printf ( "%d\n", count );
       
  }
 
  return ( 0 );
}

10
本題同ZJ的b077。

題目目的︰判斷測資的第二個數是否大於等於第一個數。

解題技巧︰測資的範圍仍在g++的unsigned long long範圍內,直接比大小即可。

代碼: [選擇]
// C++, NPSC 2007 C., junior first

#include <cstdio>

int main ()
{
  unsigned long long v1, v2;
 
  while ( ~ scanf ( "%llu%llu", &v1, &v2 ) && ( v1 + v2 ) )
  {
    printf ( "%s\n", ( ( v2 >= v1 ) ? "Fair" : "Unfair" ) );
  }
 
  return ( 0 );
}

11
本題同ZJ的b076。

題目目的︰測資是   人名1 人名2 關係值   的格式,要輸出關係值最小並且為負數的那一組人名1和人名2。如果所有關係值都不是負數,輸出題目規定的特定字串。

解題技巧︰令一個變數值為0,然後依序讀入資料。如果關係值比此變數小,則紀錄人名和更新變數。最後再看變數是否改變來作輸出。

代碼: [選擇]
//  C++, ZJ b076, NPSC 2007 junior first

#include <cstdio>
#include <cstring>

#define NAME_LENGTH  11

int main ()
{
  int cases, r;
 
  r = scanf ( "%d", &cases );
 
  while ( cases-- )
  {
    int g;  // group for girls
   
    r = scanf ( "%d", &g );
   
    char girl1[NAME_LENGTH], girl2[NAME_LENGTH],
         worst1[NAME_LENGTH], worst2[NAME_LENGTH];
    int relation, worst_value = 0;
   
    // find the group of maximum negative value
    while ( g-- )
    {
      r = scanf ( "%s %s %d", girl1, girl2, &relation );
     
      if ( relation < worst_value )
      {
        worst_value = relation;
        strncpy(worst1, girl1, sizeof ( worst1 ) );
        strncpy(worst2, girl2, sizeof ( worst2 ) );
      }
    }
   
    if ( worst_value == 0 )
      printf ( "Are you kidding me?\n" );
    else
      printf ( "%s %s\n", worst1, worst2 );
  }
 
  return ( 0 );
}

12
本題同ZJ的b075。

題目目的︰給您一個火車到站時間的區間,包括區間起點和區間終點,和每位學生需要多久時間才能到達車站。求出每位學生最早要幾點出發,最晚要幾點出發。

解題技巧︰時間的相減。如果被減數的分鐘數比較小,就向小時借位。

代碼: [選擇]
// C++, ZJ b075, NPSC 2007 junior first

#include <cstdio>

struct Time
{
  int sh;  // start hour
  int sm;  // start minute
  int eh;  // end hour
  int em;  // end minute
};

int main ()
{
  int k, r;
 
  r = scanf ( "%d", &k );
 
  while ( k-- )
  {
    Time station;
    int q;
   
    r = scanf ( "%d %2d:%2d %2d:%2d", &q,
                &station.sh, &station.sm, &station.eh, &station.em );
               
    char dummy[1000];
    Time student;
   
    while ( q-- )
    {
      r = scanf ( "%s %2d:%2d", dummy, &student.sh, &student.sm );
     
      Time temp = station;
     
      if ( temp.sm < student.sm )
      {
        --temp.sh;
        temp.sm += 60;
      }
     
      if ( temp.em < student.sm )
      {
        --temp.eh;
        temp.em += 60;
      }
     
      printf ( "%.2d:%.2d %.2d:%.2d\n",
               temp.sh - student.sh, temp.sm - student.sm,
               temp.eh - student.sh, temp.em - student.sm);
    }
  }
 
  return ( 0 );
}

13
本題同ZeroJudge高中部網站的b101。

只要用一個vector統計所有磁鐵的個數,取最小者即可。可以利用讀入字元的方式加快速度。只是要小心測資數字之間的空白可能不止一個。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  while (cin >> N && N)
  {
    cin.get();  // catch newline character
    vector<unsigned int> count(42, 0);
    while (N--)
    {
      int M = 0;
      char c;
      while ((c = cin.get()) >= '0' && c <= '9')
        M = M * 10 + (c - '0');
      while (M--)
      {
        while (!((c = cin.get()) >= '0' && c <= '9'))
          ;
        unsigned int val = c - '0';
        while ((c = cin.get()) >= '0' && c <= '9')
          val = val * 10 + (c - '0');
        ++count[val];
      }
      while (c != '\n' && (c = cin.get()) != '\n')
        ;
    }
    unsigned int min = 1e9;  // just a very big value
    for (unsigned int i = 1; i <= 41; ++i)
      if (min > count[i])
        min = count[i];
    cout << min << "\n";
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


14
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 B. 節約尺
« 於: 三月 08, 2010, 09:48:43 am »
本題同ZeroJudeg高中部網站的b102。

因為是要求1到總和K的所有數,所以可以從總和來做文章。
1.用一個陣列紀錄累計的總和。如果有i,j,k三段而要求j到k段長度,就把sum[ k ] - sum[ i ]即可。
2. n == 總和K時,輸出NO。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  unsigned int n;
  while (cin >> n && n)
  {
    vector<unsigned int> num(n);
    unsigned int K = 0;
    for (unsigned int i = 0; i != n; ++i)
    {
      cin >> num[i];
      K += num[i];
    }
    if (n == K)
      cout << "NO\n";
    else
    {
      vector<unsigned int> sum(n);
      vector<unsigned int> mark(K + 1, false);
      for (unsigned int i = 0; i != n; ++i)
      {
        if (i)
          sum[i] = num[i] + sum[i - 1];
        else
          sum[i] = num[i];
        mark[sum[i]] = true;
        for (unsigned int j = 0; j != i; ++j)
          mark[sum[i] - sum[j]] = true;
      }
      unsigned int i;
      for (i = 1; i <= K; ++i)
        if (!mark[i])
          break;
      if (i > K)
        cout << "YES\n";
      else
        cout << "NO\n";
    }
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}



15
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 C. 怪物辨識
« 於: 三月 08, 2010, 02:48:48 am »
本題同ZeroJudge高中部網站的b103。

沒有特別的技巧。照著題目的意思寫if判斷式,加上善用vector紀錄正確的點數和錯誤的點數,剩下的大概就只是輸出入的加速而已。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  int m, n, y, x;
  while (cin >> m >> n >> x >> y)  // y is height, x is width
  {
    cin.get();  // catch newline character
    vector< vector<string> > monster(m);
    vector<string> pic(y);
    for (int i = 0; i != m; ++i)
      monster[i] = pic;
    for (int i = 0; i != m; ++i)
      for (int j = 0; j != y; ++j)
        getline(cin, monster[i][j], '\n');
    for (int i = 0; i != n; ++i)
    {
      vector<unsigned int> wrong_points(m, 0);
      vector<unsigned int> right_points(m, 0);
      for (int j = 0; j != y; ++j)
      {
        for (int k = 0; k != x; ++k)
        {
          char c = cin.get();
          for (int p = 0; p != m; ++p)
            if (monster[p][j][k] != '-')
            {
              if (monster[p][j][k] != c)
                ++wrong_points[p];
              else
                ++right_points[p];
            }
        }
        cin.get();  // catch newline character
      }
      int p;
      for (p = 0; p != m; ++p)
        if (right_points[p] >= (wrong_points[p] << 2))
        {
          cout.put('Y');
          break;
        }
      if (p == m)
        cout.put('N');
      cout.put('\n');
    }
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


16
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 D. 似曾相識
« 於: 三月 08, 2010, 01:25:40 am »
本題同ZeroJudge高中部網站的b104。

題目規定測資的兩個句子是等長的。所以如果兩個句子不同,一定會有一個句子某字元較多及另一個字元較少。所以在統計第一個句子的所有字元數之後,跑第二個句子時,將其字元減去統計好的數字。如果減到小於0,表示字元數不同,就可直接跳出迴圈了。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  int cases;
  cin >> cases;
  cin.get(); // catch newline character
  while (cases--)
  {
    vector<int> ascii(128, 0);
    string s;
    getline(cin, s, '\n');
    string::iterator iter = s.begin();
    for (; iter != s.end(); ++iter)
      ++ascii[*iter];
    getline(cin, s, '\n');
    iter = s.begin();
    for (; iter != s.end(); ++iter)
    {
      --ascii[*iter];
      if (ascii[*iter] < 0)
      {
        cout << "impossible\n";
        break;
      }
    }
    if (iter == s.end())
      cout << "possible\n";
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


17
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 E. 誰先晚餐
« 於: 三月 08, 2010, 01:05:48 am »
本題同ZeroJudge高中部網站的b105。

1.廚具只有一組,一次只煮一道菜。所以不管誰先煮誰後煮,總total時間一定會大於等於所有菜的煮的時間Ci總和。
2.既然煮的順序不能做判斷,只好對吃的時間來研究。是Ei小的先還是Ei大的先呢?答案是Ei值比較大(吃的比較久的)的先煮。因為先煮之後,別人煮的時間和吃的時間正好可以消耗吃的比較久的這個人的時間。
3.結論,先對Ei做排序,Ci的順序要跟著排序來變。然後設定兩個變數,cook_time和total_time來代表累計煮的時間和所有需要花費的時間。到了某i人時,如果累計煮的時間cook_time加上Ci和Ei會大於總total_time,表示在他之前的人都已經吃完在等他了,所以total_time就要更新。nlgn的排序加上跑一次迴圈n就可以算出答案。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

inline void swap(unsigned int &x1, unsigned int &y1,
                 unsigned int &x2, unsigned int &y2)
{
  unsigned int temp = x1;
  x1 = y1;
  y1=  temp;
  temp = x2;
  x2 = y2;
  y2 = temp;
}

void quicksort(vector<unsigned int> &C, vector<unsigned int> &E,
               int left, int right)
{
  if (left < right)
  {
    int i = right + 1, j = left;
    while (true)
    {
      while (i > j && E[--i] > E[left])
        ;
      while (i > j && E[++j] < E[left])
        ;
      swap(C[i], C[j], E[i], E[j]);
      if (i == j)
        break;
    }
    swap(C[left], C[j], E[left], E[j]);
    quicksort(C, E, left, j - 1);
    quicksort(C, E, j + 1, right);
  }
}

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  while (cin >> N && N)
  {
    vector<unsigned int> C(N);
    vector<unsigned int> E(N);
    for (int i = 0; i != N; ++i)
      cin >> C[i] >> E[i];
    quicksort(C, E, 0, N - 1);
    unsigned int total_time = 0, cook_time = 0;
    for (int i = N - 1; i >= 0; --i)
    {
      if (C[i] + E[i] + cook_time > total_time)
        total_time = C[i] + E[i] + cook_time;
      cook_time += C[i];
    }
    cout << total_time << "\n";
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


18
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 F. P方陣
« 於: 三月 08, 2010, 12:52:52 am »
本題同ZeroJudge高中部網站的b106。

這題應該要有特殊的解法。不過我沒有想到。
暴力加條件判斷硬解的速度大概在1秒左右,使用讀字元的方式讀入數字可以將時間縮減一半。
因為P方陣的每一行數字不能重複,所以簡單地設置bool vector來紀錄已經出現過的數字。只要不符合規定,整個P方陣就可以不用再多算了。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

inline bool P_matrix(const vector< vector<unsigned char> > &M,
                     const unsigned int &y, const unsigned int &x,
                     const unsigned int &size)
{
  unsigned int y2 = y + size, x2 = x + size;
  for (unsigned int i = y; i != y2; ++i)
  {
    vector<bool> A(size + 1, false);
    for (unsigned int j = x; j != x2; ++j)
    {
      if (M[i][j] > size || A[M[i][j]])
        return(false);
      A[M[i][j]] = true;
    }
  }
  for (unsigned int i = x; i != x2; ++i)
  {
    vector<bool> A(size + 1, false);
    for (unsigned int j = y; j != y2; ++j)
    {
      if (M[i][j] > size || A[M[i][j]])
        return(false);
      A[M[i][j]] = true;
    }
  }
  return(true);
}

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  unsigned int T, cases;
  cin >> T;
  for (cases = 0; cases != T; )
  {
    cout << "Page #" << ++cases << ":\n";
    unsigned int A, B;
    cin >> A >> B;
    cin.get();  // catch newline character
    unsigned int max = (A < B) ? A : B;
    vector<unsigned char> count(101, 0);
    vector< vector<unsigned char> > M(A);
    for (unsigned int i = 0; i != A; ++i)
      for (unsigned int j = 0; j != B; ++j)
      {
        unsigned char value = 0;
        char c;
        while ((c = cin.get()) != ' ' && c != '\n')
          value = value * 10 + (c - '0');
        ++count[value];
        M[i].push_back(value);
      }
    if (A == 1 || B == 1)
    {
      cout << "No P-square exists.\n";
      continue;
    }
    bool possible = false;
    for (unsigned int k = 2; k <= max; ++k)
    {
      if (count[k] >= k)
      {
        unsigned int num = 0;
        for (unsigned int i = 0; i != A; ++i)
        {
          if (i + k <= A)
          {
            for (unsigned int j = 0; j != B; ++j)
            {
              if (j + k <= B)
              {
                if (P_matrix(M, i, j, k))
                  ++num;
              }
              else
                break;
            }
          }
          else
            break;
        }
        if (num)
        {
          cout << k << "x" << k << " P-square: appear " << num << " time(s).\n";
          possible = true;
        }
      }
    }
    if (!possible)
      cout << "No P-square exists.\n";
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


19
NPSC2005國中組決賽 / [C++] 2005 NPSC 國中組決賽 G. 裝備整理
« 於: 三月 02, 2010, 10:23:47 pm »
本題同ZeroJudge高中部網站的b107。

必須認清題目需求。
1.一開始分成五大類。
2.五大類裡面,手上的刀劍斧,弓弩,棍棒杖,盾沒有顏色,故不用排,但要排等級。包含手套等其他的裝備,沒有等級,但要排顏色。
3.每一個裝備都要排名字。
4.名字順序是短 < 長。同樣長度則 A < a <B < b <C < c ...... < Z < z。和C++字串的lib的compare()不一樣。
5.實作快速排序是比較方便做if分支不同情況的。

代碼: [選擇]
#include <iostream>
#include <vector>
using namespace std;

const unsigned int eSIZE = 5;  // equipment size

struct equip
{
  vector< vector<string> > equip_n;
  vector< vector<unsigned int> > equip_v;
};

inline char compare_str(const string &sa, const string &sb)
{
  if (sa.length() > sb.length())
    return(1);
  else if (sa.length() < sb.length())
    return(-1);
  for (unsigned int i = 0; i != sa.length(); ++i)
  {
    if ((sa[i] & 31) > (sb[i] & 31))
      return(1);
    else if ((sa[i] & 31) < (sb[i] & 31))
      return(-1);
    else
    {
      if (sa[i] > sb[i])
        return(1);
      else if (sa[i] < sb[i])
        return(-1);
    }
  }   
  return(0);
}

void quicksort(equip &A, int left, int right, const unsigned int &value)
{
  if (left < right)
  {
    int i = right + 1, j = left;
    if (value != 3)
    {
      while (true)
      {
        while (i > j && A.equip_v[--i][value] > A.equip_v[left][value])
          ;
        while (i > j && A.equip_v[++j][value] < A.equip_v[left][value])
          ;
        A.equip_v[i].swap(A.equip_v[j]);
        A.equip_n[i].swap(A.equip_n[j]);
        if (i == j)
          break;
      }
      A.equip_v[left].swap(A.equip_v[j]);
      A.equip_n[left].swap(A.equip_n[j]);
      quicksort(A, j + 1, right, value);
      quicksort(A, left, j - 1, value);
    }
    else
    {
      while (true)
      {
        while (i > j && compare_str(A.equip_n[--i][0], A.equip_n[left][0]) > 0)
          ;
        while (i > j && compare_str(A.equip_n[++j][0], A.equip_n[left][0]) < 0)
          ;
        A.equip_v[i].swap(A.equip_v[j]);
        A.equip_n[i].swap(A.equip_n[j]);
        if (i == j)
          break;
      }
      A.equip_v[left].swap(A.equip_v[j]);
      A.equip_n[left].swap(A.equip_n[j]);
      quicksort(A, j + 1, right, value);
      quicksort(A, left, j - 1, value);
    }
  }
}

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  const unsigned int tSIZE = 12;
  const string type[tSIZE] = {"hat", "earring", "sword", "bow",
                              "bastinado", "targe", "glove", "clothes",
                              "cape", "pant", "skirt", "shoe"};
  const unsigned int type_value[tSIZE] = {0, 1, 10, 11,
                                          12, 13, 14, 20,
                                          21, 30, 31, 40};
  const unsigned int cSIZE = 8;
  const string color[cSIZE] = {"W", "P", "B", "R",
                               "Y", "G", "K", "U"};
  const unsigned int color_value[cSIZE] = {0, 1, 2, 3,
                                           4, 5, 6, 7};
  int cases;
  cin >> cases;
  while (cases--)
  {
    unsigned int item;
    cin >> item;
    cin.get();
    if (!item)
      cout << "--------\n";
    else
    {
      vector<equip> equip_vec(eSIZE);
      for (unsigned i = 0; i != eSIZE; ++i)
        equip_vec[i].equip_n.clear(), equip_vec[i].equip_v.clear();
      for (unsigned int i = 0; i != item; ++i)
      {
        vector<string> name(2);  // 0 is name, 1 is AA
        cin >> name[0];  // name
        string s;
        s.clear();
        for (unsigned int j = 0, k = 0; k != 2 && j != name[0].length(); ++j)
          if (name[0][j] <= 'Z')
          {
            s.append(1, name[0][j]);
            ++k;
          }
        name[1] = s;
        vector<unsigned int> value(3);  // 0 is type, 1 is color, 2 is level
        unsigned int index = 0;
        cin >> s;  // type
        for (unsigned int j = 0; j != tSIZE; ++j)
          if (!s.compare(type[j]))
          {
            value[0] = type_value[j] % 10;
            index = type_value[j] / 10;
            break;
          }
        cin >> s;  // color
        for (unsigned int j = 0; j != cSIZE; ++j)
          if (!s.compare(color[j]))
          {
            value[1] = color_value[j];
            break;
          }
        cin >> value[2]; // level
        cin.get();
        equip_vec[index].equip_n.push_back(name);
        equip_vec[index].equip_v.push_back(value);
      }
      for (unsigned int i = 0; i != eSIZE; ++i)
      {
        int size = equip_vec[i].equip_n.size();
        if (i != 4)
          quicksort(equip_vec[i], 0, size - 1, 0);
        int l1, l2, r1, r2;
        for (l1 = 0, r1 = 0; r1 != size; ++r1)
          if (equip_vec[i].equip_v[l1][0] != equip_vec[i].equip_v[r1][0])
          {
            if (!(i == 1 && equip_vec[i].equip_v[l1][0] != 4))
            {
              quicksort(equip_vec[i], l1, r1 - 1, 1);
              for (l2 = l1, r2 = l1; r2 != r1; ++r2)
              {
                if (equip_vec[i].equip_v[l2][1] != equip_vec[i].equip_v[r2][1])
                {
                  quicksort(equip_vec[i], l2, r2 - 1, 3);
                  l2 = r2;
                }
              }
              if (r2 - l2 > 1)
                quicksort(equip_vec[i], l2, r2 - 1, 3);
              l2 = r2;
            }
            else  // "sword", "bow", "bastinado", "targe"
            {
              quicksort(equip_vec[i], l1, r1 - 1, 2);
              for (l2 = l1, r2 = l1; r2 != r1; ++r2)
              {
                if (equip_vec[i].equip_v[l2][2] != equip_vec[i].equip_v[r2][2])
                {
                  quicksort(equip_vec[i], l2, r2 - 1, 3);
                  l2 = r2;
                }
              }
              if (r2 - l2 > 1)
                quicksort(equip_vec[i], l2, r2 - 1, 3);
              l2 = r2;
            }
            l1 = r1;
          }
        if (r1 - l1 > 1)
        {
          if (!(i == 1 && equip_vec[i].equip_v[l1][0] != 4))
          {
            quicksort(equip_vec[i], l1, r1 - 1, 1);
            for (l2 = l1, r2 = l1; r2 != r1; ++r2)
            {
              if (equip_vec[i].equip_v[l2][1] != equip_vec[i].equip_v[r2][1])
              {
                quicksort(equip_vec[i], l2, r2 - 1, 3);
                l2 = r2;
              }
            }
            if (r2 - l2 > 1)
              quicksort(equip_vec[i], l2, r2 - 1, 3);
            l2 = r2;
          }
          else  // "sword", "bow", "bastinado", "targe"
          {
            quicksort(equip_vec[i], l1, r1 - 1, 2);
            for (l2 = l1, r2 = l1; r2 != r1; ++r2)
            {
              if (equip_vec[i].equip_v[l2][2] != equip_vec[i].equip_v[r2][2])
              {
                quicksort(equip_vec[i], l2, r2 - 1, 3);
                l2 = r2;
              }
            }
            if (r2 - l2 > 1)
              quicksort(equip_vec[i], l2, r2 - 1, 3);
            l2 = r2;
          }
          l1 = r1;
        }
      }
      for (unsigned int i = 0; i != eSIZE; ++i)
      {
        unsigned int size = equip_vec[i].equip_n.size();
        for (unsigned int j = 0; j != size; ++j)
        {
          cout << equip_vec[i].equip_n[j][1];
          if (((j + 1) & 3) == 0)
            cout.put('\n');
        }
        unsigned int spaces = size & 3;
        if (spaces)
        {
          for (unsigned int j = 0; j != 4 - spaces; ++j)
          {
            cout.put('_');
            cout.put('_');
          }
          cout.put('\n');
        }
      }
      cout << "--------\n";
    }
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}



20
NPSC2005國中組初賽 / [C++] 2005 NPSC 國中組初賽 F. 奇幻之樹
« 於: 三月 02, 2010, 03:44:31 pm »
本題同ZeroJudeg高中部網站的b100。

假設 分子 / 分母 為 L / R,來研究 4 / 9。
1. 9 > 4 => R > L => R, 4 / 9 => 4 / (9 - 4) => 4 / 5。
2. 5 > 4 => R > L => R, 4 / 5 => 4 / (5 - 4) => 4 / 1。
3. 4 > 1 => L > R => L, 4 / 1 => (4 - 1) / 1 => 3 / 1。
4. 3 > 1 => L > R => L, 3 / 1 => (3 - 1) / 1 => 2 / 1。
5. 2 > 1 => L > R => L, 2 / 1 => (2 - 1) / 1 => 1 / 1。
end.

我們求得RRLLL,和題目給的LLRRR剛好相反。所以只要L > R,輸出R;R > L,輸出L,就可以了。

代碼: [選擇]
#include <iostream>
using namespace std;

int main(void)
{
  cout << flush;
  ostream *old_tie = cin.tie();
  cin.tie(0);
  ios::sync_with_stdio(false);
  unsigned int m, n;
  while (cin >> m >> n && (m + n))
  {
    while (!(m == 1 && n == 1))
    {
      if (m > n)
      {
        m-=n;
        cout.put('R');
      }
      else
      {
        n-=m;
        cout.put('L');
      }
    }
    cout.put('\n');
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


頁: [1] 2