NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

文章 - bleed1979

頁: [1] 2
1
DP的方式和前面兩三位的解法大同小異,差別在最內圈DP關鍵點要加上前一次狀態的考量。
我採取的是所有可能都考量的方式,速度上會比較慢一些些,試著解釋清楚一些。

首先是group的分割和規劃。

彎道數會比直線賽道少1,意思是,5個直線賽道只有4個彎道。
所以在5個直線賽道的例子裡,切割如下:

group1: 直線1
group2: 彎道1 + 直線2
group3: 彎道2 + 直線3
group4: 彎道3 + 直線4
group5: 彎道4 + 直線5

也就是group1只有直線,之後的group都是先彎道再直線。
這種配置方式對於DP的迴圈疊代會比較好寫。

第二,配置DP[ i ][j]的陣列。

一樣地,i代表第幾個group,j代表第幾個group跑完,甩尾數還剩幾個。
而DP[ i ][j]就是所花費的最少時間。

所以DP[ i ][j]的通式就是:

代碼: [選擇]
DP[i][j] = DP[i][j]的前一個狀態 + 直線是否開加速器 + 是否甩尾。

關鍵就在如何取DP[ i ][j]的前一個狀態。

第三,討論所有可能。

因為我已經寫完這題,所以直接告訴大家,所有可能分為兩類。

第一類:甩尾數剩下0的情況。
第二類:甩尾數是其他數量的情況。

什麼時候甩尾數剩下0呢?

case1: 在本次的group不開加速器,不甩尾,則通式就是:

代碼: [選擇]
DP[i][j] = DP[i - 1][j] + 直線長度 * 2 + 不甩尾的5;

case2: 在本次的group開加速器,不甩尾。

因為可以開加速器,代表至少是到group4(累積前三次甩尾)。

而因為開加速器甩尾數扣3,所以前一次狀態是甩尾數加3的情況,要小心陣列索引值。

通式是:

代碼: [選擇]
if(i >= 4 && j + 3 < 7) {
  DP[i][j] = DP[i - 1][j + 3] + 直線長度 + 不甩尾的5;
}

case3: 在本次group開加速器,又甩尾。

要注意除了group1以外的group2, group3...都是彎道在前,

前一個狀態只要有2個以上甩尾,再配合這次的甩尾湊成3個以上的甩尾就足夠換加速器。

所以,前一個狀態是甩尾數加2的情況,一樣小心陣列索引值。

代碼: [選擇]
if(i >= 4 && j + 3 < 7) {
  DP[i][j] = DP[i - 1][j + 2] + 直線長度 + 甩尾的10;
}

以上是第一類的情況。

第一類和第二類的差別在於第一類是不能在甩尾後還有多餘的甩尾數(因為是0嘛)。

但是第二類除了第一類的3個case以外,還多了case4的不開加速器,但甩尾的情況。

通式就是:

代碼: [選擇]
DP[i][j] = DP[i - 1][j - 1] + 直線長度 * 2 + 甩尾的10;


如此就完成了所有可能都考量的情況。

在下面的程式碼的註解,使用D代表加速器,has D代表開加速器,no D代表不開加速器。使用T則代表甩尾。

這個程式碼應該是可以通過高中生解題系統的測資,但真實比賽是否過關就不得而知了,僅供參考。

代碼: [選擇]
//  Senior NPSC 2010 First pB

#include <cstdio>

long long DP[10002][7];
int LINE[10002];

