[Thuật toán] Bài toán số 7

Đề bài: link
Mã bài: VOSSEVEN
Cho chuỗi gồm N ký tự, mỗi ký tự là một chữ số từ 0 đến 9
Yêu cầu: Với mỗi đoạn con có số 7 liên tiếp hãy đếm xem đoạn con đó xuất hiện bao nhiêu lần trong chuỗi.

Input

Chuỗi s

Output

Mỗi dòng ghi một độ dài tương ứng từ thấp đến cao kèm số lần xuất hiện của nó. Dữ liệu vào đảm bảo xâu có ít nhất 1 số 7. Nếu số lần xuất hiện bằng 0 thì không in ra gì.
Example
Input: 72774777 Output:
1 6
2 3
3 1
Giới hạn:

• 30% số test có N <= 10^3.
• 30% số test có N <= 10^5.
• Trong tất cả các test  N <= 10^6.

* Gọi f[i] là số các xâu chỉ gồm các số 7 liên tiếp và có độ dài là i.
VD với chuỗi 72774777 thì f[1] = 1, f[2] = 1, f[3] = 1.
* Gọi ans[i] là số các xâu có độ dài i xuất hiện trên xâu s. Dễ dàng nhận thấy nếu từ xâu có độ dài là i sẽ tạo ra được 1 xâu độ dài i, 2 xâu độ dài (i-1), … , nếu có f[i] xâu độ dài i sẽ tạo được ra f[i] xâu độ dài i, f[i]*(i-j+1) xâu độ dài j.
VD f[1] = 1 thì có 1 xâu độ dài 1.
f[2] = 1 thì có 1 xâu độ dài 2, f[2]*(2-1+1) = 2 xâu có độ dài 1.
f[3] = 1 thì có 1 xâu độ dài 3, f[3]*(3-2+1) = 2 xâu độ dài 2, f[3]*(3-1+1) = 3 xâu có độ dài 1.
->Duyệt vòng i, nếu f[i]>0:
->ans[j]=ans[j]+f[i]*(i-j+1), với j0.

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main(){
	string s;
	cin >> s;
	int n = s.length();
	int *f = new int[n + 1];
	int *ans = new int[n + 1];
	
	for (int i=0; i<=n; i++){
		f[i] = ans[i] = 0;
	}
	// duyet tinh f[i]
	for (int i=0; i<n; i++){
		int c = 0;
		while(i < n && s[i] == '7'){
			c++;
			i++;
		}
		if (c > 0){
			f++;
		}
	}
	/*
	for (int i=1; i<=n; i++){
		cout << f[i] << " ";
	}
	cout << endl;
	*/
	
	// duyet tinh ans[i]
	for (int i=n; i>0; i--){
		if (f[i] > 0){
			for (int j=0; j<=i; j++){
				ans[j] += f[i]*(i-j+1);
			}
		}
	}
	
	// duyet in ra ket qua
	for (int i=1; i<=n; i++){
		if (ans[i] > 0){
			printf("%d %d
", i, ans[i]);
		}
	}
	//cout << endl;
	
	return 0;
}

Trong code trên các bạn cần lưu ý khi xuất kết quả nên dùng printf, nếu dùng cout thì xuống dòng bằng “ ” vì endl sẽ chậm rất nhiều so với “ ”, mình đã dính đoàn chỗ này. Rất may sau khi tham khảo ý kiếm ace trên VNOI