D. Min Cost String——（构造）Educational Codeforces Round 107 (Rated for Div. 2)

D. Min Cost String
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s define the cost of a string s as the number of index pairs i and j (1≤i<j<|s|) such that si=sj and si+1=sj+1.

You are given two positive integers n and k. Among all strings with length n that contain only the first k characters of the Latin alphabet, find a string with minimum possible cost. If there are multiple such strings with minimum cost — find any of them.

Input
The only line contains two integers n and k (1≤n≤2⋅105;1≤k≤26).

Output
Print the string s such that it consists of n characters, each its character is one of the k first Latin letters, and it has the minimum possible cost among all these strings. If there are multiple such strings — print any of them.

Examples
inputCopy
9 4
outputCopy
aabacadbb
inputCopy
5 1
outputCopy
aaaaa
inputCopy
10 26
outputCopy
codeforces

在解决分析问题的时候，要学会抓住重点：B题是利用10^n作为最大公倍数进行构造，十分巧妙。本题则是：当串长过长时，造成花费是不可避免的。由于花费的定义是连续连个字符相等，所以专注于组合不同的、长度为2的字符串。答案时使用欧拉回路进行构造（图中边的定义恰好和花费一致），这里可以直接按照aabacadbbcbd…的顺序构造（其实更像图中的每条边只取一次，每个顶点只取一次），然后循环。

#include <vector>
#include <cstdio>
using namespace std;

int n, k;
int cur[26];
vector<int> path;

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < k; i++)
	{
		path.push_back(i);
		for (int j = i + 1; j < k; j++)
		{
			path.push_back(i);
			path.push_back(j);
		}
	}

	for (int i = 0; i < n; i++)
		printf("%c", path[i % path.size()] + 'a');
	return 0;
}