题目翻译
有一个长度为 $n$，且只由 $\tt R,\tt G,\tt B$ 组成的字符串 $s$，求有多少个三元组 $(i,j,k)$ 满足：
- $1\leq i<j<k\leq n$。
- $s_i\neq s_j,s_j\neq s_k,s_i\neq s_k$。
- $j-i\neq k-j$。
$1\leq n \leq 4,000$。
题目思路
暴力枚举 $i,j,k$，但是 $\mathcal O(n^3)$ 超时。
考虑优化，我们枚举 $i,k$，可以通过前缀和预处理出这一段中 $s_j\neq s_i,s_j\neq s_k$ 的个数。
然后考虑性质 $j-i\neq k-j$，不难发现对于每一对 $(i,k)$，最多只有 $1$ 个 $j$ 使得 $j-i=k-j$，而且这个 $j=\frac{i+k}{2}$。
那么我们特判这一个特殊的 $j$ 即可。
时间复杂度 $\mathcal O(n^2)$，可以通过。
完整代码
代码
#include<bits/stdc++.h>
using namespace std;
int id(char c){if(c=='R')return 0;if(c=='G')return 1;return 2;}
int h[3][4020];
int n;
string s;
long long ans;
int main()
{
cin>>n>>s;
s=' '+s;
for(int i=1;i<=n;i++)
{
for(int j=0;j<3;j++)h[j][i]=h[j][i-1];
h[id(s[i])][i]++;
}
for(int i=1;i<=n;i++)
{
for(int k=i+1;k<=n;k++)
{
if(s[i]==s[k])continue;
int x=3-id(s[i])-id(s[k]);
int tmp=h[x][k]-h[x][i-1];
ans+=tmp;
if(!(k+i&1)&&id(s[k+i>>1])==x)ans--;
}
}
cout<<ans<<endl;
return 0;
}