Centroid và một số bài toán nhỏ

Centroid và một số bài toán nhỏ

* Khi giải thuật n*n --> nlogn

Đây là một giải thuật khá hữu dụng để xử lí các bài toán về cây mà mình mới học được, và có sự tham khảo rất lớn từ:

+ https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

+ http://www.geeksforgeeks.org/centroid-decomposition-of-tree/

Bài toán truy vấn 2: Truy vấn trên đồ thị

Sau đây mình xin trình bày một số bài toán có sử dụng truy vấn trên đồ thị 

Bài toán 1: Cho n đỉnh, và n-1 giai đoạn. Giai đoạn i cho phép ta liên kết đỉnh i+1 à với 1 đỉnh nào đấy(<i) . Ban đầu có đỉnh 1. Bài toán đặt ra: Với mỗi giai đoạn, hãy tìm khoảng cách xa nhất giữa 2 đinh bất kì.

DP part 5 - Last version

II.5 Kho báu kia kìa

Bài toán: Cho bản đồ n*m (n, m <=1000). Ô i,j có giá trị là a(i,j)
Ta sẽ xuất phát từ 1 ô bất kì ở cột 1 đến 1 ô bất kì ở cột n . Chi phí đường đi sẽ là tổng giá trị các ô. Ta cần tính đường đi với chi phí nhỏ nhất.
Từ (i,j) --> (i+1,j) hoặc (i,j+1)

VD: Với hình 3*3

1 2 3

4 5 6

7 8 9

DP_part 4

II.4. Bài toán biến đổi xâu

Bài toán: Cho 2 xâu A, B. Ta muốn biến xâu A --> B sau 1 số thao tác và mất một vài chi phí như sau

( lưu ý các phép biến đổi đều chỉ diễn ra trên xâu A) 

+ insert(i,c) -- Chèn vào sau vị trí i , chữ cái c. với chi phí x 

+ replace(i,c) -- thay thế chữ cái thứ i bằng chữ cái c với chi phí y

+ delete(i) xóa chữ cái thứ i với chi phí z

--> in ra chi phí nhỏ nhất.

input:  Nhâp x, y, z và 2 xầu A, B( lenA , lenB <= 1000)

output:  In ra chi phí nhỏ nhất (output đảm bảo <= 10^9)

DP_ part 3

II.3.LCS dãy con chung dài nhất

Ta xét bài toán sau:
Cho 2 xâu, tìm xâu con chung dài nhất của chúng.  độ dài của mỗi xâu <= 1000

Bài toán truy vấn 1:IT

IT:
Cơ bản:
+  QMAX
+  QMAX2
+  NKBRACKE
Trung bình,khó
+ http://vn.spoj.com/problems/PATULJCI/
+ http://vn.spoj.com/problems/GSS/
+ http://tjsct.wikidot.com/usaco-feb08-gold
+ http://usaco.org/index.php?page=viewproblem2&cpid=365

Solution_tuần 1

HSPC14A - Biến đổi cặp số 

Bài toán này , để đơn giản , ta sẽ làm ngược bài toán : 

từ 2 số (a,b) sử dụng các thao tác:

+(a , a-b) (nếu a>b)

+ (b, b-a) (nếu b>a)

sao cho đưa về trạng thái (1,1)

nhận thấy đấy chính là thao tác tìm UCLN của 2 số

Do số test nhỏ <= 10 nên ta có giải thuật đơn giản sau:

+ với mỗi số X , ta cần tìm Y để sao cho số UCLN (X,Y) = 1 và số bước tìm UCLN min 

+ Giờ đây ta có hàm F(x,y) là số bước đưa số X,Y về trạng thái (1,1) --> F(x,y) == F(y%x, x) + y/x;

( với y>=x) 

Dưới đây là code của mình : http://ideone.com/zDKK0N 

1 số bài toán đơn giản ...

http://vn.spoj.com/problems/HSPC14A/
http://vn.spoj.com/problems/AMSSEQ/
http://vn.spoj.com/problems/FLOYD/
http://vn.spoj.com/problems/REVAMP/
quá đơn giản cho ae code tay hihi

Kì thì HSGSO - Olympic Chuyên KHTN

Đây là kì thi do trường THPT chuyên KHTN tổ chức .

Dưới đây là link đề bài của ki thì . Chúc ae vui vẻ .click vào đây

LIS_chặt nhị phân

Bonus: Bài toán LIS sử dụng chặt 
nhị phân 

Bài toán : Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N]. 
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn 
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử? 
Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 30000).
• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

DP_part 2

Phần II: Các bài toán và áp dụng.

Quy hoạch động thường được chia làm 2 phần:

          + Trả lời:

-         Khởi tạo.

-         Tính toán dựa theo công thức truy hồi.

          + Truy vết: in ra cấu hình tối ưu.

II.1: LIS _ Khởi đầu của DP

1.     Bài toán tổng quát.

LIS là từ viết tắt của Longest Increasing Subsequence LIS (dãy con tăng dài nhất ). Bài toán được phát biểu tổng quát như sau:

DP_part1

DP_quy hoạch động

Lời mở đầu

Đây là blog đầu tiên của tôi nên không tránh khỏi sai sót, mong bạn đọc thông cảm và góp ý với

mình ạ. ^^

Tin học mới xuất hiện, nhưng tầm ảnh hưởng của nó là vô cùng lớn. Thời đại nay, đâu đâu cũng thấy tin học, từ những chiếc máy tính để bàn, đến các công cụ, các phần mềm lập trình như C, C++ , Pascal, Python, VC , ... , hay lớn hơn nữa chính là mạng xã hội :facebook, twitter ,instagram,.. Trong bài viết này mình sẽ đề cập đến 1 vấn đề như hạt cát nhưng mang tính nền móng của tin