HeinzHuang

Eudaimonia

0%

IdealString（Topcoder 9757）

Posted on Edited on In

题目描述：

一个理想字符串的定义是每个字符第一个出现的位置编号就是等于这个字符出现的次数，比如 ABOOOB就是一个理想字符串(A第一次出现的位置是1，一共有一个1，O最早出现的位置是3，一共有三个O,B第一次出现的位置为2，一共有2个B)。给定长度length，返回字典序最小的理想字符串，如果没有，则返回空串

输入

一个长度length,length<=100

输出

输出该字符串

思路：

题意分析

这题只要把题意稍微转化一下就会变得比较简单：若在 \(p\)位置放一个字符，那么就会出现\(p\)个相同的字符，那么若所有的字符第一次出现的位置为\([p1,p2..pm]\),那么必定满足\(p1+p2+..+pm\)等于\(length\)，有因为length的范围比较小那么可以考虑直接深搜。

深搜策略

说策略，其实也没啥策略，因为范围实在太小啦，注意的就是每次放下一个新的字符的位置是有范围的，不能超过上一个位置的两倍，也不能超过\(length\)的一半，否则都不符合条件，具体原因自行思考,又由于字符串的字典序要最小所以每次放新的字符位置要尽可能远（当然先放A，再放B…）。
当最后得到每个第一位置后，最后就是组成字符串了，这个其实用一个队列就ok了，比较简单。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <queue>
#include <ctime>
#define FOR(i,l,r) for(int i=(int)l;i<=(int)r;i++)
#define DOR(i,r,l) for(int i=(int)r;i>=(int)l;i--)
#define loop(i,n) for(int i=0;i<(int)n;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define sf scanf
#define pf printf
#define N 105
using namespace std;
typedef long long ll;
queue<char>Q;
int a[N],len,found=0,L;
char s[N];
string ans;
void dfs(int sum,int x,int cnt){//剩余字符数量，上一个位置，用了几个字符 
//	printf("sum:%d x:%d cnt:%d\n",sum,x,cnt);
	if(sum<0)return;
	else if(sum==0){
		FOR(i,1,cnt){
			FOR(j,1,a[i]-1)Q.push(i+'A'-1); 
			s[a[i]-1]=i+'A'-1;//放第一个位置 
		}
		loop(i,L)if(!s[i])s[i]=Q.front(),Q.pop();//用队列组成字符串 
		found=1;
		return;
	}
	DOR(i,min(sum,min(x+x==0?1:x+x,(L+1)>>1)),x+1){//枚举下一个字符的位置，由于要尽可能远所以倒着枚举 
		a[cnt+1]=i;//记录第一个位置 
		dfs(sum-i,i,cnt+1);
		a[cnt+1]=0;
		if(found)return;
	}
}
class IdealString {
public:
	string construct(int length) {
		L=length,mms(s,0),ans.clear();
		found=0,len=0;
		dfs(L,0,0);
		if(found)ans=s;
		else puts("");
		return ans;
	}
};