F. Min Cost String Problem solving report

Topic link

label ： character string structure

subject

The question ：

Give constant n,k, Let's use before k Lowercase letters are constructed with a length of n String
Letters can be in front k Any use or no use within the scope , But it is required to minimize the index pairs in the output string
When s[i]=s[j] And is s[i+1]=s[j+1] (1≤i<j<|s|) It constitutes an index pair

Their thinking ：

To minimize index pairs , We can divide the string into one-to-one pairs ,
such as s=aaba At this time, we see three pairs aa ab ba It has been taken
Then the next idea is to list all Character pair Add to s in
If the string length is greater than or equal to n Before output n Characters
If the length of the character string is less than n
Because all the character pairs that can be formed are already in s It's in No matter what you add, there will be index pairs
We let s += s Until the length is greater than n Before interception n Character output

resize Function usage

When n The length is less than the string s The length of s.resize(n), Intercept s front n Characters
When n The length is greater than the string s The length of char a; s.resize(n,a), stay s Add characters after a until s Length up to n

Code implementation

#include <iostream>
#include <string>
using namespace std;

int main(){
	long long 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;
		}
	}
	while(s.size()<n)s+=s;
	s.resize(n);
	cout<<s<<endl;
}