「题解」洛谷 P7993 [USACO21DEC] Lonely Photo B
我们完全没有必要一开始就去思考正解。
根据题意，我们可以将题目抽象成一个模型：
在一个长度为 \(n\) 的字符串中的每个长度 不小于三 的子串中，统计 只有一个 G 字符 或 只有一个 H 字符 的字串数量。
我们可以先尝试使用暴力方法解决问题。
我们从 长度为三 的子串枚举到 长度为 \(n\) 的子串，
再枚举每个子串的 起点和终点，
最后统计这个子串中，字符 G 和字符 H 的数量。
时间复杂度为 \(O(n^3)\)。
#include
#define int long long
using namespace std;
int n,ans=0;
char s[500005];
signed main()
{
scanf("%lld%s",&n,s+1);
for(int i=3;i<=n;i++)
{
for(int j=1;j<=n-i+1;j++)
{
int G=0,H=0;
for(int k=j;k 提交记录
这种方法可以拿到 36分。
\(O(n^3)\) 级别的复杂度显然无法通过。
但是，我们统计的某个字串中的字符数量，本质上其实是 区间求和。
于是，我们可以用 前缀和 将复杂度优化到 \(O(n^2)\)。
#include
#define int long long
using namespace std;
int n,ans=0,sumG[500005],sumH[500005];
char s[500005];
signed main()
{
scanf("%lld%s",&n,s+1);
sumG[1]=(s[1]=='G'?1:0);
sumH[1]=(s[1]=='H'?1:0);
for(int i=2;i<=n;i++)
{
sumG[i]=sumG[i-1];
sumH[i]=sumH[i-1];
if(s[i]=='G')
++sumG[i];
else if(s[i]=='H')
++sumH[i];
}
for(int i=3;i<=n;i++)
{
for(int j=1;j<=n-i+1;j++)
{
int totG=sumG[j+i-1]-sumG[j-1],totH=sumH[j+i-1]-sumH[j-1];
if(totG==1||totH==1)
++ans;
}
}
printf("%lld",ans);
return 0;
}
提交记录
可以看到，运行速度有了显著提升，我们可以拿到 90分。
正解：
为了能通过这一题，我们的时间复杂度至少要降到 \(O(n\log n)\)。
不过，我们可以用 \(O(n)\) 级别的时间复杂度解决这个问题。
对于每个字符，我们可以计算 该字符数量 是 奇数 的照片数量。
在该字符是 G 的情况下，子串的 一侧至少有两个字符 H 或 两侧都至少有一个字符 H，并且不出现字符 G。我们可以直接 向左和向右 计算不匹配字符的数量，并考虑这两种情况。
#include
#define int long long
using namespace std;
int n,ans=0;
string s;
signed main()
{
cin>>n>>s;
for(int i=0;i0&&s[i-1]!=s[i])
{
++l;
for(int k=i-2;k>=0&&s[k]==s[i-1];k--)
++l;
}
int r=0;
if(i+1 提交记录