题解 | #小乐乐与字符串#

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> int main() { char a[8000]; int b; scanf("%s", a);//把字符串存进a数组里 b=strlen(a);//统计一下输入的数组长度 //思路一 //整体思路就是要找到第一个C，然后找第一个H，再找后面有几个N，然后第一个C，第二个H，后面有几个N，后面同理 //int i, j, k; //long long c=0;//用于统计CHN个数 //for (i = 0; i < b; i++) //{ // if (a[i] == 'C')//找到一个C，就往下找H，找到一个H，就往下找N的个数，然后c++统计总的个数 // { // for (j = i+1; j < b; j++) // { // if (a[j] == 'H') // for (k = j+1; k < b; k++) // { // if(a[k]=='N') // c++; // } // } // } //} //printf("%lld", c); //但是由于此思路循环过多，超过了通过所要求的时间，所以就需要优化一下算法，我看了下别人的思路，只用了一次循环，往下是思路二 //思路二意思是，用三个量统计当前状态。举个例子，假设我们现在已经分别累计统计了a，b，c，个C，CH，CHN。如果往后一个遇见C，那么个数变成a+1，b，c；如果遇见H，那么个数变成a，b+a，c；如果遇见N，则变成a，b，c+b //这个算法的关键在于当前统计的量会结合重新累计之前的C、CH、CHN个数，并且影响出现C，H，N，出现时改变C，H，CHN的个数，方式是累计，可以自己那笔算一组实例感受一下

long C=0, CH=0, CHN=0,i;
for (i = 0; i < b; i++)
{
	if (a[i] == 'C')
	{
		C++;
	}
	else
	{
		if (a[i] == 'H')
			CH = CH + C;
		else
		{
			if (a[i] == 'N')
				CHN = CH + CHN;
		}
	}
}
printf("%ld", CHN);

return 0; }