P10233 [yLCPC2024] A. dx 分计算 题解

题目大意：

题目传送门

共 \(T\) 组测试数据，每组数据给定一个字符串 \(s\) 和 \(Q\) 次询问，按照特定的赋值方式，每次询问 \(l\) 到 \(r\) 间按这样的赋值方式的总和是多少。

赋值方式如下：

• P 可得3分
• p 可得2分
• G 可得1分
• 其余字符不得分

题目分析：

前置知识：前缀和。（没有学过的可以先完成这题再回来做本题）

考虑数据范围，\(1 \leq \sum{|s|} \leq 10^7,1 \leq \sum{Q} \leq 10^4,1 \leq l \leq r \leq |s|\)，发现 \(\sum{|s|}\) 可高达 \(10^7\)，暴力的总时间复杂度为 \(O(T \times |s| \times {Q})\)，故暴力求和不可，考虑优化。

由题意发现没有强制性在线询问，故可以考虑离线询问。用前缀和提前计算出前 \(i\) 个数的总和，每次询问 \(l\) 到 \(r\)，记答案为 \(ans\)，前缀和数组为 \(sum\)，则：

故时间复杂度为 \(O(\sum |s|+\sum Q)\)。

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int T,sum[N],Q,len;
string s;
signed main()
{
	scanf("%d",&T);
	while(T--)
	{
		cin>>s;
		scanf("%d",&Q);
		len=s.size();
		//for(int i=1;i<=len;i++) sum[i]=0; 
		//这里因为前缀和的计算会直接覆盖上次的值故可以不用清零 
		for(int i=1;i<=len;i++)
		{
			//前缀和依题意赋值 
			sum[i]=sum[i-1];
			if(s[i-1]=='P') sum[i]+=3;
			if(s[i-1]=='p') sum[i]+=2;
			if(s[i-1]=='G') sum[i]++;
		}
		while(Q--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",sum[y]-sum[x-1]);//询问 O(1) 求出答案 
		}
	}
	return 0;
}