题目描述

给定一个长度为NN的字符串SS 。保证SS 由 “R”， “G”， “B”三种字符组成。
现在问，一共有多少个不同的三元组(i,j,k)(i,j,k)满足下面两个条件：
Si≠Sj,Si≠Sk,Sj≠SkSi≠Sj,Si≠Sk,Sj≠Sk;
j−i≠k−jj−i≠k−j.
三元组还要保证 i<j<ki<j<k

输入格式

第一行一个整数N。
第二行，长度为N的字符串 SS

输出格式

一个整数，表示答案。

样例数据

input_1

4
RRGB

output_1

1

input_2

39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB

output_2

1800

数据规模与约定
50% 数据保证 N≤50
70% 数据保证 N≤1000
100% 数据保证 1≤N≤4000
时间限制：1s
空间限制：256MB

题解：

暴力是一种很不错的思路
枚举每一位，查找到符合条件的组合的数量，代码如下：

#include<bits/stdc++.h>
using namespace std;
long long ans,n;
char a[110000];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	cin>>a[i];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<i;j++)
		{
			if (a[i]==a[j]) continue;	  //一个剪枝，可以保证极限数据不TLE
			for (int k=1;k<j;k++)
			{
				if ((j-i!=k-j and a[i]!=a[j]) and (a[j]!=a[k] and a[i]!=a[k])) ans++; 
			}
		}
	}
	cout<<ans;
	return 0;
}

当你写完暴力算法时，我可以告诉你：暴力时超时的

这里就要一个简单的模型转换：各种字符的个数的乘积就是满足条件1的方案数
再减去不符合条件2的方案的数目就行了，代码如下：

#include<bits/stdc++.h>
using namespace std;
long long x1,x2,x3,n;
char a[11000];
int main()
{
  freopen("rgbtri.in","r",stdin);
  freopen("rgbtri.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		if (a[i]=='G') x1++;
		if (a[i]=='B') x2++;
		if (a[i]=='R') x3++;
	}
	long long ans=x1*x2*x3;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n/2;j++)
		{
		if((a[i]=='R' and a[i+j]=='G' )and a[i+j*2]=='B')	ans--;
		if((a[i]=='R' and a[i+j]=='B' )and a[i+j*2]=='G')	ans--;
		if((a[i]=='G' and a[i+j]=='R' )and a[i+j*2]=='B')	ans--;
		if((a[i]=='G' and a[i+j]=='B' )and a[i+j*2]=='R')	ans--;
		if((a[i]=='B' and a[i+j]=='G' )and a[i+j*2]=='R')	ans--;
		if((a[i]=='B' and a[i+j]=='R' )and a[i+j*2]=='G')	ans--;
		}
	}
	cout<<ans;
	return 0;
}

最后的最后,希望看见此博客的所有older们,以理解为主,不要直接复制代码.