int main() {
    const long long MAX = 1000000000000000LL;
    int m, n;
    scanf("%d", &m);
    while(m--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &LINE[i]);
        }

        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j < 7; ++j) {
                DP[i][j] = MAX;
            }
        }

        DP[1][0] = LINE[1] * 2;
        for(int i = 2; i <= n; ++i) {
            for(int j = 0; j < 7; ++j) {
                if(!j) {
                    // no D, no T
                    if(DP[i][j] > DP[i - 1][j] + LINE[i] * 2 + 5LL) {
                        DP[i][j] = DP[i - 1][j] + LINE[i] * 2 + 5LL;
                    }

                    if(i >= 4 && j + 3 < 7) {
                        // has D, has T
                        if(DP[i][j] > DP[i - 1][j + 2] + LINE[i] + 10LL) {
                            DP[i][j] = DP[i - 1][j + 2] + LINE[i] + 10LL;
                        }

                        // has D, no T
                        if(DP[i][j] > DP[i - 1][j + 3] + LINE[i] + 5LL) {
                            DP[i][j] = DP[i - 1][j + 3] + LINE[i] + 5LL;
                        }
                    }
                } else {
                    // no D, has T
                    if(DP[i][j] > DP[i - 1][j - 1] + LINE[i] * 2 + 10LL) {
                        DP[i][j] = DP[i - 1][j - 1] + LINE[i] * 2 + 10LL;
                    }

                    // no D, no T
                    if(DP[i][j] > DP[i - 1][j] + LINE[i] * 2 + 5LL) {
                        DP[i][j] = DP[i - 1][j] + LINE[i] * 2 + 5LL;
                    }

                    if(i >= 4 && j + 3 < 7) {
                        // has D, has T
                        if(DP[i][j] > DP[i - 1][j + 2] + LINE[i] + 10LL) {
                            DP[i][j] = DP[i - 1][j + 2] + LINE[i] + 10LL;
                        }

                        // has D, no T
                        if(DP[i][j] > DP[i - 1][j + 3] + LINE[i] + 5LL) {
                            DP[i][j] = DP[i - 1][j + 3] + LINE[i] + 5LL;
                        }
                    }
                }
            }
        }

        long long cost = MAX;
        for(int j = 0; j < 7; ++j) {
            if(cost > DP[n][j]) {
                cost = DP[n][j];
            }
        }
        printf("%lld\n", cost);
    }
    return 0;
}


2
本題同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 );
}

3
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 );
}

4
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 );
}

5
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 );
}

6
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 );
}

7
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 );
}

8
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 );
}

9
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 );
}

10
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 );
}

11
本題同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 );
}

12
本題同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 );
}

13
本題同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 );
}

14
本題同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);
}


15
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);
}



16
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);
}


17
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);
}


18
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);
}


19
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);
}


20
依照題意,上述程式速度很快但有bug。

考慮以下測資︰
代碼: [選擇]
3
a 00:00:01
b 00:00:01.000
c 00:00:01.

上述程式輸出為︰
代碼: [選擇]
LIST START
a
LIST END

實際上應該是要輸出︰
代碼: [選擇]
LIST START
a
b
c
LIST END

正統作法還是對double排序,但速度大概慢了10倍。以下提供double的解法。

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

void quicksort(vector<double> &A, vector<unsigned int> &B, int left, int right)
{
  if (left < right)
  {
    int i = right + 1, j = left;
    while (true)
    {
      while (i > j)
      {
        double dval = A[--i];
        if (!(dval > A[left] || A[left] - dval < 1e-9))
          break;
      }
      while (i > j)
      {
        double dval = A[++j];
        if (!(dval < A[left] || dval - A[left] < 1e-9))
          break;
      }
      double temp_d = A[i];
      A[i] = A[j];
      A[j] = temp_d;
      unsigned int temp_ui = B[i];
      B[i] = B[j];
      B[j] = temp_ui;
      if (i ==j)
        break;     
    }
    double temp_d = A[left];
    A[left] = A[j];
    A[j] = temp_d;
    unsigned int temp_ui = B[left];
    B[left] = B[j];
    B[j] = temp_ui;
    quicksort(A, B, left, j - 1);
    quicksort(A, B, j + 1, right);
  }
}

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)
  {
    cin.get();  // catch newline character
    cout << "LIST START\n";
    vector<string> name(N);
    vector<unsigned int> index(N);
    for (unsigned int i = 0; i != N; ++i)
      index[i] = i;
    vector<double> second(N);
    for (unsigned int i = 0; i != N; ++i)
    {
      cin >> name[i];
      string s;
      cin >> s;
      istringstream stream(s);
      char c;
      double hh, mm, ss;
      stream >> hh >> c >> mm >> c >> ss;
      second[i] = ss + mm * 60.0 + hh * 3600.0;
    }
    quicksort(second, index, 0, N - 1);
    unsigned int q = N / 3;
    while (q != N && second[q] - second[q - 1] < 1e-9)
      ++q;
    unsigned int l1, r1;
    for (l1 = 0, r1 = 0; r1 != q; ++r1)
    {
      if (!(second[l1] < second[r1] || second[r1] - second[l1] < 1e-9))
      {
        if (r1 - l1 > 1)
          sort(index.begin() + l1, index.begin() + r1);
        l1 = r1;
      }
    }
    if (r1 - l1 > 1)
      sort(index.begin() + l1, index.begin() + r1);
    for (unsigned int i = 0; i != q; ++i)
      cout << name[index[i]] << "\n";
    cout << "LIST END\n";
  }
  ios::sync_with_stdio(true);
  cin.tie(old_tie);
  cout << flush;
  return(0);
}


頁: [1] 2