Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 69 trên tổng số 69 Đầu tiênĐầu tiên ... 1959676869
Từ 681 tới 688 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. #681
    Ngày gia nhập
    04 2013
    Nơi ở
    $HOME
    Bài viết
    48

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

    Không nghĩ là có thể giảm thời gian đến được 0.15s. Chưa thử những hacks này bao giờ. Nice hacks!
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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

    hack io gì kinh thế, thử rút gọn hàm của ông rox lại

    thử fail :-"

  3. #683
    Ngày gia nhập
    03 2011
    Nơi ở
    Hà Nội
    Bài viết
    89

    cám ơn anh rox_rook bài này em AC rồi
    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    @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. }
    bài này mình code ok rồi ctdl là quy hoạch động
    C++ Code:
    1. #include<iostream>
    2. #include<cstdio>
    3. #include<cstdlib>
    4.  
    5. using namespace std;
    6.  
    7. int main()
    8. {
    9.     freopen("VBOARD2.inp","r",stdin);
    10.     freopen("VBOARD2.out","w",stdout);
    11.     int n,q;
    12.     int s[501][501],a[501][501];
    13.     int i1,j1,i2,j2;
    14.     int res;
    15.     scanf("%d",&n);
    16.     for(int i=1; i<=n; ++i)
    17.         for(int j=1; j<=n; ++j)
    18.             scanf("%d",&a[i][j]);
    19.     for(int i=1; i<=n; ++i)
    20.         a[0][i]=0;
    21.     for(int i=0; i<=n; ++i)
    22.         a[i][0]=0;
    23. //quy hoach dong tich luy trong mang S[][]
    24.     for(int i=1; i<=n; ++i)
    25.         for(int j=1; j<=n; ++j)
    26.         {
    27.             if((i+j)%2==0)
    28.                 s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    29.             else
    30.                 s[i][j]=-a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    31.         }
    32.    /* for(int i=0; i<=n; ++i)
    33.     {
    34.         for(int j=0; j<=n; ++j)
    35.             printf("%3d",s[i][j]);
    36.         printf("\n");
    37.     }*/
    38.     scanf("%d",&q);
    39.     for(int i=0; i<q; ++i)
    40.     {
    41.         scanf("%d%d%d%d",&i1,&j1,&i2,&j2);
    42.         res=0;
    43.         res+=abs(s[i2][j2]+s[i1-1][j1-1]-s[i1-1][j2]-s[i2][j1-1]);
    44.         printf("%d\n",res);
    45.     }
    46. }
    Đã được chỉnh sửa lần cuối bởi fithou91192 : 12-11-2013 lúc 10:29 AM.

  4. #684
    Ngày gia nhập
    12 2012
    Nơi ở
    vinh
    Bài viết
    1

    Mặc định Đề thi chuyên tin OLP 2010 - Làm mãi không được

    Mọi người giúp e xử lý 2 bài cuối đề chuyên tin 2010 với (bài ĐẾN TRƯỜNG và bài GENOME) em làm mãi mà không biết làm thế nào. Ai biết xin chỉ giùm em cách giải (có code thì càng tốt). Thanks mọi người.

  5. #685
    Ngày gia nhập
    03 2011
    Nơi ở
    Hà Nội
    Bài viết
    89

    mọi người cho em hỏi bài này em sai ở đâu vậy ạ? em submit lên báo lỗi tràn mảng ...bài này em code theo cây interval
    http://vn.spoj.com/problems/QMAX/

    C++ Code:
    1. #include<iostream>
    2. #include<cstdio>
    3. #include<cstring>
    4. #include<algorithm>
    5. #include<cmath>
    6.  
    7. using namespace std;
    8.  
    9. int res,a[50002],t[200001],n,m,q,u,v,k;
    10.  
    11. void update_t(int k,int l,int r)
    12. {
    13.     int mid;
    14.     if(l==r)
    15.     {
    16.         t[k]=a[l];
    17.         return ;
    18.     }
    19.     mid=(l+r)/2;
    20.     update_t(k*2,l,mid);
    21.     update_t(k*2+1,mid+1,r);
    22.     t[k]=max(t[k*2],t[k*2+1]);
    23. }
    24.  
    25. void getmax(int k,int l,int r,int i,int j)
    26. {
    27.     int mid;
    28.     if((l<=i)&&(r<=j))
    29.     {
    30.         res=max(res,t[k]);
    31.         return ;
    32.     }
    33.     mid=(l+r)/2;
    34.     getmax(k*2,l,mid,i,j);
    35.     getmax(k*2+1,mid+1,r,i,j);
    36. }
    37. int main()
    38. {
    39.     freopen("qmax.inp","r",stdin);
    40.     freopen("qmax.out","w",stdout);
    41.     scanf("%d%d",&n,&m);
    42.     memset(a,0,sizeof(a));
    43.     memset(t,0,sizeof(t));
    44.     for(int i=1; i<=m; ++i)
    45.     {
    46.         scanf("%d%d%d",&u,&v,&k);
    47.         a[u]+=k;
    48.         a[v+1]-=k;
    49.     }
    50.     for(int i=1; i<=n; ++i)
    51.         a[i]=a[i]+a[i-1];
    52.     update_t(1,1,n);
    53.     scanf("%d",&q);
    54.     for(int i=0; i<q; ++i)
    55.     {
    56.         scanf("%d%d",&u,&v);
    57.         getmax(1,1,n,u,v);
    58.         printf("%d\n",res);
    59.     }
    60. }

  6. #686
    Ngày gia nhập
    03 2011
    Nơi ở
    Hà Nội
    Bài viết
    89

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

    bài này mình AC rồi ....bài này mình sai trong 2 hàm update_t và getmax
    Trích dẫn Nguyên bản được gửi bởi fithou91192 Xem bài viết
    C++ Code:
    1. #include<iostream>
    2. #include<cstdio>
    3. #include<cstring>
    4. #include<algorithm>
    5. #include<cmath>
    6.  
    7. using namespace std;
    8.  
    9. int res,a[50002],t[200001],n,m,q,u,v,k;
    10.  
    11. void update_t(int k,int l,int r)
    12. {
    13.     int mid; //thiếu trường hợp if(l>r) return ; có thể thừa nhưng đưa thêm vào cho chắc ăn
    14.     if(l==r)
    15.     {
    16.         t[k]=a[l];
    17.         return ;
    18.     }// thêm else cho cả đoạn này ...bảo sao mình dính lỗi tràn mảng
    19.     mid=(l+r)/2;
    20.     update_t(k*2,l,mid);
    21.     update_t(k*2+1,mid+1,r);
    22.     t[k]=max(t[k*2],t[k*2+1]);
    23. }
    24.  
    25. void getmax(int k,int l,int r,int i,int j)
    26. {
    27.     int mid; // tiếp tục là thiếu đk i và j nằm ngoài khoảng
    28.     if((l<=i)&&(r<=j)) // đk này sai (i<=l&&r<=j) phải là l và r nằm trong i và j
    29.     {
    30.         res=max(res,t[k]);
    31.         return ;
    32.     }// thêm else cho cả đoạn này
    33.     mid=(l+r)/2;
    34.     getmax(k*2,l,mid,i,j);
    35.     getmax(k*2+1,mid+1,r,i,j);
    36. }
    37. int main()
    38. {
    39.     freopen("qmax.inp","r",stdin);
    40.     freopen("qmax.out","w",stdout);
    41.     scanf("%d%d",&n,&m);
    42.     memset(a,0,sizeof(a));
    43.     memset(t,0,sizeof(t));
    44.     for(int i=1; i<=m; ++i)
    45.     {
    46.         scanf("%d%d%d",&u,&v,&k);
    47.         a[u]+=k;
    48.         a[v+1]-=k;
    49.     }
    50.     for(int i=1; i<=n; ++i)
    51.         a[i]=a[i]+a[i-1];
    52.     update_t(1,1,n);
    53.     scanf("%d",&q);
    54.     for(int i=0; i<q; ++i)
    55.     {
    56.         scanf("%d%d",&u,&v);
    57.         getmax(1,1,n,u,v);
    58.         printf("%d\n",res);
    59.     }
    60. }

  7. #687
    Ngày gia nhập
    08 2010
    Bài viết
    82

    Các bác thử giải hộ em đề thi siêu cúp chuyên tin năm 2013. Em chưa nghĩ ra các nào ngoài cách duyệt các bác ạ. Mà duyệt thì chỉ ăn được các test nhỏ thôi. Cảm ơn các bác.
    Đề thi đây ạ.
    http://www.olp.vn/olympic/ket-qua---dhe-thi
    Attached Files Attached Files

  8. #688
    Ngày gia nhập
    11 2014
    Bài viết
    1

    Angry Giải đề olympic 2011!

    Nhờ mọi người giúp mình với ! Nghĩ mãi mà chưa ra ý tưởng

    Cho số n ở hệ cơ số 10, có không quá 20 chữ số và không chứa các số 0 không có nghĩa ở đầu. bằng cách xóa 1 hoặc 1 vài chữ số liên tiếp của n (nhưng không xóa hết tất cả các chữ số của n) ta nhận đc những số mới. số mới đc chuẩn hóa bằng cách xóa các chữ số 0 vô nghĩa nếu có. Tập số nguyên D đc xây dựng bằng cách đưa vào nó số n, các số mới khác nhau đã chuẩn hóa và khác n. ví dụ, với n=1005 ta có thể nhận đc các số mới sau;
    * Bằng cách xóa 1 chữ số ta có các chữ số :5 ( từ 005), 105,105,100;
    * Bằng cách xóa 2 chữ số ta có các chữ số: 5 (từ 05), 15, 10;
    * Bằng cách xóa 3 chữ số ta có các số 5 và 1.
    Tập D nhận đc từ n chứa các chữ số { 1005, 105, 100, 15, 10, 5 , 1 }. trong tập D này có 3 số chia hết cho 3, đó là các số 1005, 105 và 15.
    -Yêu cầu: cho số nguyên n. hãy xác định số lượng số chia hết cho 3 có mặt trong tập D đc tạo thành từ n.
    -Dữ liệu: vào từ file văn bản NUMSET.INP gồm 1 dòng chứa số nguyên n.
    -Kết quả: Đưa ra file văn bản NUMSET.OUT một số nguyên- số lượng số chia hết cho 3 tìm đc.
    ???
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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