P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}
Khuyên dùng

 

Speak Your Mind

*