Educational Codeforces Round 107 (Rated for Div. 2) D. Min Cost String(構造)

題意：

構造一個長度為 n n n字串，只能使用字母表前 k k k 個字母，使得 s i = s j s_i=s_j si?=sj? 并且 s i + 1 = s j + 1 s_{i+1} =s_{j+1} si+1?=sj+1? 的 ( i , j ) (i,j) (i,j) 數量最少，

題解：

當 n n n到達一定長度時，必然會存在上述 ( i , j ) (i,j) (i,j) ，

那么我們先考慮如何利用這 k k k個字母先構造出一個最長的字串，滿足不存在上述 ( i , j ) (i,j) (i,j) ，

其實，每個字母后面最多有 k k k種情況,，比如 k = 4 k=4 k=4, 那么 a a a 就是 a a , a b , a c , a d aa ,ab ,ac ,ad aa,ab,ac,ad ，

將這四種合起來，大致可以分為兩種構造情況：

1. 1. 1. a a b a c a d aabacad aabacad

2. 2. 2. a b a c a d a a abacadaa abacadaa

那么選擇哪一種呢？顯然要第一種，因為第二種后面不管放什么都會出現相等，而第一種后面還能再去構造 b b b

即： a a b a c a d b b c b d aabacadbbcbd aabacadbbcbd ,構造 b b b的時候就不能再把 a a a放進來，以此類推，最后就可以構造出 k ? k k \cdot k k?k 的字串，也就是每個字母都被使用了 k k k次，保證了最長，

最后要構造長度為 n n n 的字串，那么就以這個 k ? k k \cdot k k?k 的字串為回圈節即可，

代碼：

#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
int main() {
    
    int n, k;
    cin >> n >> k;
    string s;
    for(int i = 0; i < k; i++)
    {
        s += 'a' + i;
        for(int j = i + 1; j < k; j++)
        {
            s += 'a' + i;
            s += 'a' + j;
        }
    }
    for(int i = 0; i < n; i += 1) cout << s[i % s.size()];
    return 0;
}