SPOJ.COM - Thuật toán bài VMSUBSTR - Vườn cây của ba

Đề bài:

Sau một năm học cày cuốc vất vả; Hè này Huy quyết định mời bạn về quê chơi. Huy sẽ dẫn bạn đi leo núi, ngắm cảnh... và sẽ mở một buổi chiêu đãi bạn tài nhà mình. "Nhà rộng và đẹp lắm, có cả một vườn cây ăn trái sum xuê !" - Huy giới thiệu về ngôi nhà của mình.

Sau khi kì kèo với ba, Huy đã xin được hái trái trong vườn đãi bạn. Nhưng với một điều kiện: Huy chỉ được hái trái những LOẠI cây mà ba qui định. Vườn cây chia thành L khu đất liên tiếp nằm thẳng hàng (được đánh số thứ tự từ 1 đến L từ đầu vườn đến cuối vườn), mỗi khu chỉ trồng duy nhất một cây. Nhà Huy có rất nhiều nhân công, mỗi nhân công sẽ chấp nhận làm việc trên những khu đất liên tiếp.

Vì muốn đãi bạn thật nhiều trái cây, nên Huy sẽ tận dụng hái hết TẤT CẢ những cây được ba cho phép. Nhưng mắc nỗi phải dẫn bạn đi chơi ròi, nên không có thời gian hái trái cây. Nên Huy sẽ nhờ đến các nhân công.

Bạn tính xem Huy sẽ phân công ít nhất bao nhiêu nhân công để thực hiện kế hoạch chiêu đãi trái cây của mình? Biết rằng mỗi nhân công sẽ hái hết tất cả trái cây ở các khu đất mình được phân vào.

Đầu vào

Dòng 1: Gồm 1 số nguyên dương duy nhất: L - số khu đất trong khu vườn.

Dòng 2: Chứa xâu S gồm đúng L chữ cái Latin (in thường hoặc hoa), miêu tả khu vườn của Huy. Mỗi chữ cái cho biết loại cây được trồng ở khu đất tương ứng

Dòng 3: Q - số trường hợp mà bạn phải xứ lý.

Q dòng tiếp, mỗi dòng mô tả một trường hợp và gồm các chữ cái Latin (in thường hoặc hoa). Mỗi chữ đại diện cho một loại cây được phép sử dụng.

Đầu ra

Với mỗi trường hợp, ghi ra 1 dòng duy nhất là số nhân công ít nhất cần nhờ đến.

Giới hạn:

L ≤ 1,000,000;

Q ≤ 100,000;

Số ký tự trong mỗi query không quá 52.

Trong mỗi query, các ký tự không lặp lại Trong 50% số test, L ≤ 1000, Q ≤ 1000;

Ví dụ

Đầu vào:

7
abacaba
3
ac
b
ab

Đầu ra:

3
2
2

Giải thích:

• Với trường hợp 'ac', Huy chỉ hái những cây loại 'a' và 'c'. Nên Huy cần nhờ ít nhất 3 nhân công lo 3 phần 'a', 'aca', 'a';

• Với trường hợp 'b', Huy cần nhờ ít nhất 2 nhân công lo 2 phần 'b';

• Với trường hợp 'ab', Huy cần nhờ ít nhất 2 nhân công lo 2 phần 'aba';

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://vn.spoj.com/problems/VMSUBSTR/

Phân tích

• Mình sẽ sử dụng thuật toán tham lam Greedy để giải quyết bài toán.

• Trước tiên, mình sẽ dùng một mảng đếm, mục đích là để đánh dấu xem trong các loại quả thì quả nào được phép hái. Sau khi đã có mảng đánh dấu rồi thì mình sẽ duyệt mảng, để tìm ra các cụm mà chỉ có những phần tử thuộc tập cho phép liền nhau. Đó chính là kết quả

• Xin mời bạn theo dõi cách triển khai của mình sau đây.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
using namespace std;

const int MAX = 1000005;
const int MAX_QUERY = 55;

int  L;                 // Số khu đất trong vườn
char S[MAX];            // Xâu đầu vào
int	 Q;                 // Số testcase
char Query[MAX_QUERY];  // Xâu querry
int  MinHuman;          // Số nhân công tối đa.
int  Count[150];        // Kiểm tra chữ cái có xuất hiện trong querry hay không.

int main()
{
	//freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin >> L >> S >> Q;
	for(int i = 0; i < Q; i++)
	{
		for(int i = 0; i < 150; i++)
			Count[i] = 0;

		// Nhập đầu vào
		MinHuman = 0;
		cin >> Query;

		// Đánh dấu các kí tự xuất hiện trong xâu query
		int Leng = 0;
		while(Query[Leng] != '\0')
		{
			Count[Query[Leng]] = 1;
			Leng++;
		}

		// Duyệt từ đầu đến cuối mảng
		// Tìm ra số cụm chỉ toàn các kí tự thuộc query.
		int before = 0;
		for(int i = 0; i < L; i++)
		{
			if(Count[S[i]] == 1 && before == 0)
			{
				MinHuman++;
				before = 1;
			}
			else if(Count[S[i]] == 0 && before == 1)
			{
				before = 0;
			}
		}
		// In kết quả
		cout << MinHuman << endl;
	}
	return 0;
}