哈夫曼编码和字典树

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
priority_queue <int,vector <int>,greater <int> > q;
int main() {
  int t;
  cin>>t;
  while(t--) {
    int n;
    char ch[100005];
    cin>>n>>ch;
    int tem[26];
    for(int i=0; i<26; i++)tem[i]=0;
    for(int i=0; i<strlen(ch); i++) {
      tem[ch[i]-'a']++;
    }
    int len=0,sum=0;
    for(int i=0; i<26; i++) {
      q.push(tem[i]);
      len++;
    }
    if(len==1){
      sum=q.top();
    }
    else{
      while(q.size()>1){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        sum+=a+b;
        q.push(a+b);
      }
    }
    q.pop();
    if(sum>n)
      cout<<"no"<<endl;
    else
      cout<<"yes"<<endl;
  }
}

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
priority_queue <int,vector <int>,greater <int> > q;
int main() {
  int n;
  while(cin>>n) {
    int len=1;
    for(int i=0; i<n; i++) {
      long long t;
      cin>>t;
      q.push(t);
      len++;
    }
    long long sum=0;
    if(len==1) {
      sum=q.top();
    } else {
      while(q.size()>1) {
        long long a=q.top();
        q.pop();
        long long b=q.top();
        q.pop();
        sum+=a+b;
        q.push(a+b);
      }
    }
    q.pop();
    cout<<sum<<endl;
  }
}

#include<iostream>
#include<string.h>
#include<sstream>
using namespace std;
int dict[10005][26];
int vis[10005];
int ans,k;
void insert (string s) {
  int len = s.size();
  int root = 0;
  for (int i = 0; i < len; i++) {
    int index = s[i] - 'a';
    if (!dict[root][index]) {
      dict[root][index] = ++k;
    }
    root = dict[root][index];
  }
  if(!vis[root]){
    vis[root]=1; 
    ans++;
  }
}
int main() {
  string s;
  while(getline(cin,s)) {
    if(s[0]=='#')return 0;
    memset(dict,0,sizeof(dict));
    memset(vis,0,sizeof(vis));
    stringstream ss(s);
    string s1;ans=0;
    while(ss>>s1) {
      insert(s1);//插入一个单词 
    }
    cout<<ans<<endl;
  }
}

#include<iostream>
#include<string>
using namespace std;
int dict[1000005][30];
int vis[1000005];
int ans,k;
void insert (string s) {
  int len = s.size();
  int root = 0;
  for (int i = 0; i < len; i++) {
    int index = s[i] - 'a';
    if (!dict[root][index]) {
      dict[root][index] = ++k;
    }
    root = dict[root][index];
    vis[root]++;//每个子串都赋值为1，则abcd里找a，ab，abc，abcd，
    //对应的vis[root]都有 ，并且重复前缀累加vis值 
  }
}
void find (string s) {
  int root = 0;
  int len = s.size();
  for (int i = 0; i < len; i++) {
    int index = s[i] - 'a';
    if(!dict[root][index]) {//如果bc，找abc的前缀，必然不存在以bc为前缀，
    //此时dict[root][index]没有被insert() 赋值，所有为0，检测到直接cout<<0退出即可 
      cout<<0<<endl;
      return ;
    }
    else {
      root=dict[root][index];
    }
  }
  cout<<vis[root]<<endl;//为前缀的单词的数量
}
int main() {
  string s;
  while(getline(cin,s)) {
    if(s[0]=='\0')break;
    insert(s);
  }
  while(cin>>s) {
    find(s);
  }
}

#include<iostream>
#include<stdio.h>
#include<string.h> 
using namespace std;
int dict[3200005][2];
int vis[3200005];
int ans,k;
int n,m;
void insert (int s) {
  int root = 0;
  for (int i = 31; i>=0; i--) {
    int index = (s>>i) & 1;//从高位到低位，存储该数的二进制编码 
    if (!dict[root][index]) {
      dict[root][index] = ++k;
    }
    root = dict[root][index];
  }
  vis[root]=s;//标记数字s的编码root为s 
}
void find (int s) {
  int root = 0;
  for (int i = 31; i>=0; i--) {
    int index = (s>>i) & 1;//位移出每一位 
    if (dict[root][index^1]) {//因为是异或，101与010匹配，所以优先考虑与当前index互斥的数
      root = dict[root][index^1];
    } 
    else {
      root = dict[root][index];//,如果互斥的分支没有那没办法了  
    }
  }
  cout<<vis[root]<<endl;//最后通过标记输出与哪个数最匹配即可 
}
int main() {
  int t;
  scanf("%d",&t);
  for(int i=1; i<=t; i++) {
    memset(dict,0,sizeof(dict));
    k=0;
    scanf("%d%d",&n,&m);
    for(int j=1; j<=n; j++) {
      int cnt;
      scanf("%d",&cnt);
      insert(cnt);
    }
    cout<<"Case #"<<i<<":"<<endl;
    for(int j=1; j<=m; j++) {
      int cnt;
      scanf("%d",&cnt);
      find(cnt);
    }
  }
}