本文主要是介绍小花梨的字符串--美登杯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
小花梨有一个长度为n且只包含小写字母的字符串。现在对其进行q次询问。
每次询问字符串的一段区间[l,r],从[l,r]区间内的所有子串中最多可以选出多少个字符串,
使得选出来的这些字符串存在一种排列方式满足相邻的两个字符串a,b的最长公共后缀长度
大于等于min( strlen(a),strlen(b) )-1。
Input
第一行输入两个正整数n和q,分别表示字符串长度和询问次数。
第二行为长度为n的字符串。接下来q行,每行两个正整数l,r表示询问的区间。
(1 ≤ n ≤ 10000,1 ≤ q ≤ 10000,1 ≤ l ≤ r ≤ n)
Output
输出q行,第 i 行输出第 i 次询问的答案
Note
[1,1]内有1个子串:a,存在排列a满足要求,长度为1
[1,2]内有3个子串:a,b,ab,存在排列a,ab,b满足要求,长度为3
[1,3]内有6个子串:a,b,c,ab,bc,abc,存在排列ab,b,c,bc,abc,a满足要求,长度为6
分析
这个题用一个等差数列前n项和公式就可以了,对应每个区间的字符串,其所有子串都能用到,组成一个序列满足题目要求。具体原理我也不知道,只是在做题的时候看了上面的note,发现了这个规律,一交,A了。。。
代码
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll cal(ll l,ll r)
{ll len=r-l+1;return len*(1+len)/2;
}
int main()
{int n,q;char s[10005];scanf("%d%d",&n,&q);scanf("%s",s);for(int i=0;i<q;i++){ll l,r;scanf("%lld%lld",&l,&r);ll ans=cal(l,r);printf("%lld\n",ans);}return 0;
}
这篇关于小花梨的字符串--美登杯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!