Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
ACM 2010 ĐHQG HN ! (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 1
CHỦ ĐỀ - ACM 2010 ĐHQG HN !
#32784
white_cobra (Thành viên)
Nhắm mắt code không bug
Bài viết: 188
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+1)
Sao không ai chúc mừng Anh TranHaiDang đạt vô địch siêu cúp nhỉ
Mà siêu cúp sao có 6 người thi thế . Năm ngoái thấy có anh TinAms thi mà
 
Đã lưu IP Đã lưu IP  
 
Khiêm tốn , thật thà , dũng cảm
  Đã khóa chức năng gửi bài.
#32795
technolt (Admin)
technolt+70
Admin
Bài viết: 296
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
Test và solution bài K
File gửi kèm:
Tên file: K.rar
Độ lớn file: 2560
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32800
hoangle (Thành viên)
Biết code binary-indexed tree
Bài viết: 47
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+1)
tunght_53 viết:
QUOTE:
Em ở đội UET6 trình độ nói chung là gà không tả(lên đại học mới sờ máy tính). Đội anh Tuấn có làm được bài D không bảo em với, thầy Lê Sỹ Vinh bảo bài này quy hoạch động cơ bản :o :o :o :o


Cũng không cơ bản lắm, còn có thể coi là khó nếu bị ám ảnh bởi cái thuật toán cổ điển tìm dãy con chung dài nhất.
Để tìm dãy con chung dài nhất của x1...m và y1...n trong đó m khá nhỏ và n khá lớn, bạn có thể QHĐ theo kiểu
Gọi F[i, k] là chỉ số j nhỏ nhất mà dãy con chung dài nhất của x[1..i] và y[1..j] có độ dài k.
Màng f kích thước mxm.

Thuật toán này có trên bài báo của Hunt năm 1977. Có thể đáp án còn có cách tốt hơn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32806
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
hoangle viết:
QUOTE:

Cũng không cơ bản lắm, còn có thể coi là khó nếu bị ám ảnh bởi cái thuật toán cổ điển tìm dãy con chung dài nhất.
Để tìm dãy con chung dài nhất của x1...m và y1...n trong đó m khá nhỏ và n khá lớn, bạn có thể QHĐ theo kiểu
Gọi F[i, k] là chỉ số j nhỏ nhất mà dãy con chung dài nhất của x[1..i] và y[1..j] có độ dài k.
Màng f kích thước mxm.

Thuật toán này có trên bài báo của Hunt năm 1977. Có thể đáp án còn có cách tốt hơn :p


Vậy thuật toán này có độ phức tạp O(min(m,n)^2), chắc đủ để pass bài này rồi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32807
tunght_53 (Thành viên)
tunght_53
Đã biết code đệ quy
Bài viết: 8
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
Lúc cuối bọn em định làm thế này nhưng mà vội quá code sai mất . Các anh xem hộ em xem có đúng không
Code:
 
#include <iostream>
using namespace std;
#define SIZE 300
#define MAX 10001
int a[300][10001] = {0}, b[10001];
string s2, s1;
 
int get(char c) {
    return int(c);
}
 
int search(int i, int j) {
    int t = get(s2[i]);
//    for(int k = 1; k <= a[t][0]; ++k) {
//        if(a[t][k] > b[j-1]) {
//            cout << "found " << a[t][k] << endl;
//            break;
//            //return a[t][k];
//        }
//    }
 
    int s = 1, e = a[t][0];
    if(a[t][e] <= b[j-1]) return MAX;
 
    while(s < e) {
        int mid = (s+e)/2;
        if(a[t][mid] > b[j-1]) {
            e = mid;
        }
        else {
            s = mid+1;
        }
    }
 
    if(a[t][s-1] > b[j-1] && s > 1) {
        //cout << "1 " << a[t][s-1] << endl << endl;
        return a[t][s-1];
    }
    //cout << "2 " << a[t][s] << endl << endl;
    return a[t][s];
}
 
