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
Chuỗi con đối xứng dài nhất (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Ủ ĐỀ - Chuỗi con đối xứng dài nhất
#26829
nhut95 (Thành viên)
nhut95
Đã biết code đệ quy
Bài viết: 14
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#26831
Bom (Thành viên)
Super fast coder
Bài viết: 62
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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
nhut95 viết:
QUOTE:
Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba

Bài này bạn chỉ cần tìm xâu con chung dài nhất của xâu đó với xâu ngược lại của nó thôi..
Tỉ dụ input là abcdecba thì bạn tìm xâu con chung lớn nhất của xâu abcdecba và xâu abcedcba, sau đó truy vết là ra kết quả.
 
Đã lưu IP Đã lưu IP  
 
******* Bà con trật tự nghe thời sự *******
Hãy bẫm nút + ấy nhá nút - ! của tôi bị liệt rồi
  Đã khóa chức năng gửi bài.
#26832
nhut95 (Thành viên)
nhut95
Đã biết code đệ quy
Bài viết: 14
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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
Cám ơn bạn nhe.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#26834
ruacon (Thành viên)
dinhcamnhung-
Nhắm mắt code không bug
Bài viết: 219
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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
Bom viết:
QUOTE:
nhut95 viết:
QUOTE:
Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba

Bài này bạn chỉ cần tìm xâu con chung dài nhất của xâu đó với xâu ngược lại của nó thôi.:).
Tỉ dụ input là abcdecba thì bạn tìm xâu con chung lớn nhất của xâu abcdecba và xâu abcedcba, sau đó truy vết là ra kết quả.


Nhưng với 5000 mà O(N^2) thì...
 
Đã lưu IP Đã lưu IP  
 
Tạm biệt vnoi.
  Đã khóa chức năng gửi bài.
#26835
conmachua (Thành viên)
Super fast coder
Bài viết: 63
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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (-1)
Có thể giảm xuống N^2 div 2 bằng cách gọi F[i,j] là độ dài chuỗi con dối xứng dài nhất của đoạn S[i..j]
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#26838
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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
@conmachua: O(n^2 div 2) thì vẫn là O(n^2)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#27906
programmer2010 (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: Chuỗi con đối xứng dài nhất 10 năm, 6 tháng trước   (+0)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#28453
tacungcay (Thành viên)
trungkien11-
Đã code là AC
Bài viết: 94
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: Chuỗi con đối xứng dài nhất 10 năm, 5 tháng trước   (-1)
đâu có liên wan jì đâu nhỉ??? :s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#44045
pencil_man (Thành viên)
pencil_man
Đã code là AC
Bài viết: 98
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: Chuỗi con đối xứng dài nhất 9 năm, 7 tháng trước   (+0)
5000 mà n^2 thì có sao đâu. Thời gian yêu cầu là 2s mà.
 
Đã 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