01ディクショナリツリー異種または問題解決学習、

5570 ワード

アルゴリズム学習

連絡先:blcakcat
HDU 4825
最高から欲張りを始めて、どのように現在の位置の異あるいは結果を歩いて異あるいは結果を歩いてさもなくば現在の結果を歩きます

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
LL value[32 * qq];
int ch[32 * qq][2];
int n, m, node_cnt;
void Init() {
	node_cnt = 1;
	mst(ch[0], 0);
}
void Insert(LL x) {
	int cur = 0;
	for(int i = 32; i >= 0; --i) {
		int idx = (x >> i) & 1;
		if(!ch[cur][idx]) {
			mst(ch[node_cnt], 0);
			ch[cur][idx] = node_cnt;
			value[node_cnt++] = 0;
		}
		cur = ch[cur][idx];
	}
	value[cur] = x;
}
LL Query(LL x) {
	int cur = 0;
	for(int i = 32; i >= 0; --i) {
		int idx = (x >> i) & 1;
		if(ch[cur][idx ^ 1])	cur = ch[cur][idx ^ 1];
		else	cur = ch[cur][idx];
	}
	return value[cur];
}

int main(){
	int t;	scanf("%d", &t);
	int Cas = 0;
	while(t--) {
		Init();
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; ++i) {
			LL x;	scanf("%lld", &x);
			Insert(x);
		}
		printf("Case #%d:
", ++Cas);
		for(int i = 0; i < m; ++i) {
			LL x;	scanf("%lld", &x);
			printf("%lld
", Query(x));
		}
	}
	return 0;
}

HDU 5536
題意:n個の求めることを与えて、(si+sj)^skの最大値を求めて、i,j,kは互いに等しくありません
構想:まずすべての数に対して1粒の01辞書の木を建てて、それからi,jを列挙して、siとsjを辞書の順序から削除して、貪欲に最大の結果を探します

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
int ch[32 * qq][2], value[32 * qq], node_cnt, n;
LL num[qq];
void Init() {
	node_cnt = 1;
	mst(ch[0], 0);
	mst(value, 0);
}
void Insert(LL x) {
	int cur = 0;
	for(int i = 32; i >= 0; --i) {
		int idx = (x >> i) & 1;
		if(!ch[cur][idx]) {
			mst(ch[node_cnt], 0);
			ch[cur][idx] = node_cnt++;
		}
		cur = ch[cur][idx];
		value[cur]++;
	}
}
void Delete(LL x) {
	int cur = 0;
	for(int i = 32; i >= 0; --i) {
		int idx = (x >> i) & 1;
		cur = ch[cur][idx];
		value[cur]--;
	}
}
LL Query(LL x) {
	int cur = 0;
	LL ans = 0;
	for(int i = 32; i >= 0; --i) {
		int idx = (x >> i) & 1;
		if(ch[cur][idx ^ 1] && value[ch[cur][idx ^ 1]]) {
			ans |= (1LL << i);
			cur = ch[cur][idx ^ 1];
		} else {
			cur = ch[cur][idx];
		}
	}
	return ans;
}

int main(){
	int t;	scanf("%d", &t);
	while(t--) {
		Init();
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%lld", num + i);
			Insert(num[i]);
		}
		LL maxn = 0;
		for(int i = 1; i <= n; ++i) {
			Delete(num[i]);
			for(int j = i + 1; j <= n; ++j) {
				LL x = num[i] + num[j];
				Delete(num[j]);
				maxn = max(maxn, Query(x));	
				Insert(num[j]);
			}
			Insert(num[i]);
		}
		printf("%lld
", maxn);
	}
	return 0;
}

HDU 3460
タイトル:n文字列があって、あなたは1つのプリンタがあって、あなたはプリンタを使ってすべての文字列を出力して、プリンタは3種類の操作があって、1つの文字を増加して、1つの文字を削除して、印刷して、少なくとも何回操作する必要がありますかを聞きます
構想:明らかに辞書ツリーを構築することができますが、肝心なのはどのように解くかです.このように考えることができます.まず、各文字列を印刷する貢献がnであることを知っています.では、印刷の貢献と削除の貢献を計算する必要があります.辞書ツリーを構築すると、辞書ツリーのすべてのノードが印刷する必要があります.これがすべての印刷の貢献です.削除の貢献は?最後に必ず1つの文字列しか残っていないことを明確にしなければならないので、前の肯定は削除されるので、すべて削除し、最長の文字列である削除操作の貢献を加えると仮定します.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e4 + 10;
const int INF = 1e9 + 10;
int ch[qq * 26][26];
int node_cnt, n;
char st[qq];
void Init() {
	mst(ch[0], 0);
	node_cnt = 1;
}
void Insert() {
	int cur = 0;
	int len = strlen(st);
	for(int i = 0; i < len; ++i) {
		int idx = st[i] - 'a';
		if(!ch[cur][idx]) {
			mst(ch[node_cnt], 0);
			ch[cur][idx] = node_cnt++;;
		}
		cur = ch[cur][idx];
	}
}

int main(){
	while(scanf("%d", &n) != EOF) {
		Init();
		int maxn = 0;
		for(int i = 0; i < n; ++i) {
			scanf("%s", st);
			maxn = max(maxn, (int)strlen(st));
			Insert();
		}
		printf("%lld
", -maxn + (node_cnt - 1) * 2LL + n);
	}
	return 0;
}

手引き裂きアルゴリズムシリーズのバブルソート

剣指offer-階段を跳ぶpython実現