7-86 有几个ZUCC (25分)

7-86 有几个ZUCC (25分)

字符串 AAZBCZCUCIOCQWC 共包含6个 ZUCC。

输入样例:
AAZBCZCUCIOCQWC

输出样例:
6

思路
该题类似一个数学题。先找到字符串中每个U的位置，统计这个U前面的Z的个数和后面的C的个数，就能计算出该U有几种组合方式了。以类似的方法计算其他U，最后相加最得到最后结果了。

那怎么根据Z的个数和C的个数计算呢？
分析知：U前面有几个Z，即最后在原有的组合个数乘以几。
U后面有几个Z，即高中学过的排列组合问题，从n个数中选取两个C的排列组合，如后面有3个C，则CC的组合就有3种。解释如图：

代码如下:

#include<bits/stdc++.h>
using namespace std;
long long  u[100009]; //统计每个U前面的Z的个数 

int main()
{
	long long c=0,z=0;
	long long sum=0;
	string s;
	cin >> s;
	for(int i=0; i<s.size(); i++){
		if(s[i] == 'Z'){
			z++;
		}else if(s[i] == 'U'){
			u[i] = z; //统计U[i]前面Z的个数 
		}
	} 
	for(int i=s.size()-1; i>=0; i--){
		if(s[i] == 'C'){
			c++;
		}else if(s[i] == 'U'){
			sum += u[i] * (c*(c-1)/2);  //根据Z和C的个数，计算该U可以组合的情况个数，并累加 
		}
	}
	cout << sum;
	return 0;
}

欢迎大家批评改正，积极讨论，让我们共同进步，加油！！！