Not yet registered? Create a OverBlog!

Create my blog

Nick

Nick

Associated tags : acm, dp, dp bitmask, kmp, trie

Blogs

Diary of a wimpy algorithmist

Diary of a wimpy algorithmist

hihi hehe hoho :*
Nick Nick
Articles : 37
Since : 11/06/2014

Articles to discover

UVA 12526 - Cellphone Typing

Một nhóm nghiên cứu đang tìm cách phát triển 1 phần mềm giúp gõ bàn phím nhanh hơn bằng cách phát triển 1 tập từ điển gồm n xâu, giả sử khi gõ 1 xâu P, ta đã gõ đến vị trí i, c1c2...ci, phần mềm sẽ kiểm tra xem nếu tồn tại 1 kí tự c sao cho tất cả các từ trong từ điểm

Spoj SEC

Bessie định dẫn đàn bò đi trốn. Để đảm bảo bí mật, đàn bò liên lạc với nhau bằng cách tin nhắn nhị phân. Từng là một nhân viên phản gián thông minh, John đã thu được M (1 <= M <= 50,000) tin nhắn mật, tuy nhiên với tin nhắn i John chỉ thu được b_i (1 <= b_i <= 10,000) bit đầu

[Manacher] Codechef TACHEMIS

http://www.codechef.com/problems/TACHEMIS Algorithm: Áp dụng manacher cho n compressed string Do nếu các các compressed string ghép lại đk thành 1 PS thì độ dài của PS đó chắc chắn lẻ nên ta ko cần bước thêm các "#" như Manacher nguyên bản int C = 1, R = 1; a[0]=MP('#',0); a[n+1]=MP('@',0); for (int i = 1; i <

[Hashing 2 dimensions] UVA 11019 Matrix Matcher

Given an N * M matrix, your task is to find the number of occurences of an X * Y pattern (N,M<=1000, X,Y<=100) Algorithm: Hashings trên ma trận 2 chiều: ull hash() { ull res=0; FOR(i,0,x-1) { ull u=0; FOR(j,0,y-1) u=u*base1+b[i][j]; res=res*base2+u; } return res; } Hash ma trận N*M: ull u=1; FOR(i,1,y-1) u=u*base1; FOR(i,0,n-1) { ull tg=0; F

UVA 12506 Shortest Names

Trong 1 ngôi làng, mọi người đều có tên rất dài. Để thuận tiện họ gọi nhau = prefix của tên. Một prefix của tên 1 người có thể được dùng để gọi người đó nếu nó ko fai là prefix của tên 1 người khác. Cho tên của n người trong làng (n<=1000, tổng độ dài của n tên <=1000
Chiến thuật ACM [3x1=4]

Chiến thuật ACM [3x1=4]

Điều căn bản: Luyện tập, Luyện tập, Luyện tập! Để chiến thuật được thực hiện hiệu quả, bạn không cần phải là thiên tài bởi vì việc luyện tập có thể đưa bạn đi đủ xa. Trong triết lí của chúng tôi, có 3 đặc điểm mấu chốt để tạo nên 1 team xuất sắc: Kiến t

[Latin America 2011] Diccionário Portuñol

Cho 2 tập xâu S, P (|S|, |P| <=1000, mỗi xâu có độ dài <=1000, tổng độ dài mỗi tập <=10^5) Đếm số xâu khác nhau tạo được bằng cách nối 1 prefix khác rỗng của S với 1 suffix khác rỗng của P. Sample Input 3 3 mais grande mundo mas grande mundo 1 5 a aaaaa aaaaaa aaaaaaa a aaaaaaaaa 1 1 abc abc 0 0 Sa

[OOP] const char *p vs char const *p

const char* p kí tự mà p trỏ tới là hằng => có ko thể thay đổi giá trị của kí tự đó nhưng có thể có thể trỏ p tới ô nhớ khác char const* p pointer p là hằng => có thể thay đổi dữ liệu mà nó trỏ tới mà ko thể thay đổi ô nhớ mà p trỏ tới. char a = 'x'; char b = 'y'; char * con

Spoj Chain2

Chuỗi từ có độ dài n là một dãy các từ w1, w2, ..., wn sao cho với mọi 1 ≤ i < n, từ wi là tiền tố của từ wi+1. Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u. Cho tập hợp các từ S={s1, s2, ..., sm}. Tì
10 thuật toán đang chế ngự thế giới chúng ta [part 1]

10 thuật toán đang chế ngự thế giới chúng ta [part 1]

Thuật toán là gì? Về mặt lí thuyết, thuật toán là một thủ tục tính toán, nhận đầu vào là một tập các giá trị được gọi là input và tạo ra một tập các giá trị được gọi là output. Vì vậy thuật toán là một chuỗi các bước biến đổi input thành output. -Nguồn: Thomas H.