Codeforces 37 C Old Berland Language

题意

构造出指定长度的n个01字串，每个字串不能是其他字串的子串

算法：用DFS模拟

“不能是其他字串的子串”用哈夫曼编码方式编的字串符合这个规则，且会“最短”，本题无需最短，只需满足前一个条件即可。
哈夫曼编码需要构造哈夫曼树（不过此题不需要构造树），然后对哈夫曼树的所有指向左子树的边编码为0，右为1，以此解决“不能是其他字串的子串”问题
因此我们本题可以假设哈夫曼树已经构造完毕，然后用dfs去寻找01字串的编码，当编码长度是题目给定的长度值时就表示构造成功了一个长度
因为dfs也是逐步构造的，长度信息也是逐步增加的，因此需要将原始长度序列升序排序

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 1000 + 5;
struct node {
    int len, id;string s;
};
node a[maxn];
int n, cnt = 0, flag = 0;bool cmp1(node a, node b)
{
    return a.len < b.len;
}
bool cmp2(node a, node b)
{
    return a.id < b.id;
}void dfs(int len, string str)
{
    if (len == a[cnt].len){
            a[cnt].s = str;cnt++;if (cnt == n) flag = true;return ;}dfs(len+1, str + "0");if (cnt < n)dfs(len+1, str + "1");
}int main()
{
    scanf("%d", &n);for (int i = 0; i < n; i++){
    scanf("%d", &a[i].len);a[i].id = i;a[i].s = "";}sort(a, a+n, cmp1);dfs(0, "");if (flag){
    printf("YES\n");sort(a, a+n, cmp2);for (int i = 0; i < n; i++)printf("%s\n", a[i].s.c_str());} else {
    printf("NO\n");}return 0;
}