欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

XTU online judge 1294 Enquiry

程序员文章站 2022-06-01 22:41:58
...

Description
男女同学排成一列,你想知道第i个到第j个同学之间,男女相邻排列的出现次数。

Input
第一行是一个整数K,表示样例的个数。
每个样例的第一行是一个字符串s,其长度len不超过10000,只含字符M和F,M表示男生,F表示女生。
每个样例的第二行是一个整数n(1≤n≤1000) ,表示查询的次数。
以后的N行,每行两个整数i,j(1≤i<j≤len) ,表示查询的区间。

Output
每个样例的每次查询输出一个整数。

Sample Input
2
MMMMM
3
1 2
1 3
1 5
MFMFM
3
1 5
2 3
3 5

Sample Output
0
0
0
4
1
2

解题思路:

一、暴力解法:

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int k,n,a,b;
	char s[10001];
	memset(s,0,sizeof(s));
	
	scanf("%d",&k);
	while(k--)
	{
		scanf("%s",s);
		scanf("%d",&n);
		
		while(n--)
		{
			int cnt=0;
			scanf("%d %d",&a,&b);
			
			for(int i=a-1;i<b-1;i++)
			{
				if(s[i]!=s[i+1])
					cnt++;
			}
			cout<<cnt<<endl;
		}
	}
	return 0;
} 

二、这种题型也有一种很常见的套路,即求[i, j]的区间的男女相邻次数等于求[1, j]区间男女相邻的次数减去[1, i-1]区间男女相邻的次数。用数组存储各个数的男女相邻次数,然后按照套路计算区间男女相邻的次数即可。

#include <iostream>
#include <cstring>
#include <cstdio>
char s[10001];
int arr[10001];
using namespace std;
int main() 
{
	int K, n, a, b;
	cin >> K;
	while(K--) 
	{
		scanf("%s",s);
		scanf("%d", &n);
		arr[0] = 0;
		int cnt = 1;
		int strlenc = strlen(s);
		for(int i = 1; i < strlenc; i++) 
		{
			if(s[i] != s[i - 1]) 
			{
				arr[cnt] = arr[cnt-1]+1;
			} else 
			{
				arr[cnt] = arr[cnt-1];
			}
			cnt++;
 		}
		while(n--)
		{
			scanf("%d%d", &a, &b);
 			printf("%d\n", arr[b-1] - arr[a-1]);
		}
	}
	return 0;
}
相关标签: 大学课程