神秘代码:好像忘记专门设签到题了
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题,直接自闭,太膨胀了。

京公网安备 11010502036488号