字典树模板，v记录当前节点下单词数，注意与当前节点相同（到当前节点为止）的单词的统计p->v-sumall_vnext
#include <iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<bitset> using namespace std; #define zero {0} typedef struct Trie { int v; Trie *next[26]; } Trie; char s[100100][100]; Trie root; void createTrie(char *str) { int len = strlen(str); Trie *p = &root, *q; for(int i=0; i<len; ++i) { int id = str[i]-'a'; if(p->next[id] == NULL) { q = (Trie *)malloc(sizeof(root)); q->v = 1; for(int j=0; j<26; ++j) q->next[j] = NULL; p->next[id] = q; p = p->next[id]; } else { p->next[id]->v++; p = p->next[id]; } } } int findTrie(char *str) { int len = strlen(str); int ret=0,x,y; Trie *p = &root; for(int i=0; i<len; ++i) { int id = str[i]-'a'; if (i!=0) x=p->v; else x=-1; p = p->next[id]; y=p->v; if(i!=0&&x==y) ret++; } return len-ret; } int findnum(char *str) { int len=strlen(str); Trie *p = &root; for(int i=0; i<len; i++) { int id=str[i]-'a'; if(p->next[id]) { p=p->next[id]; } else { return 0; } } int sum=0; for(int i=0; i<26; i++) { if(p->next[i]) sum+=p->next[i]->v; } sum=sum+p->v-sum; return sum; } int main() { int i,n,sum,m; while (scanf("%d%d",&n,&m)!=EOF) { for(i=0; i<26; ++i) root.next[i] = NULL; getchar(); for (i=1; i<=n; i++) { gets(s[i]); createTrie(s[i]); } sum=0; for(i=0;i<m;i++) { int zimushu; scanf("%d",&zimushu); char str[1005]=zero; double bit[10]=zero; for(int j=0;j<zimushu;j++) { double ave=0; bitset<32>b; for(int k=7;k>=0;k--) { scanf("%lf",&bit[k]); ave+=bit[k]; } ave/=8; for(int k=7;k>=0;k--) { if(bit[k]>ave) { b.set(k,1); } else { b.set(k,0); } } str[j]=b.to_ulong(); // cout<<b.to_string()<<endl; } // cout<<str<<endl; sum+=findnum(str); } // scanf("%s",str); // cout<<findnum(str)<<endl; printf("%d\n",sum); } return 0; } View Code
转载于:https://www.cnblogs.com/Skyxj/p/3407603.html
相关资源：数据结构—成绩单生成器