RGB(c++)

问题 D: RGB

题目描述
给你一个长度为N,由R,G,B组成的字符串S。
求有多少组(i,j,k),(0<=i 1.Si != Sj,Si != Sk且Sj != Sk
2.j-i != k-j
输入
N,(1<=N<= 4000)
S
样例输入
4
RRGB
样例输出
1
思路：求出满足条件1.的组数，再减去不满足条件2.，但满足条件1.的组数。
解题：
1.写三个循环，时间复杂度n^3很好理解，但是超时
2.数据越界，改用long long类型
3.成功

#include
using namespace std;

int main()
{
	int n;
	string a;
	cin>>n;
	cin>>a;
	long long r=0,g=0,b=0;
	for(int i=0;i<n;i++){
		if(a[i]=='R') r++;
		else if(a[i]=='G') g++;
		else b++;
	}
	long long res = r*g*b;
	for(int i=0;i<n;i++){
		for(int x=1;;x++){
			//最妙的地方就在这里了。
			//条件二就是i和j跟j和k不能相隔的距离一样
			int j = i+x;
			int k = j+x;
			//k+i = j+x+i = 2*i+2*x
			//2*j = 2*i+2*x
			//k+i = 2*j
			//j-i = k-j
			if(k>=n) break;
			if(a[i]!=a[j]&&a[i]!=a[k]&&a[j]!=a[k]) res--;
		}
	}
	cout<<res<<endl;
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

问题 C: gcd问题

题目描述
gcd也就是最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为gcd（a，b），具体的例
子有，gcd(12,12)=12,gcd(5,1)=1,gcd(4,6)=2。
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
现在，小明遇到了得到了一个正整数K，他想知道的值为多少？

温馨提示：没有思路可以点击这里学习~~

输入
K
1<=K<=200

输出

样例输入
2
样例输出
9
提示
样例解释 gcd(1,1,1)+gcd(1,1,2)+gcd(1,2,1)+gcd(2,1,1)+gcd(1,2,2)+gcd(2,2,1)+gcd(2,1,2)+gcd(2,2,2)=9

#include
using namespace std;

int gcd(int a,int b,int c)
{
	int i;
	//当时忘了辗转相除法是怎么个样子了，直接最暴力解了
	for(int i=min(a,min(b,c));i>=1;i--){
		if(a%i==0&&b%i==0&&c%i==0){
			return i;
		}
	}
	return 1;
}

int main()
{
	int x;
	int sum=0;
	cin>>x;
	for(int i=1;i<=x;i++){
		for(int j=1;j<=x;j++){
			for(int k=1;k<=x;k++){
				sum += gcd(i,j,k);
			}
		}
	}
	cout<<sum;
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30