LTPMSEQ spoj – Tìm xâu

Nguồn đề bài: http://vn.spoj.com/problems/LTPMSEQ/

1. Đề bài LTPMSEQ spoj

Sau khi đã giải được PTQMSEQ, PM bắt leaxtanh vượt qua thử thách thứ 2 là chứng tỏ tình cảm của mình. Leaxtanh viết ra trên giấy n xâu với những dòng chữ tình cảm.

Sau khi viết xong, với con mắt tinh đời, PM hỏi leaxtanh : có duy nhất 1 xâu xuất hiện lẻ lần. Nếu tìm được thì sẽ đi chơi.

Bạn hãy giúp leaxtanh nhé. 😀

Input

Dòng đầu tiên chứa số n( n<=10^5)

N dòng sau là các xâu st ( length(st) <=15);

Output

1 dòng duy nhất chứa xâu cần tìm.

Nếu không tìm được in ra -1;
Input:
9
Mai
Yeu
Lam
Son
Toi
Toi
Lam
Son
Yeu

Output:
Mai

2. Hướng dẫn LTPMSEQ spoj

Bài này dùng Bitmask bằng phép tính xor. tất nhiên không thể xor chuỗi vs chuỗi rồi 😀 nên bạn sẽ xor theo mã ASCII của nó.

ở đây tân dụng tính chất a xor a = 0 và 0 xor a = a. 1 chữ cái xuất hiện chẵn lần thì khi xor hết lại sẽ được 0, xuất hiện lẻ lần thì sẽ được chính nó. tạo 1 mảng s[15], mỗi khi đọc 1 xâu st, gán lại s[i] = s[i] xor st[i]. khi đọc đủ n xâu thì mảng s còn lại chính là kq.

Ngoài ra bài này còn có thể duyệt, dùng Hash + xor, sort,… cũng làm dc…

3. code tham khảo LTPMSEQ spoj

=================

code tham khảo cho ý tưởng khác (duyệt):

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *