首页 > 试题广场 >

小乐乐与字符串

[编程题]小乐乐与字符串

热度指数：12501 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在庆祝祖国母亲70华诞之际，老师给小乐乐出了一个问题。大家都知道China的英文缩写是CHN，那么给你一个字符串s，你需要做的是统计s中子序列“CHN”的个数。

子序列的定义：存在任意下标a < b < c，那么“s[a]s[b]s[c]”就构成s的一个子序列。如“ABC”的子序列有“A”、“B”、“C”、“AB”、“AC”、“BC”、“ABC”。

输入描述:

输入只包含大写字母的字符串s。(1 ≤ length ≤ 8000)

输出描述:

输出一个整数，为字符串s中子序列“CHN”的数量。

示例1

输入

CCHNCHN

输出

示例2

输入

CCHNCHNCHNCHN

输出

算法知识视频讲解

梦想还是要有的丶

计数变量记得long类型，int对于一些用例不够大

#include<iostream>
using namespace std;

int main()
{
    long c=0,h=0,n=0;
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='C')
            c++;
        else if(s[i]=='H')
            h+=c;
        else if(s[i]=='N')
            n+=h;
    }
    cout<<n<<endl;
    return 0;
}

发表于 2020-07-27 21:53:43 回复(0)

仰望那片深邃

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    long int count = 0;
    long int c = 0, h = 0;
    
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == 'C')
            ++c;
        else if (s[i] == 'H')
            h += c;
        else if (s[i] == 'N')
            count += h;
    }
    
    cout << count << endl;
    return 0;
}

编辑于 2020-03-28 13:28:40 回复(0)

椒

致力于写最烂的代码

import java.util.Scanner;
public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int i = 0;
        int j = 0;
        int k = 0;
        char[] ss = s.toCharArray();
        int len = s.length();
        int to=0;
        for (;i<len;i++){
            for (j=i+1;j<len;j++){
                for (k=j+1;k<len;k++){
                    if(ss[i]=='C'&&ss[j]=='H'&&ss[k]=='N')
                        to ++;
                }
            }
        }

        System.out.println(to);
    }
}

发表于 2020-10-18 16:32:24 回复(4)

LeslieYoung

/*统计字符串CCHNCHN 的子串CHN的个数*/
#include<cstdio>
(802)#include<cstring>
const int maxn = 100010;
const int mod = 1000000007;
char str[maxn];          //字符串
int leftNumC[maxn] = {0};   //每一位左边含有p的个数
int main()
{
	gets(str);
	int len = strlen(str);
	for(int i = 0; i<len; i++)
	{
		if(i>0)
		{
			leftNumC[i] = leftNumC[i-1];
		}
		if(str[i] == 'C')
		{
			leftNumC[i]++;      //当前为是C，则C的个数增加1 
		}
	}
	int ans = 0, rightNumN = 0;    //ans为答案，rightNumT记录右边N的个数 
	for(int i = len-1; i>=0; i--)
	{
		if(str[i] == 'N')
		{
			rightNumN++;
		}else if(str[i] == 'H')
		{
			ans = (ans + leftNumC[i] * rightNumN)%mod; 
		}
	 } 
	 printf("%d\n",ans);
	 return 0;
 }

发表于 2020-03-29 20:53:54 回复(0)

C/C++

wydxry

#include <stdio.h>
(737)#include <string.h>
int main()
{
    char str[8005];
    gets(str);
    long long i,cnt_c=0,cnt_h=0,cnt_n=0;
    for(i=0;str[i]!='\0';i++){
        if(str[i]=='C') cnt_c++;
        else if(str[i]=='H') cnt_h+=cnt_c;
        else if(str[i]=='N') cnt_n+=cnt_h;
        //printf("%c",str[i]);
    }
    printf("%lld\n",cnt_n);
}

发表于 2020-04-10 23:17:00 回复(2)

60万毕业生80万offer优势在我

