Game xe tăng bằng C++

Trong lúc rảnh mình làm được một game xe tăng cho 2 người bằng C++. Nên share. Hi vọng mọi người thấy thú vị, Enjoy =))
Tank

Một số bài toán thú vị tuần 1 ( 1/5 - 7/5/2017)

Giới thiệu chuyên mục :
 Đây là chuyên mục ghi lại một vài toán tôi cho rằng thú vị tôi gặp trong 1 tuần và cách giải và 1 số hướng đi của nó. Hy vọng các bạn thích nó.

Bài toán 1: Permutation Happiness
Tóm tắt đề : Cho n người với mỗi chỉ số phân biệt từ 1 --> n. Họ xếp thành 1 hàng. Người thứ i được cho là hạnh phúc nếu có ít nhất 1 trong 2 người đứng cạnh anh ta có chỉ số lớn hơn anh ta.
Cho n (n <= 3000) và k <= n. Đếm số cách để xếp để tồn tại ít nhất k người hạnh phúc.

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