CF1511D-Min Cost String

2022-04-04 题解

题目大意：要求用前k个小写字母（比如：前3个小写字母是abc，前六个小写字母是abcdef）组成一个长度为n的字符串，要求组成的字符串各个长度为2的子串互相相同的个数最少。

这道题比较容易想到需要构造出aabacadaeafag...az+bbcbdbebfbg...bz+…+xxzz这样的串（假设k给定的是26），如果这么一个串不够长就依次重复用。

但想不到怎么实现，查阅了网上的代码，写得非常精妙

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, i, j, k;
    scanf("%d%d", &n, &k);
    string s = "";
    for (i = 0; i < k; i++)
    {
        for (j = i; j < k; j++)
        {
            s += 'a' + i;
            if (i != j)
                s += 'a' + j;
        }
    }
    for (i = 0; i < n; i++)
        printf("%c", s[i % s.size()]);
    return 0;
}