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
Bài B ACM/ICPC Hà nội 2012 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Bài B ACM/ICPC Hà nội 2012
#68376
trumdkny (Thành viên)
Biết code binary-indexed tree
Bài viết: 26
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Bài B ACM/ICPC Hà nội 2012 8 năm, 1 tháng trước   (+0)
Team nào submit được bài B có thể share code được không ?
Mình thì nộp bài này mãi mà vẫn cứ wrong answer ! Ức chế cả buổi.
Mình dùng vét cạn thì mất 47 giây với 20 bộ test max, sau đó cái tiến thì chỉ mất chưa tới 1 giây nhưng lại bị wrong answer ! mặc dù mình đã so sánh kết quả sau khi cải tiến với kết quả vét cạn thì đầu giống nhau, kiểm tra kĩ các trường hợp đặc biết nhưng vẫn wrong answer, thật tình không biết wrong ở đâu.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68378
takiemtam (Thành viên)
takiemtam-
Đã code là AC
Bài viết: 114
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: Bài B ACM/ICPC Hà nội 2012 8 năm, 1 tháng trước   (+0)
Bài B bạn đếm như thế nào
 
Đã lưu IP Đã lưu IP  
 
Thiên hạ đệ nhất kiếm
  Đã khóa chức năng gửi bài.
#68392
phuthuynhochienthan (Thành viên)
chien_than001+1
Biết code binary-indexed tree
Bài viết: 25
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: Bài B ACM/ICPC Hà nội 2012 8 năm, 1 tháng trước   (+0)
Bài B thì ý tưởng của mình là thế này:
Tính số bộ bằng nhau (a,a) từ dãy 1-2, số bộ bằng nhau (b,b) từ dãy 3-4 rồi nhân lại.
Chẳng hạn từ số dãy bằng nhau từ dãy 1-2:

Code:
long long count = 0, count_1 = 0, count_2 = 0;
for(int i = 1; i <= n; i++){
  A[i] = a[i];
  B[i] = b[i];
}
for(int i = 1; i <= n; i++){
  count_1 = 0; count_2 = 0;
  for(int j = 1; j <= n; j++){
    if(A[i] == A[j] && i != j && A[j] > 0){
    count_1++;
    A[j] = -1;
  }
  for(int j = 1; j <= n; j++){
    if(A[i] == B[j] && B[j] > 0){
    count_2++;
    B[j] = -1;
  }
  count += count_1 * count_2;
}
Làm tương tự với cách chọn bộ bằng nhau từ dãy 1-3, 2-4 và 1-4, 2-3. Cộng hết ba giá trị này lại, đặt là x. Sau đó tính số bộ (a,a,a,a) là các số bằng nhau từ các dãy (chú ý làm sao để vẫn giữ độ phức tạp O(n^2), không thì TLE chắc ăn luôn), đặt số bộ này là y. Số hình chữ nhật cần tìm là x-2y. Bài này cần chú ý 2 điều sau: - Các số trong mỗi dãy đều có thể bằng nhau. - Các bộ số là chứa chỉ số chứ không phải chứa độ dài nên hai bộ gọi là khác nhau nếu chúng có chỉ số lấy từ hai dãy là khác nhau tại ít nhất một vị trí. Đooạn tìm bộ (a,a,a,a) mình chọn các số bằng nhau từ dãy 1-2, các số bằng nhau từ dãy 3-4 ra rồi lưu vào trong 2 mảng. Tiếp tục duyệt 2 mảng đó để tìm ra số bộ bốn bằng nhau. Mình biết là cách này còn kém lắm nên các bạn có gì trao đổi thêm nhé!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68409
trumdkny (Thành viên)
Biết code binary-indexed tree
Bài viết: 26
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: Bài B ACM/ICPC Hà nội 2012 8 năm, 1 tháng trước   (+0)
mình làm cũng cách giống như bạn, đã kiểm tra rất kĩ nhưng submit mãi mà cứ bị WA.
Mình làm theo kiểu vét cạn thì bị LTE nhưng so sánh kết quả random của max test thì ra kết quả như nhau. Thật khó hiểu? ko bít wrong chỗ nào
 
Đã 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