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
Trả lời: PSTRING (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Ủ ĐỀ - Trả lời: PSTRING
#36289
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
PSTRING 9 năm, 11 tháng trước   (+0)
http://www.spoj.pl/problems/PSTRING/
Mọi người giải quyết bài này thế nào? Các cao thủ ra tay dùm cái
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36301
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
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: PSTRING 9 năm, 11 tháng trước   (+0)
Bài này mình nghĩ là qhd O(length(x) * length(y)).
Gọi f[i, j] là số kí tự bỏ đi ít nhất từ xâu x[1..i] để xâu còn lại không nhận xâu y[1..j] làm xâu con.
Nếu nhiều test chắc vẫn không qua dc.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36303
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
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: PSTRING 9 năm, 11 tháng trước   (+0)
Bạn có thể nói rõ hơn về công thức được không? Mình chưa nghĩ ra.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36304
lightning31 (Thành viên)
lightning31
Nhắm mắt code không bug
Bài viết: 168
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: PSTRING 9 năm, 11 tháng trước   (+0)
Theo mình nghĩ qua thì là thế này:
f[i, j]: là số kí tự ít nhất bỏ đi từ i kí tự đầu tiên trong xâu X để xâu còn lại không chứa xâu Y và có đúng j kí tự cuối cùng trùng với j kí tự đầu tiên của xâu Y.

* Khởi tạo: f[i][j] = oo với mọi i, j. f[0, 0] = 0;

* QHD: for i: 0 -> length(x) - 1
for j: 0-> length(y) - 1
begin
// ko sử dụng kí tự x[i + 1]
f[i + 1, j] := min(f[i + 1, j], f[i, j] + 1);
// có sử dụng kí tự x[i + 1]
j + x[i + 1] -> j2 (biến đổi bằng kmp qhd từ trước)
if j2 < length(y) then f[i + 1, j2] := min(f[i + 1, j2], f[i, j]);
end;

* Lấy kết quả: res := min (f[length(x), j]) với 0 <= j <= length(y) - 1

* Độ phức tạp: O(length(x) * length(y)). Mình nghĩ là có vài test thì cũgn vẫn chạy được trong thời gian 3s vì thuật toán khá đơn giản, ít phép tính toán. Phần qhd kmp chuẩn bị sẵn chạy cũng nhanh vì chỉ có độ phức tạp O(length(y)).
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36317
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
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: PSTRING 9 năm, 11 tháng trước   (+0)
Lúc Trước mình tưởng xâu con có thể không liên tiếp . Tại đề bài không nói rõ, xem lại test ví dụ mới biết. Trong trường hợp xâu con liên tiếp thì cũng phức tạp hơn một chút. Mình cũng làm như lightning31.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36441
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
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: PSTRING 9 năm, 11 tháng trước   (+0)
Ừ mình cũng nhầm sang xâu con không liên tiếp. Mọi người thử nghĩ xem liệu có thể giải bài này với xâu con không liên tiếp với độ phức tạp đa thức được hay không?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36448
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
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: PSTRING 9 năm, 11 tháng trước   (+0)
Nếu là không liên tiếp thì bài toán sẽ dễ hơn. Không cần sử dụng kmp, qhđ với trạng thái như mình nói ở trên.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã 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