苏州大学2020 ICPC集训队个人排位赛（1）

神秘代码：好像忘记专门设签到题了
B：https://codeforces.com/problemset/problem/510/B
C：https://codeforces.com/problemset/problem/1183/H
参考博客：https://blog.csdn.net/slark_/article/details/100713998
题意：给你一个字符串s，又给你一个数n，要你用s的子串填满一个数量为n的集合，对于每个子串，它和原来的串s相比，少了几个字符它就要付出多少代价（删去一个字符需要花费1个代价）。问你填满集合时代价最小是多少，如果填不满，输出-1。
思路：我们看数据范围，可以猜到是dp,那么具体的dp怎么写呢？我们想，对于每个位置，我们记录以这个位置上的字符为结尾的子串，也就是定义dp[i][len]为以第i个字母为子串最后一个字符，长度为len的子串有多少个。那么dp[i][len] += dp[前i-1个字符中最后的'a'-'z'][len-1]。
对于前i-1个字符中最后的'a'-'z'，用一个数组来记录每个位置上其前面的'a'-'z'的位置。
然后我们开始按长度贪心，每个长度都是以'a'-'z'结尾的子串的数量的和。

//author CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
char s[105];//原来的串
ll n,k;
int last[105][26]={0};//last 记录当前位置下，在其前面的最近的'a'-'z'，没有的话就是-1
ll dp[105][105]={0};//dp[i][len]为以第i个字母为子串最后一个字符，长度为len的子串有多少个。
int main()
{
        ios::sync_with_stdio(false);
    memset(last,-1,sizeof(last));
    memset(dp,0,sizeof(dp));
    scanf("%lld %lld ",&n,&k);

    scanf("%s",s);
    //先来计算last
    last[0][s[0]-'a']=0;//第一个字符特殊处理掉，你要是从1计数，这里就可以省去了
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<26;j++)
        {
            last[i][j]=last[i-1][j];//从前面接收来
        }
        last[i][s[i]-'a']=i;//修改当前位置上对应的字符
    }

    for(int i=0;i<n;i++)
    {
        dp[i][1]=1;//每个字符长度为一的子串就是自己 
    } 
    for (int i=2;i<n;i++)//i 是长度 
    {
        for (int j=1;j<n;j++)//j是坐标 
        {
            for(int k=0;k<26;k++)
            {
                if(last[j-1][k]!=-1)//前面有这个字符，没有就算了
                {
                    dp[j][i]+=dp[last[j-1][k]][i-1];
                }
            }
        } 
    }

    ll ans=0;
    k--;//原始串，不要代价 
    //接下来是个贪心的过程
    for(int i=n-1;i>=1;i--)//肯定是从n-1开始贪
    {
        ll cnt = 0;//有多少长度为i的子串 
        for(int j=0;j<26;j++)
        {
            if(last[n-1][j]!=-1)//如果这个字符存在，就把以它结尾的长度为i的子串数量加进来
                cnt+=dp[last[n-1][j]][i];    
        } 
        if(cnt>k)
        {
            ans+=(n-i)*k;
            k = 0;
            break;
        }
        else
        {
            ans+=(n-i)*cnt;
            k-=cnt;
        }

    } 

    if(k==1)//如果最后k还有，恰好有一个，那就是把空串""加进来
    {
        ans+=n;
        k--;
    }
    if(k==0)
        printf("%lld\n", ans);
    else//所有情况都出来了，真没串了
        printf("-1\n");
     return 0;
}

写在最后：
比赛的时候，看了眼C题，觉得能做，想到了组合数，结果写了半天(样例最后一个就是过不去)，WA了。出来一看H题，直接自闭，太膨胀了。