为什么示例1是7个？？难道还能跳着数？？

发表于 2021-01-31 11:30:42 回复(5)

Python

玖拾肆

s=input()
x=0
y=0
z=0
for i in range(len(s)):      #循环判断元素
        if s[i]=="C":        #如果第一个符合C
            x=x+1
        elif s[i]=="H":      #遇到H的话就组成CH此时有C个"CH”序列
            y=x+y
        elif s[i]=="N":      #找到“N”的时候,就是“CH“还有"N组成的“CHN”
            z=z+y
print(z)

发表于 2020-09-08 16:09:45 回复(0)

CodeGeek

子串和子序列都整不明白？？？？

发表于 2021-12-03 10:12:28 回复(1)

泪痕梦雪

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
    int main()
    {
        char a[8000];
        gets(a);
        long int c = 0, h = 0, n = 0;
       
        for (int i = 0; i <= strlen(a); i++)
        {
            if (a[i] == 'C')
            {
                c++;
            }
            else if (a[i] == 'H')
            {
                h += c;
            }
            else if (a[i] == 'N')
            {
                n += h;
            }
        }
        printf("%ld", n);


        return 0;
    }

发表于 2021-07-11 11:14:05 回复(0)

不懂《算法》的《小白》

这是什么题目，我感觉我语文水平不过关了

CCHNCHN

C：3个

H：2个

N：2个

CH：2个

HN：2个

CHN：2个

共计13个，怎么答案7个，求理解

发表于 2022-02-06 14:08:05 回复(4)

牛客909538634号

#include <stdio.h>

#include<string.h>

int main() {

char a[8000];

int i, j, n, k, count = 0;

n = strlen(a);

scanf("%s", a);

for (i = 0; i < n; i++)

{

if (a[i] == 'C')

for (j = i; j < n; j++)

{

if (a[j] == 'H')

{

for (k = j; k < n; k++)

{

if (a[k] == 'N')

count++;

}

这个有什么问题，在别的地方就可以啊

printf("%d", count);

return 0;

}

编辑于 2023-12-12 15:56:40 回复(0)

Powercs12

我笑了，弄了半天又农回来发现是对的

错了这么多次又对了

最后试了几次都是对的

无语了

花了2个小时

#include<stdio.h>
#include<string.h>
int main(void)
{
    char ch[8001] = { 0 };
    gets(ch);
    int i = 0;
    int j = 0;
    int k = 0;
    int len = strlen(ch);
    unsigned long int sum1 = 0;
    unsigned long int sum2 = 0;
    int flag1 = 10000;
    int flag2 = 10000;
    int ret = 0;
    for (i = 0; i < len; ++i)
    {
        if (ch[i] == 'C')
        {
            sum2 = 0;
            for (j = i + 1; j < len; ++j)
            {
                if (ch[j] == 'H')
                {
                    ret = 0;
                    for (k = j + 1; k < len; ++k)
                    {
                        if (ch[k] == 'N')
                        {
                            ++ret;
                        }
                    }
                    ++j;
                    sum2 += ret;
                    while (ch[j] == 'H')
                    {
                        sum2 += ret;
                        ++j;
                    }
                }
            }
            sum1 += sum2;
            ++i;
            while (ch[i] == 'C')
            {
                sum1 += sum2;
                ++i;
            }
        }

    }
    printf("%u\n", sum1);
    return 0;
}

发表于 2022-02-28 20:59:47 回复(0)

牛客462485885号

这样算超时，有没有好一点的算法

#include<stdio.h>

#include<string.h>
int main(){
    char str[8000];
    scanf("%s",&str);
    long int i,j,k;
    long long int num=0;
    long long int size=strlen(str);
    for(i=0;i<size;i++){
        if(str[i]=='C'){
            for(j=i;j<size;j++){
                if(str[j]=='H'){
                    for(k=j;k<size;k++){
                        if(str[k]=='N'){
                            num++;
                        }
                    }
                }
            }
        }
    }
    printf("%lld",num);
}

发表于 2022-01-05 20:26:17 回复(1)

阿金要努力

#include<stdio.h>
int main()
{
    long long c=0,ch=0,chn=0;
    char s[8000]={0};
    scanf("%s",s);
    char*p=s;
    while(*p)
    {
        if(*p=='C')
        {
            c++;
        }
        else if(*p=='H')
        {
            ch+=c;
        }
        else if(*p=='N')
        {
            chn+=ch;
        }
        p++;
    }
    printf("%lld",chn);
    return 0;
}

发表于 2022-01-03 17:51:57 回复(0)

乐意999

#include<stdio.h>
int main(){
    char arr[8001];
    scanf("%s",arr);
    unsigned long long c=0;
    unsigned long long h=0;
    unsigned long long chn=0;
    for(char *p=arr;*p;p++){
        if(*p=='C')
            c++;
        if(*p=='H')
            h+=c;
        if(*p=='N')
            chn+=h;
        }
    printf("%u",chn);
    return 0;
}

发表于 2021-12-08 17:49:06 回复(0)

牛客856864169号

#include<stdio.h>
#include<string.h>

int main(){
    char str[9000];
    scanf("%s\n",str);
    char* p=str;
    long long count1=0;
    long long count2=0;
    long long count3=0;
    while(*p){
        if(*p=='C') count1++;
        else if(*p=='H') count2+=count1;
        else if(*p=='N') count3+=count2;
        p++;
    }
    printf("%lld\n",count3);
    return 0;
    
}

这个代码是不是有问题呀，如果最后一个字符输出的不是N,输出的结果和预想的结果是不一样的吧。

发表于 2021-09-25 01:58:47 回复(0)

Python3

左空一

s = input()
a = 0
b = 0
c = 0
for i in range(len(s)):
    if s[i] == 'C':    # 如果第一个符合
        a += 1
    elif s[i] == 'H':    # 遇到H的话就组成CH，此时有C个”CH“序列
        b = a + b
    elif s[i] == 'N':    # 找到“N”的时候，就是“CH”还有“N组成的CHN”
        c = b + c
print(c)

发表于 2021-09-02 10:12:58 回复(0)

Python

Pukino

s=input()
x,y,z = 0,0,0
for i in range(len(s)):
    if s[i]=="C":
        x+=1
    elif s[i]=="H":
        y+=x
    elif s[i]=="N":
        z+=y
print(z)

发表于 2021-07-01 01:33:08 回复(0)

qhebcbx

#include <stdio.h>

int main(){
    char s[8001];
    scanf("%s",s);
    int chns[8000][2],chnsIndex=0,chnsLength;
    int tempCount=0;
    char *sp = s;
    while(*sp != '\0'){
        if(*sp =='C'){
            tempCount++;
        }else if (*sp =='H'){
            chns[chnsIndex++][0]=tempCount;
        }
        sp++;
    }

    tempCount=0;
    chnsLength=chnsIndex;
    chnsIndex--;

    while(sp != s){
        if(*sp =='N'){
            tempCount++;
        }else if (*sp =='H'){
            chns[chnsIndex--][1]=tempCount;
        }
        sp--;
    }
    int i ;
    long total=0;
    for (i=0;i<chnsLength;i++){
        total+= chns[i][0] *chns[i][1];
    }
    printf("%ld\n",total);
    return 0;
}

发表于 2021-06-11 16:56:01 回复(0)

磨洋工程师

import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        long C=0,CH=0,CHN=0;
        for(int i = 0;i<s.length();i++)
        {
            if(s.charAt(i) == 'C')
                C++;
            else if(s.charAt(i) == 'H')
                CH+=C;
            else if(s.charAt(i) == 'N')
                CHN+=CH;
        }
        System.out.println(CHN);
    }
}

发表于 2021-03-30 20:30:21 回复(0)