首页 > 代码库 > UVa 10745 - Dominant Strings
UVa 10745 - Dominant Strings
题目:给你一些字符串,问哪些字符串不是其他字符串的子集,字符串的集合为字母组成的重集。
分析:字符串,dancing-links。Knuth有一篇关于dancing-links的论文,讲述关于搜索的优化。
在搜索时,将所有的状态建立一个链表,表之间的状态建立相互关系。
每次搜索时,进行剪枝,将不成立的节点从链表中删掉,回溯时在拼上去。
用数组建立链表,高效方便,存储L,R左右两端下标即可。
本题直接进行删除即可。
如果,一个字符串的补集是另一个字符串的子集,这个字符串的集合一定是另一的超集。
解法:
1.对每个字符串求补集(每个字符的个数记成负的即可)。
2.对补集排序,然后向后扫描,扫到他的子集(补集的超级)就删除那个节点。
3.重新排序,输出。
说明:看到有人用字典树做的,每次插入的时候先查询。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> typedef struct noded { char word[11]; int used; }dnode; dnode s[15005]; int L[15005]; int R[15005]; int id[15005]; int sum[15005][27]; using namespace std; int cmp1( const void* a, const void* b ) { int l1 = strlen(((dnode *)a)->word); int l2 = strlen(((dnode *)b)->word); if ( l1 == l2 ) return strcmp( ((dnode *)b)->word, ((dnode *)a)->word ); return l2 - l1; } int cmp2( const void* a, const void* b ) { if ( ((dnode *)b)->used == ((dnode *)a)->used ) return strcmp( ((dnode *)a)->word, ((dnode *)b)->word ); return ((dnode *)a)->used - ((dnode *)b)->used; } int main() { int count = 1; while ( gets(s[count].word) ) { if ( !strlen(s[count].word) ) break; s[count ++].used = 0; } qsort( s+1, count-1, sizeof(s[0]), cmp1 ); memset( sum, 0, sizeof(sum) ); for ( int i = 1 ; i < count ; ++ i ) for ( int j = 0 ; s[i].word[j] ; ++ j ) sum[i][s[i].word[j]-'a'] --; for ( int i = 1 ; i < count ; ++ i ) { id[i] = i; L[i] = i-1; R[i] = i+1; } R[0] = 1; R[count-1] = 0; for ( int p = R[0] ; p ; p = R[p] ) for ( int q = R[p] ; q ; q = R[q] ) { int flag = 1; for ( int k = 0 ; k < 26 ; ++ k ) if ( sum[id[p]][k] > sum[id[q]][k] ) { flag = 0; break; } if ( flag ) { s[id[q]].used = 1; R[L[q]] = R[q]; L[R[q]] = L[q]; } } qsort( s+1, count-1, sizeof(s[0]), cmp2 ); for ( int i = 1 ; i < count ; ++ i ) if ( s[i].used ) break; else printf("%s\n",s[i].word); //system("pause"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。