LTPMSEQ spoj – Tìm xâu

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệ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 *