作者：mobiledu2502911073 | 来源：互联网 | 2024-10-29 16:58
原题链接：http://codeforces.com/problemset/problem/848/A。题目要求我们构建一个特定的字符串。具体操作为：从给定字符串中选取若干部分，将其分割成两段，然后进行重新组合。本文将深入探讨该问题的解法，分析其背后的算法逻辑，并提供高效的实现方法。
原题链接：http://codeforces.com/problemset/problem/848/A
题意：让我们构造一个字符串。这里有一种操作：取走这个字符串的若干部分，分成两部分，然后将这两部分的合并插回字符串中，进行过处理的字符串部分不能再次被单独取出，只能整体取出，直到无法操作后停止。每次这种操作后，消耗
, f(s,c)是c字符在s字符串重复的次数。
让我们输出：若干次操作后最小值恰好为k的字符串，不用考虑字符的顺序。
思路：最好怎么简单怎么做。如果我们让字符串中只有一种字符，显然通过一个一个字符加到字符串的方法可以得到最小值（n-1）*n/2，n是构造出的字符串长度。那么，如果字符串有两种字符，我们可以先构造出两段不同字符的字符串，然后合并，由于合并时没有公共的字符，合并不会使结果变化，此时的最小值为两个n*(n-1)/2相加，以此类推到26种字符的情况。
经过一些例子的检验，发现这种方法是对的。
构造结束后似乎不太可能完全用上26个字母，那么先在答案加上单个字符，防止0的特殊情况。
AC代码：
1 #include
2 #include<string>
3 #include
4 using namespace std;
5 char ch[27];
6 int val[5000],t;
7 int res[5000];
8 void init()
9 {
10 val[1]=0;
11 int i;
12 for(i=0;i<26;i++) ch[i]=(char)(i+'a');
13 for(i=2;val[i-1]<=100000;i++){
14 val[i]=val[i-1]+i-1;
15 }
16 t=i;
17 return ;
18 }
19 int main()
20 {
21 int n;
22 init();
23 //cout<
24 while(cin>>n){
25 memset(res, 0, sizeof(res));
26 int num=0;
27 res[num++]=1;
28 for(int i=t-1;i>0;i--){
29 if(n==0) break;
30 while(n>=val[i]){
31 //cout<<'*'<
32 n-=val[i];
33 res[num++]=i;
34 }
35 }
36 string str="";
37 for(int i=0;i){
38 str=str+string(res[i], ch[i]);
39 }
40 cout<endl;
41 }
42 return 0;
43 }
京公网安备 11010802041100号