CodeForces849CFromYtoY

From beginning till end, this message has been waiting to be conveyed.

For a given unordered multiset of n lowercase English letters (“multi” means that a letter may appear more than once), we treat all letters as strings of length 1, and repeat the following operation n - 1 times:

Remove any two elements s and t from the set, and add their concatenation s &＃43; t to the set.
The cost of such operation is defined to be , where f(s, c) denotes the number of times character c appears in string s.

Given a non-negative integer k, construct any valid non-empty set of no more than 100 000 letters, such that the minimum accumulative cost of the whole process is exactly k. It can be shown that a solution always exists.

Input
The first and only line of input contains a non-negative integer k (0 ≤ k ≤ 100 000) — the required minimum cost.

Output
Output a non-empty string of no more than 100 000 lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.

Note that the printed string doesn’t need to be the final concatenated string. It only needs to represent an unordered multiset of letters.

Examples
Input
12
Output
abababab
Input
3
Output
codeforces
Note
For the multiset {‘a’, ‘b’, ‘a’, ‘b’, ‘a’, ‘b’, ‘a’, ‘b’}, one of the ways to complete the process is as follows:

{“ab”, “a”, “b”, “a”, “b”, “a”, “b”}, with a cost of 0;
{“aba”, “b”, “a”, “b”, “a”, “b”}, with a cost of 1;
{“abab”, “a”, “b”, “a”, “b”}, with a cost of 1;
{“abab”, “ab”, “a”, “b”}, with a cost of 0;
{“abab”, “aba”, “b”}, with a cost of 1;
{“abab”, “abab”}, with a cost of 1;
{“abababab”}, with a cost of 8.
The total cost is 12, and it can be proved to be the minimum cost of the process.

题意难读懂的地方在于那个计算

这个公式的意思是
两个子串s和t
c在a到z里面取,每个都取一遍,
s里字母c的数量和t里字母c的数量的积,
把c在a到z里的每一个结果相加

举例:
&＃39;aab’和’abb’代表着s和t
从a到z依次选择c

c &＃61; a时: aab里面有两个a,abb里面有一个a,那么结果就是21 &＃61; 2
c &＃61; b时: aab里面有一个b,abb里面有两个b,那么结果就是12 &＃61; 2
c &＃61; 字符c时: aab和abb里面没有c,结果为0*0 &＃61; 0
其他依次下去都是0
结果为4

然后,观察结果
a 0
aa 1
aaa 3
aaaa 6
aaaaa 10
…
可以看出规律, i*(i-1)/2

如果从另一个字母开始,就重新开始计数

我们需要找到第一个小于k的值的数,然后从那个数开始用另一个字母重新开始计数

#include
using namespace std;
const int MAXN &＃61; 1e4;
int arr[MAXN];
int main(){for(int i&＃61;1;i>k;char temp&＃61;&＃39;a&＃39;;if(k&＃61;&＃61;0) putchar(temp);//特判一下while(k){int cnt&＃61;lower_bound(arr,arr&＃43;MAXN,k)-arr;if(arr[cnt]>k) cnt--;// 找到第一个小于k的值k-&＃61;arr[cnt];cnt&＃43;&＃43;; // 因为序号为0的时候&＃xff0c;是1个awhile(cnt--) putchar(temp);temp&＃43;&＃43;;// 改变字符}return 0;
}


参考:
https://blog.csdn.net/qq_37383726/article/details/78328527?utm_medium&＃61;distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.edu_weight&depth_1-utm_source&＃61;distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.edu_weight