`
从此醉
  • 浏览: 1034958 次
  • 性别: Icon_minigender_1
  • 来自: US
社区版块
存档分类
最新评论

hdu 3460 Ancient Printer

 
阅读更多

点击打开链接hdu3640


思路:字典树

分析:
1 题目要求的是给定n个字符串,现在有一台的打印机有三种操作“取字符”,“删除最后一个字符”,“打印当前单词”,问最少需要几次的操作(最后一个单词不用删除)。
2 要最少的次数,那么就是使得最后一个单词必须是所有单词中的最长的,所以这里需要涉及到对二维数组的排序利用qsort从小到大;
3 如果两个单词有相同的公共前缀那么肯定是可以减少输入的次数,所以在建字典树的时候应该在节点里面用一个flag标记当前的字符是否被取过,还有要几下以当前的单词为前缀的字符串的个数count。
4 几下了以当前字符串为前缀的字符串的个数的时候,那么我们在具体查找的时候就是判断当前的字符是否被取过,如果没被取过那么标记为取过并ans++;每一次都要把当前字符的count--,当count = 0并且不是最后一个单词的时候就要开始删除所以这个时候ans++;

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define MAXN 1000010
#define MAX 60
#define N 30

int cnt , n;
int ans;
char words[10010][MAX];
struct Trie{
   int count;
   bool flag;
   Trie *child[N];
}trie[MAXN];
Trie *root;

/*自定义的函数*/
int cmp(const void *str1 , const void *str2){
    return strlen((char*)str1) - strlen((char*)str2);
}

/*字典树的空间的分配*/
Trie* newTrie(){
   trie[cnt].count = 0;
   trie[cnt].flag = false;
   for(int i = 0 ; i < N ; i ++)
     trie[cnt].child[i] = NULL;
   return &trie[cnt++];
}

/*字典树的插入*/
void insert(char *str){
    Trie *s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
       int num = str[i]-'a';
       if(s->child[num] == NULL)
         s->child[num] = newTrie();
       s = s->child[num];
       s->count++;/*这里自增加1*/
    }
}

/*字典树的查找*/
void search(char *str , int j){
    Trie *s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
       int num = str[i]-'a';
       s = s->child[num];
       if(s->flag == false){
         ans++;
         s->flag = true;
       }
       s->count--;/*这个地方一定要减1,不然就是WA*/
       if(s->count == 0 && j != n-1)
         ans++;
    }
    ans++;/*每一个单词都要打印就是加1*/
}

int main(){
   while(scanf("%d" , &n) != EOF){
       cnt = 0;
       root = newTrie();
       for(int i = 0 ; i < n ; i++){
          scanf("%s" , words[i]);   
          insert(words[i]);
       }
       qsort(words , n , sizeof(words[0]) , cmp);/*按照长度排序*/
       ans = 0;
       for(int i = 0 ; i < n ; i++)
          search(words[i] , i);
       printf("%d\n" , ans);
   }
   return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics