题目描述

让我们将字符串S的代价定义为索引对i和j（1≤i<j <|s|）的数量，以使S$[i]$ = S$[j]$和S$[i+1]$ = S$[j+1]$。

给出两个正整数n和k。 在所有长度为n且仅包含拉丁字母的前k个字符的字符串中，找到可能成本最低的字符串。 如果有多个此类字符串且成本最低，请找到它们中的任何一个。

样例

9 4
aabacadbb
5 1
aaaaa

算法1

(构造) $O(n)$

首先我们可先找到代价为0的子串排列方式,然后根据长度均摊一下就好了!!
以样例1为例子

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
char e[N*2];
int idx,n,k;;
void solve()
{
    for(int i=0;i<k;i++)
    {
        e[++idx]='a'+i;
        for(int j=i+1;j<k;j++)
        {
            e[++idx]='a'+i;
            e[++idx]='a'+j;
        }
    }
    int len=idx;
    idx=1;
    for(int i=1;i<=n;i++)
    {
        printf("%c",e[idx++]);
        if(idx>len) idx=1;
    }

}
int main()
{
    scanf("%d%d", &n, &k);
    solve();
    return 0;
}