哈夫曼

在这里插入图片描述

HUD2527

http://acm.hdu.edu.cn/showproblem.php?pid=2527

#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;

	}
}

VJ

http://vjudge.net/contest/view.action?cid=49918#problem/A

#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;
	}
}

字典树

在这里插入图片描述

HUD2072为例

http://acm.hdu.edu.cn/showproblem.php?pid=2072

#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;
	}
}

HUD1251为例

http://acm.hdu.edu.cn/showproblem.php?pid=1251

#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);
	}
}

01字典树

HUD4825

http://acm.hdu.edu.cn/showproblem.php?pid=4825

#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);
		}
	}
}