哈希表

题目描述:

你有一个盒子,你可以往里面放数,也可以从里面取出数。
初始时,盒子是空的,你会依次做 Q 个操作,操作分为两类:
插入操作:询问盒子中是否存在数 x,如果不存在则把数 x 丢到盒子里。
删除操作:询问盒子中是否存在数 x,如果存在则取出 x。
对于每个操作,你需要输出是否成功插入或删除。

输入
第一行一个正整数 Q,表示操作个数。

接下来 Q 行依次描述每个操作。每行 2 个用空格隔开的非负整数 op,x 描述一个操作:op 表示操作类型, op=1 则表示这是一个插入操作,op=2 则表示这是一个删除操作;x 的意义与操作类型有关,具体见题目描述。

数据范围

对于 100% 的数据,保证 x<10^18,Q≤5*10^5。

样例输入
6
1 100
1 100
2 100
1 200
2 100
2 200
样例输出
Succeeded
Failed
Succeeded
Succeeded
Failed
Succeeded

这道题的解法很多,主要涉及到插入、查询和删除操作,但需要考虑的是数据规模,第一个比较简单的方法是直接使用一个容器来维护这些数据,在stl里面,这个操作最快的是set,如果不清楚set是啥,可以在我的博客里面搜一下。set的底层是基于红黑树实现的,这种数据结构非常高级,插入查询和删除都能在O(logn)的时间内完成。下面是代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//使用查询和插入速度很快的数据结构 
set <ll> container; 
bool check(int op, ll x) {
    if(op == 1){                //如果容器里面没有,插入 
    	if(container.find(x) == container.end()){
    		container.insert(x);
    		return true;
		}
		else
			return false;    		
	}		
	else                        //如果容器里面有,删除 
		if(container.find(x) != container.end()) {
			container.erase(x); 
			return true;
		} else
			return false;
}
int main() {
    int Q, op;
    ll x;
    scanf("%d", &Q);
    while (Q--) {
        scanf("%d%lld", &op, &x);
        puts(check(op, x) ? "Succeeded" : "Failed");
    }
    return 0;
}

第二种操作比较重要,使用哈希表来进行存储,哈希表我当年学习数据结构的时候并没有实现过,只是了解它的原理,但是了解原理之后,实现还是比较简单的,我这里使用的是二维数组来存储,只不过如果每一行后面有冲突需要挂元素的时候,我使用vector来存,比较节省空间。

代码如下:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int Mod = 1000003;   //哈希的模长 
vector <ll> table[Mod];    //哈希表,向量中每个元素都是一个table数组 

int Hash(ll x) {
	return x % Mod;
} 

bool check(int op, ll x) {
    int h = Hash(x);    //找出哈希值
	vector <ll> :: iterator ptr = table[h].end();
	
	for(vector <ll> :: iterator it = table[h].begin(); it != table[h].end(); it++)
		if(*it == x) {   //看之前在不在vector中 
			ptr = it;
			break;
		}
	
	if(op == 1) {      //插入元素 
		if(ptr == table[h].end()) {   //如果之前没有找到 
			table[h].push_back(x); 
			return true;
		}
		return false;			
	} else {             //else在这里的功能是删去x的元素 
		if(ptr != table[h].end())   //指针不为表首则可以删除 
		{
			*ptr = table[h].back();  
			table[h].pop_back();  //最后一个元素弹出 
			return true;
		}
		return false;
	}		
}
int main() {
    int Q, op;
    ll x;
    scanf("%d", &Q);
    while (Q--) {
        scanf("%d%lld", &op, &x);
        puts(check(op, x) ? "Succeeded" : "Failed");
    }
    return 0;
}

哈夫曼

题目如下:

有一篇文章,文章包含 n种单词,单词的编号从 1 至 n,第 i 种单词的出现次数为 w[i]。
现在,我们要用一个 2 进制串(即只包含 0 或 1 的串) s[i] 来替换第 i 种单词,使其满足如下要求:对于任意的 1≤i,j≤n(i≤j),都有 s[i] 不是 s[j] 的前缀。(这个要求是为了避免二义性)
你的任务是对每个单词选择合适的 s[i],使得替换后的文章总长度(定义为所有单词出现次数与替换它的二进制串的长度乘积的总和)最小。求这个最小长度。
字符串 S1(不妨假设长度为 n)被称为字符串 S2 的前缀,当且仅当:S2 的长度不小于 n,且 S1 与 S2 前 n 个字符组组成的字符串完全相同。

输入格式
第一行一个整数 n,表示单词种数。(0<n<100000)

第 2 行到第 n+1 行,第 i+1 行包含一个正整数 w[i],表示第 i 种单词的出现次数m。(1<m<80000)

输出格式
输出一行一个整数,表示整篇文章重编码后的最短长度。

样例输入
4
1
1
2
2

样例输出
12

哈夫曼编码各位应该都比较熟悉,最开始森林中都是节点,然后挑选两个权重最小的节点合并成一颗树,这颗新树的权值是两个节点和,然后把这颗树放回去,再挑两个权值最小的树,直到森林中只有一棵树,就结束迭代,主要用到的算法思想是贪心。

代码如下:

#include<iostream>
#include<queue>
using namespace std; 

priority_queue<int ,vector <int> , greater<int> > pque;  //定义一个维护森林的优先级队列,这样我们的取小操作可以到达O(logn)的级别,关于优先级队列,我也会写一篇博客来描述

