第十一届蓝桥杯c++B组第二场第八题

下标从1开始输入的两种方法:
1.定义一个char x[N]数组,scanf(“%s”,x+1)或者cin>>x+1
2.从s[0]输入完string后,s = ‘ ‘+s;(可以在前面插入任意一个字符)

方法一:暴力枚举(可以过6/10个数据)

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100010;

int res;
string s;
bool st[30];

int main()
{
    cin>>s;
    for(int i = 0;s[i];i++)
    {
        memset(st,0,sizeof st);
        int t = s[i] - 'a';
        st[t] = true;
        int cnt = 1;
        res+=cnt;
        for(int j = i - 1;j >= 0;j--)
        {
            int t = s[j] - 'a';
            if(!st[t])
            {
                cnt++;
                st[t] = true;
            }
            res += cnt;
        }
    }

    cout<<res;
    return 0;
}

方法二:dp

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

LL res;
string s;
int st[26],f[N];

int main()
{
    cin>>s;
    s = ' '+s;          //防止f[i-1]在i = 0时数组越界
    for(int i = 0;s[i];++i)
    {
        int t = s[i] - 'a';
        f[i] = f[i-1] + i - st[t];
        st[t] = i;
        res += f[i];
    }

    cout<<res;
    return 0;
}