[笔试训练](三十六)106:提取不重复的整数107:哈夫曼编码108:abb

目录

106:提取不重复的整数

107:哈夫曼编码

 108:abb

106:提取不重复的整数

题目链接:提取不重复的整数_牛客题霸_牛客网 (nowcoder.com)

题目:

​ 题解:

#include <iostream>
#include <string>
using namespace std;
int n=0;
int cnt[10];
int ret=0;
int main() 
{
    cin>>n;
    string nstr=to_string(n);
    for(int i=nstr.size()-1;i>=0;i--)
    {
        int tmp=nstr[i]-'0';
        if(cnt[tmp]==0)
        {
            ret=10*ret+tmp;
        }
        cnt[tmp]++;
    }
    cout<<ret<<endl;

    return 0;
}

107:哈夫曼编码

题目链接:【模板】哈夫曼编码_牛客题霸_牛客网 (nowcoder.com)

题目:

​

 108:abb

题目链接:abb_牛客题霸_牛客网 (nowcoder.com)

 题目:

题解:

线性dp：

#include <iostream>
using namespace std;
typedef long long LL;

const int N=1e5+10;
char s[N];
LL dp[N];
LL f[26];
LL g[26];

LL n;

int main() 
{
    cin>>n>>s;

    LL ret=0;
    for(int i=0;i<n;i++)
    {
        int x=s[i]-'a';
        dp[i]=f[x];
        ret+=dp[i];

        f[x]=f[x]+i-g[x];
        g[x]=g[x]+1;
    }

    cout<<ret<<endl;
    return 0;

}