int getAnswer()
{
	int sum = 0;
	while(pque.size() > 1) { //如果森林中只有一棵树就停止迭代
		int weight = 0;
		for(int i = 0 ; i < 2 ; ++i) { //取两个最小的迭代
			weight += pque.top();
			pque.pop();				
		}
		sum += weight;  //将本次合并对答案的贡献加入答案
		pque.push(weight);  //再将新的元素加入队列
	}	
	return sum;
}
int main() {
	int n;
	scanf("%d" , &n);	
	int tmp;
	for(int i = 0 ; i < n ; ++i) {
		scanf("%d" , &tmp);
		pque.push(tmp);  //将元素都存入队列中
	}	
	printf("%d\n" , getAnswer());
	return 0;
}

sum+=weight;这条语句用到了哈夫曼树的一个性质,这也是为什么我们不用模拟出一棵树,而直接就可以得到答案的原因。

起泡排序

也就是冒泡排序,我想这么经典的算法应该不用我多赘述了。。。

题目如下:

有 n 名学生,它们的学号分别是 1,2,…,n。这些学生都选修了林老师的算法、数据结构训练营这两门课程。
学期结束了,所有学生的课程总评都已公布,所有总评分数都是 [0,100] 之间的整数。巧合的是,不存在两位同学,他们这两门课的成绩都完全相同。
林老师希望将这些所有的学生按这两门课程的总分进行降序排序,特别地,如果两位同学的总分相同,那林老师希望把算法得分更高的同学排在前面。由于上面提到的巧合,所以,这样排名就可以保证没有并列的同学了。
林老师将这个排序任务交给了他的助教。可是粗心的助教没有理解林老师的要求,将所有学生按学号进行了排序。
林老师希望知道,助教的排序结果中,存在多少逆序对。
如果对于两个学生 (i,j) 而言,i 被排在了 j 前面,并且i 本应被排在 j 的后面,我们就称 (i,j) 是一个逆序对。
请你先帮林老师把所有学生按正确的顺序进行排名,再告诉他助教的错误排名中逆序对的数目。

输入格式
第一行一个整数 n,表示学生的个数。

第 2 行到第 n+1 行,每行 2 个用空格隔开的非负整数,第 i+1 行的两个数依次表示学号为 i 的同学的算法、数据结构训练营的总评成绩。

输出格式
输出包含 n+1 行。

前 n 行表示正确的排序结果,每行 4 个用空格隔开的整数,第 i 行的数依次表示排名为 i 的同学的学号、总分、算法成绩、数据结构训练营成绩。

第 n+1 行一个整数,表示助教的错误排名中逆序对的数目。

样例输入
3
95 85
90 90
100 99
样例输出
3 199 100 99
1 180 95 85
2 180 90 90
2
样例解释
学号为 3 的同学总分为 199,是最高的,所以他应该排第一名。
学号为 1 的同学虽然总分与学号为 2 的同学一致,但是他的算法成绩更高,所以在排名规则下更胜一筹。

原错误排名中的逆序对数目为 2 ,这些逆序对分别为 (1,3) 和 (2,3)。

数据范围
对于 25% 的数据,保证 n=3。
对于 50% 的数据,保证 n≤10。
对于另外 25% 的数据,保证所有同学的总分两两不同。
对于 100% 的数据,保证 n≤5,000 ,且保证不存在成绩完全相同的学生。
时间限制:10 sec
空间限制:256 MB

#include <bits/stdc++.h>
using namespace std;

vector<int> getAnswer(int n, vector<int> A, vector<int> DS) {
    vector<int> sum, id;  //记录总分和编号 
	vector<int> ans;     //返回值 
	
	for(int i = 0 ; i < n ; ++i) {
		id.push_back(i + 1);             //将编号录入 
		sum.push_back(DS[i] + A[i]);  //将总分录入 
	}
		
		int cnt = 0;  //记录逆序对个数
		for(int i = 0 ; i < n ; ++i) {
			for(int j = n - 1;  j > 0 ; --j) {   //除了要判断总成绩之外,题目还要求:当两者成绩相同时,按算法的来 
				if(sum[j] > sum[j - 1] || sum[j] == sum[j - 1] && A[i] > A[i - 1]) {
					swap(id[j], id[j - 1]);
					swap(sum[j] , sum[j - 1]);
					swap(A[j] , A[j - 1]);
					swap(DS[j] , DS[j - 1]);
					
					cnt++;					
				}	
			
			} 
		}
		
		for(int i = 0 ; i < n ; ++i) {
			ans.push_back(id[i]);
			ans.push_back(sum[i]);
			ans.push_back(A[i]);
			ans.push_back(DS[i]);
		}		
		ans.push_back(cnt);
		return ans;		
	
	 
}

int main() {
    int n;
    scanf("%d", &n);
    vector<int> A, DS;
    for (int i = 0; i < n; ++i) {
        int a, ds;
        scanf("%d%d", &a, &ds);
        A.push_back(a);
        DS.push_back(ds);
    }
    vector<int> ans = getAnswer(n, A, DS);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        printf("%d %d %d %d\n", ans[cnt], ans[cnt + 1], ans[cnt + 2], ans[cnt + 3]);
        cnt += 4;
    }
    printf("%d\n", ans[cnt]);
    return 0;
}

在冒泡排序的过程中,交换的次数,就是逆序对的个数。


立志做一名攻城狮