Trang 68 trên tổng số 69 Đầu tiênĐầu tiên ... 185866676869 Cuối cùngCuối cùng
Từ 671 tới 680 trên tổng số 688 kết quả

Đề tài: Võ đường quán: Tuyển tập đề thi các kì thi Olympic tin học

  1. #671
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Võ đường quán: Tuyển tập đề thi các kì thi Olympic tin học

    @prog10: Loại được prime thì nhanh hơn chứ nhỉ? Với lại sieve chỉ một lần, nếu input toàn primes, thì cách kia có vẻ không ổn cho lắm.

    @fithou91192:
    Bài VBOARD của bạn đây (100% test), muốn nhanh thì chuyển về dùng scanf(), printf() hoặc viết lại fast i/o.
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    4. #include <cstdio>
    5. #include <algorithm>
    6. #include <climits>
    7. #include <utility>
    8. #include <fstream>
    9. #include <map>
    10. #include <cmath>
    11. #include <exception>
    12. #include <stdexcept>
    13. #include <sstream>
    14. #include <cassert>
    15. #include <memory>
    16. #include <limits>
    17. #include <deque>
    18. #include <queue>
    19. #include <limits>
    20. #include <climits>
    21. #include <string>
    22. #include <iomanip>
    23.  
    24. const int MAX_N = 2001;
    25.  
    26. enum square_color {
    27.     WHITE = 0,
    28.     BLACK = 1
    29. };
    30.  
    31. /**
    32.  * DP table:
    33.  *      0 for WHITE board
    34.  *      1 for BLACK board
    35.  */
    36. int dp[MAX_N][MAX_N][2];
    37.  
    38. void print_board(int size, const square_color &color) {
    39.     std::cout << ((color == WHITE) ? "WHITE board: \n" : "BLACK board: \n");
    40.     for (int x = 0; x < size; ++x) {
    41.         for (int y = 0; y < size; ++y) {
    42.             std::cout << std::setw(4) << dp[x][y][color];
    43.         }
    44.         std::cout << "\n";
    45.     }
    46.     std::cout << std::endl;
    47. }
    48.  
    49. /**
    50.  * Get color of a particular square
    51.  * where square (0, 0) is WHITE, the rest
    52.  * alternates between BLACK & WHITE
    53.  *
    54.  * @param x
    55.  *      row of board (0, size - 1)
    56.  *
    57.  * @param y
    58.  *      column of board (0, size - 1)
    59.  */
    60. square_color color_of(int x, int y) {
    61.     if (x % 2 == 0) {
    62.         return (y % 2 == 0) ? WHITE : BLACK;
    63.     } else {
    64.         return (y % 2 == 1) ? WHITE : BLACK;
    65.     }
    66. }
    67.  
    68. /**
    69.  * Flip color B -> W or W -> B
    70.  *
    71.  * @param c
    72.  *      color of a square (x, y)
    73.  */
    74. square_color flip(const square_color &c) {
    75.     return (c == WHITE) ? BLACK : WHITE;
    76. }
    77.  
    78. void print_board_color(int size) {
    79.     for (int x = 0; x < size; ++x) {
    80.         for (int y = 0; y < size; ++y) {
    81.             std::cout << std::setw(4)
    82.                     << ((color_of(x, y) == WHITE) ? 'W' : 'B');
    83.         }
    84.         std::cout << "\n";
    85.     }
    86.     std::cout << "\n\n\n";
    87. }
    88.  
    89. /**
    90.  * Compute prefix sum for all rectangles
    91.  * of size:
    92.  *      (0, 0) -> (top, left)
    93.  *      (x, y) -> (bottom, right)
    94.  *
    95.  * @param in
    96.  *      standard C++ input (either std::cin or std::ifstream)
    97.  */
    98. int read_compute_accumulative_sum(std::istream &in) {
    99.     int size;
    100.     int square;
    101.     in >> size;
    102.     square_color color;
    103.     for (int x = 0; x < size; ++x) {
    104.         for (int y = 0; y < size; ++y) {
    105.             // get value
    106.             in >> square;
    107.             // get color
    108.             color = color_of(x, y);
    109.             // if a square is W, its black value is 0
    110.             // and other way around
    111.             dp[x][y][color] = square;
    112.             dp[x][y][flip(color)] = 0;
    113.             for (int c = 0; c <= 1; ++c) {
    114.                 // add from top
    115.                 if (x > 0) {
    116.                     dp[x][y][c] += dp[x - 1][y][c];
    117.                 }
    118.                 // add from left
    119.                 if (y > 0) {
    120.                     dp[x][y][c] += dp[x][y - 1][c];
    121.                 }
    122.                 // avoid double count
    123.                 if (x > 0 && y > 0) {
    124.                     dp[x][y][c] -= dp[x - 1][y - 1][c];
    125.                 }
    126.             }
    127.         }
    128.     }
    129.     return size;
    130. }
    131.  
    132. /**
    133.  * Compute the absolution value of
    134.  * WHITE rectangle sum & BLACK rectangle sum
    135.  *
    136.  * Formula:
    137.  *
    138.  *  (0, 0)
    139.  *  ---------------------------|
    140.  *  | x |    A       |         |
    141.  *  |-----------------         |
    142.  *  |   | (t, l)     |         |
    143.  *  | B |            |         |
    144.  *  |---|-------------(b, r)   |
    145.  *  |                          |
    146.  *  |---------------------------
    147.  *
    148.  *  x is the area we subtract twice (double count)
    149.  *
    150.  *  Let S = area of rectangle (0, 0) and (b, r)
    151.  *      M = area that we need to find (t, l) and (b, r)
    152.  *
    153.  *  Then
    154.  *      M = S - A - B + x
    155.  *
    156.  *  @param top
    157.  *          coordinate of a rectangle - 0 index
    158.  *
    159.  *  @param left
    160.  *          coordinate of a rectangle - 0 index
    161.  *
    162.  *  @param bottom
    163.  *          coordinate of a rectangle - 0 index
    164.  *
    165.  *  @param right
    166.  *          coordinate of a rectangle - 0 index
    167.  */
    168. int query(int top, int left, int bottom, int right) {
    169.     int white_largest_square = dp[bottom][right][WHITE];
    170.     int black_largest_square = dp[bottom][right][BLACK];
    171.     if (top > 0) {
    172.         white_largest_square -= dp[top - 1][right][WHITE];
    173.         black_largest_square -= dp[top - 1][right][BLACK];
    174.     }
    175.     if (left > 0) {
    176.         white_largest_square -= dp[bottom][left - 1][WHITE];
    177.         black_largest_square -= dp[bottom][left - 1][BLACK];
    178.     }
    179.     if (top > 0 && left > 0) {
    180.         white_largest_square += dp[top - 1][left - 1][WHITE];
    181.         black_largest_square += dp[top - 1][left - 1][BLACK];
    182.     }
    183.     if (white_largest_square > black_largest_square) {
    184.         return white_largest_square - black_largest_square;
    185.     } else {
    186.         return black_largest_square - white_largest_square;
    187.     }
    188. }
    189.  
    190. void inout_board(std::istream &in, std::ostream &out) {
    191.     read_compute_accumulative_sum(in);
    192.     int q;
    193.     int top;
    194.     int left;
    195.     int bottom;
    196.     int right;
    197.     in >> q;
    198.     while (q--) {
    199.         in >> top >> left >> bottom >> right;
    200.         top--, left--, bottom--, right--;
    201.         out << query(top, left, bottom, right) << "\n";
    202.     }
    203. }
    204.  
    205. void test_compute_accumulative_sum() {
    206.     std::ifstream in("data.txt");
    207.     int size = read_compute_accumulative_sum(in);
    208.     print_board_color(size);
    209.     print_board(size, WHITE);
    210.     print_board(size, BLACK);
    211. }
    212.  
    213. void test_board_color_logic() {
    214.     print_board_color(3);
    215.     print_board_color(4);
    216.     print_board_color(5);
    217. }
    218.  
    219. int main() {
    220.     inout_board(std::cin, std::cout);
    221.     // test_board_color_logic();
    222.     // test_compute_accumulative_sum();
    223.     return 0;
    224. }

  2. #672
    Ngày gia nhập
    07 2011
    Bài viết
    474

    viết gì dài kinh thế @.@

  3. #673
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    viết gì dài kinh thế @.@
    Bác r_r include bừa vào ý mà. Chắc lười xoá. Chỉ cần nhiêu đây là đủ rồi:
    C++ Code:
    1. #include <iostream>
    2. #include <fstream>
    3. #include <iomanip>
    Chưa kể là bác ấy include 1 tệp hai lần =.="

    @r_r: Em nghĩ là không nên viết code kiểu này. Loại bỏ else thì tốt hơn, vì một số trình biên dịch cảnh báo là "This function could return default value implicitly." Hoặc "function f does not always return a value". Mấy cái compiler loại ngu ngốc ý. =.="

    C++ Code:
    1. square_color color_of(int x, int y) {
    2.     if (x % 2 == 0) {
    3.         return (y % 2 == 0) ? WHITE : BLACK;
    4.     } else {
    5.         return (y % 2 == 1) ? WHITE : BLACK;
    6.     }
    7. }
    Đã được chỉnh sửa lần cuối bởi doicanhden : 20-08-2013 lúc 04:44 AM. Lý do: <-- Canh 4:44 AM nào. :3 Cái trò tự kỉ ngu ngốc. =.="...
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  4. #674
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @doicanhden: Thanks em. Tại đang xài C++11 mà trang spoj chỉ có GCC 4.3.2 (siêu cùi bắp), nên anh mới phải dùng cái kiểu enum pha integer return như thế :(
    Còn cái else thì đúng là bỏ cũng được, tại anh ghi ra explicitly để thấy rõ 2 trường hợp thôi. Good point!
    Phần headers thì đang dùng mấy cái của C++11, nên xóa ra xóa vô nó trùng.
    Thật ra đoạn đó viết kĩ chắc còn ngắn gọn nữa, đoạn logic đó hơi cùi, viết vội quá :(

    @INTP: Dài do mình thêm vào mấy cái test + comments đó thôi. Quan trọng vẫn là thuật toán mà, mình viết dài tí thì người đọc khỏi phải đoán già đoán non.

    Đoạn này mình optimize thêm tí xíu, 0.32s so với 3.xxs :(
    C++ Code:
    1. #include <cstring>
    2. #include <cstdio>
    3.  
    4. const int MAX_N = 2001;
    5.  
    6. void fast_read(int *num) {
    7.     *num = 0;
    8.     bool sign = false;
    9.     char p = getchar_unlocked();
    10.     for (; p < 33;) {
    11.         p = getchar_unlocked();
    12.     }
    13.     if (p == '-') {
    14.         sign = true;
    15.     }
    16.     for (; p > 32;) {
    17.         *num = (*num << 3) + (*num << 1) + (p - '0');
    18.         p = getchar_unlocked();
    19.     }
    20.     if (sign) {
    21.         *num *= -1;
    22.     }
    23. }
    24.  
    25. enum square_color {
    26.     WHITE = 0,
    27.     BLACK = 1
    28. };
    29.  
    30. int dp[MAX_N][MAX_N][2];
    31.  
    32. square_color color_of(int x, int y) {
    33.     return (x & 1) ^ (y & 1) ? BLACK : WHITE;
    34. }
    35.  
    36. square_color flip(const square_color &c) {
    37.     return (c == WHITE) ? BLACK : WHITE;
    38. }
    39.  
    40. int read_compute_accumulative_sum() {
    41.     int size;
    42.     int square;
    43.     // scanf("%d", &size);
    44.     fast_read(&size);
    45.     square_color color;
    46.     for (int x = 0; x < size; ++x) {
    47.         for (int y = 0; y < size; ++y) {
    48.             // scanf("%d", &square);
    49.             fast_read(&square);
    50.             color = color_of(x, y);
    51.             dp[x][y][color] = square;
    52.             dp[x][y][flip(color)] = 0;
    53.             for (int c = 0; c <= 1; ++c) {
    54.                 if (x > 0) {
    55.                     dp[x][y][c] += dp[x - 1][y][c];
    56.                 }
    57.                 if (y > 0) {
    58.                     dp[x][y][c] += dp[x][y - 1][c];
    59.                 }
    60.                 if (x > 0 && y > 0) {
    61.                     dp[x][y][c] -= dp[x - 1][y - 1][c];
    62.                 }
    63.             }
    64.         }
    65.     }
    66.     return size;
    67. }
    68.  
    69. int get_rectangle_sum(int top, int left, int bottom, int right, const square_color &c) {
    70.     int area = dp[bottom][right][c];
    71.     if (top > 0) {
    72.         area -= dp[top - 1][right][c];
    73.     }
    74.     if (left > 0) {
    75.         area -= dp[bottom][left - 1][c];
    76.     }
    77.     if (top > 0 && left > 0) {
    78.         area += dp[top - 1][left - 1][c];
    79.     }
    80.     return area;
    81. }
    82.  
    83. int query(int top, int left, int bottom, int right) {
    84.     int w = get_rectangle_sum(top, left, bottom, right, WHITE);
    85.     int b = get_rectangle_sum(top, left, bottom, right, BLACK);
    86.     return (w > b) ? w - b : b - w;
    87. }
    88.  
    89. void inout_board() {
    90.     read_compute_accumulative_sum();
    91.     int q;
    92.     int top;
    93.     int left;
    94.     int bottom;
    95.     int right;
    96.     fast_read(&q);
    97.     while (q--) {
    98.         fast_read(&top);
    99.         fast_read(&left);
    100.         fast_read(&bottom);
    101.         fast_read(&right);
    102.         top--, left--, bottom--, right--;
    103.         printf("%d\n", query(top, left, bottom, right));
    104.     }
    105. }
    106.  
    107. int main() {
    108.     inout_board();
    109.     return 0;
    110. }
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		Untitled.png
Lần xem:	3
Size:		3.4 KB
ID:		11794
    Đã được chỉnh sửa lần cuối bởi rox_rook : 20-08-2013 lúc 06:23 AM.

  5. #675
    Ngày gia nhập
    04 2013
    Nơi ở
    $HOME
    Bài viết
    48

    Mình nghĩ là bỏ luôn màu của ô đi, chỉ cần dùng nó khi đọc để chuyển dấu cộng trừ thích hợp. Đoạn mã của mình chạy mất khoảng 0.4s (chậm hơn một chút so với bài của bạn rox_rook), nhưng chỉ dùng có 2.6M so với 33M.

    C Code:
    1. /* VBOARD: Difference of values in a rectangular part of a chessboard.  */
    2.  
    3. #include <stdio.h>
    4.  
    5. #define MAXSIZE     501     /* +1 as the index starts from 1.  */
    6.  
    7. /* board[i][j] contains the sum of elements (with appropriate signs) in the
    8.  * rectangle (1,1)-(i,j).  Elements in row 0 and column 0 are automatically set
    9.  * to zero (as board is global), and are used to avoid boundary tests.  */
    10. int board[MAXSIZE][MAXSIZE];
    11.  
    12. /* Return the next integer from stdin.  */
    13. int
    14. next_int()
    15. {
    16.     int k = 0, c;
    17.     while (c = getchar(), c < '0' || c > '9');
    18.     do {
    19.         k = (10 * k) + (c - '0');
    20.         c = getchar();
    21.     } while ('0' <= c && c <= '9');
    22.  
    23.     return k;
    24. }
    25.  
    26. int
    27. main(void)
    28. {
    29.     /* Get the board size.  */
    30.     int n = next_int();
    31.  
    32.     /* Read numbers in the board, and update board as reading.  Again, element
    33.      * board[i][j] is the sum of numbers (with signs) in (1,1)-(i,j).  */
    34.  
    35.     int k;  // number to be read for the current square
    36.     int s;  // sum of numbers in a row up to the current square
    37.     for (int i = 1; i < (n + 1); ++i) {
    38.         s = 0;        
    39.         for (int j = 1; j < (n + 1); ++j) {
    40.             k = next_int();
    41.             s += ((i + j) & 1) ? -k : k;
    42.             board[i][j] = board[i-1][j] + s;
    43.         }
    44.     }
    45.  
    46.     /* Get and solve puzzles.  */
    47.     int q = next_int();
    48.  
    49.     int t, l, b, r; // top, left, bottom, right
    50.     int d;          // difference of numbers in a rectangle
    51.     for (int i = 0; i < q; ++i) {
    52.         t = next_int(); l = next_int();
    53.         b = next_int(); r = next_int();
    54.         d = board[b][r] - board[t-1][r] - board[b][l-1] + board[t-1][l-1];
    55.         printf("%d\n", (d < 0) ? -d : d);
    56.     }
    57.  
    58.     return 0;
    59. }

  6. #676
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Võ đường quán: Tuyển tập đề thi các kì thi Olympic tin học

    @cvht: good work
    Đúng là chỉ cần lưu cái phần diff là đủ, code cũng gọn hơn nhiều.
    Code bạn chạy chậm do bạn dùng getchar() thôi, thằng đó thread safe, nên rùa tí. Bỏ thằng getchar_unlocked vào là code bạn chắc chỉ 0.1s Tuy nhiên nên hạn chế mấy cái hack này, dùng nó để show-off trên ranking thôi, chứ giải thuật đúng thì cin, cout vẫn AC ầm ầm.

  7. #677
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Bỏ thằng getchar_unlocked vào là code bạn chắc chỉ 0.1s
    Đã ham hố post code thử xem đúng thế không, vẫn là 0.34s thôi. =.=" Nhưng như thế đã là nhanh lắm rồi, vì đa phần bài này toàn > 0.5s.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  8. #678
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @doicanhden: Em thử thằng này, chắc là nhanh hơn
    C++ Code:
    1. /* VBOARD: Difference of values in a rectangular part of a chessboard.  */
    2.  
    3. #include <cstdio>
    4.  
    5. #define MAXSIZE     501     /* +1 as the index starts from 1.  */
    6.  
    7. /* board[i][j] contains the sum of elements (with appropriate signs) in the
    8.  * rectangle (1,1)-(i,j).  Elements in row 0 and column 0 are automatically set
    9.  * to zero (as board is global), and are used to avoid boundary tests.  */
    10. int board[MAXSIZE][MAXSIZE];
    11.  
    12. /**
    13.  * Fast IO
    14.  */
    15. const int BUFFSIZE = 10240;
    16. char BUFF[BUFFSIZE + 1], *p = BUFF;
    17. int CHAR, SIGN, BYTES = 0;
    18. #define GETCHAR(c) {                                \
    19.     if(p-BUFF==BYTES && (BYTES==0 || BYTES==BUFFSIZE)){BYTES=fread(BUFF,1,BUFFSIZE,stdin);p=BUFF;}  \
    20.     if(p-BUFF==BYTES && (BYTES>0 && BYTES<BUFFSIZE)){BUFF[0]=0;p=BUFF;}                 \
    21.     c = *p++;                                       \
    22. }
    23. #define DIGIT(c) (((c) >= '0') && ((c) <= '9'))
    24. #define LETTER(c)(((c) >= 'a' && (c) <= 'z') || ((c) >= 'A' && (c) <= 'Z'))
    25. #define MINUS(c) ((c)== '-')
    26. #define GETNUM(n) {                             \
    27.     n = 0;SIGN = 1; do{GETCHAR(CHAR);}while(!(DIGIT(CHAR)|| MINUS(CHAR)));  \
    28.     if(MINUS(CHAR)){SIGN = -1; GETCHAR(CHAR);}      \
    29.     while(DIGIT(CHAR)){n = 10*n + CHAR-'0'; GETCHAR(CHAR);}if(SIGN == -1){n = -n;}\
    30. }
    31.  
    32. int main() {
    33.     /* Get the board size.  */
    34.     int n;
    35.     int q;
    36.     int k;  // number to be read for the current square
    37.     int s;  // sum of numbers in a row up to the current square
    38.     int t, l, b, r; // top, left, bottom, right
    39.     int d;          // difference of numbers in a rectangle
    40.  
    41.     GETNUM(n);
    42.  
    43.     /* Read numbers in the board, and update board as reading.  Again, element
    44.      * board[i][j] is the sum of numbers (with signs) in (1,1)-(i,j).  */
    45.     for (int i = 1; i < (n + 1); ++i) {
    46.         s = 0;
    47.         for (int j = 1; j < (n + 1); ++j) {
    48.             GETNUM(k);
    49.             s += ((i + j) & 1) ? -k : k;
    50.             board[i][j] = board[i - 1][j] + s;
    51.         }
    52.     }
    53.  
    54.     /* Get and solve puzzles.  */
    55.     GETNUM(q);
    56.     for (int i = 0; i < q; ++i) {
    57.         GETNUM(t);
    58.         GETNUM(l);
    59.         GETNUM(b);
    60.         GETNUM(r);
    61.         d = board[b][r] - board[t - 1][r] - board[b][l - 1] + board[t - 1][l - 1];
    62.         printf("%d\n", (d < 0) ? -d : d);
    63.     }
    64.     return 0;
    65. }

  9. #679
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    ^
    0.19s. =)) Khủng thật. Tài khoảng spoj của anh là "spoj_tyrant" phải không ạ? Có một bài 0.17s ngay bên dưới bài em vừa post. =))

    =)) Vừa xem lại code của cvht, ra là sửa thiếu 1 cái getchar(). 0.15s Luôn đấy.

    Attached Thumbnails Attached Thumbnails report.png  
    Đã được chỉnh sửa lần cuối bởi doicanhden : 21-08-2013 lúc 06:26 AM. Lý do: Ghi nhầm tên. =.="
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  10. #680
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    @doicanhden: I don't know
    Đã được chỉnh sửa lần cuối bởi rox_rook : 21-08-2013 lúc 06:54 AM.

Các đề tài tương tự

  1. Tài liệu lập trình C Cần đề cương hướng dẫn Olympic tin học C
    Gửi bởi Doreamon9x trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 0
    Bài viết cuối: 22-07-2010, 10:51 AM
  2. Các đề thi Olympic qua các năm
    Gửi bởi cafelanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 17
    Bài viết cuối: 06-06-2010, 07:22 PM
  3. Xin hỏi về việc học olympic tin học
    Gửi bởi saolion trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 2
    Bài viết cuối: 04-09-2009, 01:13 PM
  4. Đề thi Olympic Quốc Nội !
    Gửi bởi Template trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 27-11-2008, 05:37 PM
  5. Xin Ebook tương tự các đề thì olympic tin học
    Gửi bởi bathong trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 3
    Bài viết cuối: 30-10-2008, 10:33 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn