abb

[编程题]abb

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

leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：

字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。

输入描述:

第一行一个正整数 
第二行一个长度为  的字符串（只包含小写字母）

输出描述:

"abb" 型的子序列个数。

示例1

输入

6
abcbcc

输出

说明

共有1个abb，3个acc，4个bcc

示例2

输入

4
abbb

输出

算法知识视频讲解

cs小白_

#include <stdio.h>

int main() {
    int n;
    scanf("%d",&n);
    char c[n];
    getchar();
    scanf("%s",c);
    int sum[n+1][26];
    for (int i=0; i<n+1; i++) {
        for (int j=0; j<26; j++) {
             sum[i][j]=0;
           }
    }
    // for (int i=0; i<n; i++) {
    //     for (int j=i; j<n; j++) {
    //          sum[i][c[j]-'a']++;
    //        }
    // }
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][c[i]-'a']++;
    }
    long long r=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<26; j++) {
             if (j!=(c[i]-'a')) {
                    r+=(sum[i][j]*(sum[i][j]-1)/2);
             }
           }
    }
   
        printf("%lld", r);
    
    return 0;
}

#include <stdio.h>

int main() {
    int n;
    scanf("%d",&n);
    char c[n];
    getchar();
    scanf("%s",c);
    int sum[n+1][26];
    for (int i=0; i<n+1; i++) {
        for (int j=0; j<26; j++) {
             sum[i][j]=0;
           }
    }
    // for (int i=0; i<n; i++) {
    //     for (int j=i; j<n; j++) {
    //          sum[i][c[j]-'a']++;
    //        }
    // }
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][c[i]-'a']++;
    }
    long long r=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<26; j++) {
             if (j!=(c[i]-'a')) {
                    r+=(sum[i][j]*(sum[i][j]-1)/2);
             }
           }
    }
   
        printf("%lld", r);
    
    return 0;
}

发表于 2024-12-01 14:30:31 回复(0)