int solve() {
    fill(b, b+MAX, MAX);
    b[0] = -1;
    int l2 = s2.length();
    int l = 0;
 
    for(int i = 0; i < l2; ++i) {
        //cout << i << " " << s2[i] << endl;
        for(int j = l+1; j > 0; --j) {
            int temp = search(i, j);
            //cout << "temp " << temp << " " << b[j] << endl;
            if(temp < b[j]) {
                //cout << "Thay " << endl;
                if(j >= l+1) {
                    l++;//cout << "Cong" << endl;
                }
                b[j] = temp;
            }
        }
        //cout << endl << "l " << l << endl;
    }
    //cout << l << endl <<  endl;
 
    return l;
}
 
int main() {
    int test, n;
    cin >> test;
    for(int ind = 0; ind < test; ++ind) {
        cin >> s1;
 
        int l1 = s1.length();
        //int l2 = s2.length();
        for(int i = 0; i < SIZE; ++i) {
            a[i][0] = 0;
        }
        for(int i = 0; i < l1; ++i) {
            a[get(s1[i])][0]++;
            a[get(s1[i])][a[get(s1[i])][0]] = i;
        }
 
        /*
        for(int i = 0; i < SIZE; ++i) {
            cout << a[i][0] << " " << char(i+'a') << endl;
            for(int j = 1; j <= a[i][0]; ++j) {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        //*/
        //*
        cin >> n;
        cin.ignore(1);
        int max = 0;
        for(int i = 0; i < n; ++i) {
            cin >> s2;
            int temp = solve();
            //cout << "hello s2 " << s2 << endl;
            //cout << "hello temp " << temp << endl;
            if(temp > max) {
                max = temp;
            }
            /*
            cout << "b " << endl;
            for(int j = 0; j < 10; ++j) {
                cout << b[j] << " " ;
            }
            cout << endl;
            //*/
        }
        cout << max << endl;
    }
    /*/
    cin >> n;
    cin.ignore(1);
    cin >> s2;
    solve();
    //*/
    return 0;
}
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32810
super_saiyan (Thành viên)
Đang tập code
Bài viết: 1
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
Olympic năm sau tổ chức ở đâu zậy mí bạn?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32816
ductam (Thành viên)
ductam+16
Nhắm mắt code không bug
Bài viết: 185
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
super_saiyan viết:
QUOTE:
Olympic năm sau tổ chức ở đâu zậy mí bạn?

Đại học Cần Thơ
 
Đã lưu IP Đã lưu IP  
 
think-solve-solution
  Đã khóa chức năng gửi bài.
#32817
ductam (Thành viên)
ductam+16
Nhắm mắt code không bug
Bài viết: 185
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
white_cobra viết:
QUOTE:
Sao không ai chúc mừng Anh TranHaiDang đạt vô địch siêu cúp nhỉ :x
Mà siêu cúp sao có 6 người thi thế . Năm ngoái thấy có anh TinAms thi mà :S

chúc mừng tranhiadangfpt nha. Vậy là kì thi năm nay hầu như mình đã gặp mặt được tất cả các thành viên mình muốn nhìn thấy mặt rồi. Các bạn giỏi quá. Tiếc quá team NTU không đạt giải nhất. Xin chia vui với giải nhì của các bạn, đồng thời xin chia buồn cùng với các bạn vì để tuột giải nhất.
 
Đã lưu IP Đã lưu IP  
 
think-solve-solution
  Đã khóa chức năng gửi bài.
#32818
tranhaidangfpt (Thành viên)
tranhaidangfpt+1
Super fast coder
Bài viết: 77
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
Cảm ơn mọi người nhé,
Cup vàng: tranhaidangfpt rank 8 VOJ, cup bạc: ktuan rank 9 VOJ, sao dhkhtn không cup bạc nữa đi cho đủ cạ nhỉ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#32821
GiongTo35 (Thành viên)
white_cobra+51
Không code nữa rồi
Bài viết: 497
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ACM 2010 ĐHQG HN ! 10 năm, 2 tháng trước   (+0)
dhkhtn hình như là vdmedragon mà Đang ở Canada sao thi thố đc , mà ổng vào top 10 hồi nào thế ko biết
Anh KTuan cũng giỏi quá , mới vào năm đầu đại học đã giành ngay cái giải nhì siêu cúp
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS