首页 > 数据结构 > Hash表 > hdu 2335 Containers-分治-[解题报告]C++
2014
01-05

hdu 2335 Containers-分治-[解题报告]C++

Containers

问题描述 :

At a container terminal, containers arrive from the hinterland, one by one, by rail, by road, or by small ships. The containers are piled up as they arrive. Then the huge cargo ships arrive, each one capable of carrying thousands of containers. The containers are loaded into the ships that will bring them to far away shores. Or the other way round, containers are brought in over sea, piled up, and transported to the hinterland one by one. Anyway, a huge parking lot is needed, to store the containers waiting for further transportation.

Building the new container terminal at the mouth of the river was a good choice. But there are disadvantages as well. The ground is very muddy, and building on firm ground would have been substantially cheaper. It will be important to build the parking lot not larger than necessary.

A container is 40 feet long and 8 feet wide. Containers are stacked, but a stack will be at most five containers high. The stacks are organized in rows. Next to a container stack, and between two container stacks (along the long side of the containers) a space of 2 feet is needed for catching the containers. Next to a row of stacks, and between two stacks (along the short side of the containers) a space of 4 feet is needed for the crane that lifts the containers. All containers are placed in the same direction, as the cranes can not make turns on the parking lot.

The parking lot should be rectangular. Given the required capacity of the parking lot, what will be the best dimension for the parking lot? In the first place the area should be minimal. The second condition is that the parking lot should be as square as possible.

Below you see a plan for a parking lot with a capacity of 8 stacks. Two rows of four containers each turns out to be the best solution here, with a total area of 92 × 42 = 3864.

A parking lot with 8 container stacks.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

A single positive integer n (n ≤ 1012) on a single line: the required capacity (number of containers) for the parking lot.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

A single positive integer n (n ≤ 1012) on a single line: the required capacity (number of containers) for the parking lot.

样例输入:

6
1
15
22
29
36
43

样例输出:

48 X 12 = 576
48 X 32 = 1536
52 X 48 = 2496
92 X 32 = 2944
92 X 42 = 3864
136 X 32 = 4352

数据结构者,“数据间关系+数据存储方式”也。

选择何种数据结构,取决于需要解决什么样的问题。

任何一个数据结构都有它的优势,这个优势说白了就是“本数据结构在进行XX操作时快”,而选择何种数据结构就看要解决的问题需要在数据结构上进行何种操作来决定。

哈希表就是体现这个道理的一个很好的例子。

哈希表提供这么一种其它数据结构并不擅长的操作:

“在理想情况下,能用常量时间查找到指定值的数据”。

 

普通数据结构如线性表、树、图等,其结点内的数据与数据所存储的位置之间的关系是随机的,所以要想提供“查找某已知值的数据的位置”只能通过“比较”方式进行,如:对于未排序的线性表,要从头至尾逐一比较是否“==”;对于二分查找,则要比较“>”“<”还是“==”。这样,时间复杂度是n或者logn。

而哈希表通过“在存储位置和数据值之间建立映射关系”这一手段,将该操作的时间复杂度降低为O(1)。

这个描述“在存储位置和数据值之间建立映射关系”的映射关系就是哈希函数。

将数据存入哈希表时,利用哈希函数为该数据安排存储位置;查找指定值数据时,也按照哈希函数得到目标索引。

 

实际操作起来时,由于数值域和索引域大小不同,所以不能简单地线性映射,而是需要建立较复杂的哈希函数,这就有可能造成“冲突”——这是哈希面临的主要问题。好的哈希函数应该让随机数据值得到的哈希结果尽可能地随即和分散,而且减少冲突。

 

=====================分割线=======================

有这样一类问题,查找是否有出现多于一次的数据?笨方法只能从头至尾逐一比对,复杂性为O(N*N)。聪明一点的方法,如果数据不是很分散,可以用做记号的方法,用一个位数组(可用bool实现)记录各个位所代表的数据是否出现过,如果读入一个已经出现过的数据则说明它出现多于一次,用int代替bool,还可以记录下每个数据出现的次数,在遍历一次便可得到出现最多次的数据,复杂度为O(N)。但是如果数据很分散,这种线性映射就不管用了,因为内存会严重浪费,如果数据过于夸张,会造成很大BUFFER的申请,但是这种映射记录的思想还是可取的,这时就需要一个从很大的数据域向相对很小的地址域映射的工具来辅助,自然就是“哈希”。

 

POJ3349就是利用哈希这个特点的一个典型应用。题目本身与存取无关,而只是要找出是否有数据出现过一次以上。就可以采取上述“标记”+“映射”的方法。

 

CODE:

/*hash判重*/
/*
1. 直接相加, 把(总和%大质数)为key.
2. 平方和相加, 把(总和%大质数)为key.
3. 从小到大的顺序, 对v[i]<<(i*3)依次异或, 然后模一个大质数作为key.(by hust07p43)
4. 六个数中非零数的积再乘上一个大质数,然后模一个100w上下的数。
自己拿随机数据测下来110w左右的效果最好,随机情况下数据量是10w的时候hash值相同的情况只有6k多个,几乎可以忽略。(by  killertom)
5. 依次对每个数异或所得的数作为key. (by archerstarlee)
6. (a[0] + a[2] + a[4])&(a[1] + a[3] + a[5]), 再模一个大质数. 中间的&还可以改成'|' 或者'^'.非常巧妙! 我采用'^'得到最快的719ms. (只对本题适用的hash方法)

其实最关键的就是要开放式寻址解决hash冲突, 不要以为hash就能解决问题了.
最后就是用getchar和gets来进行输入转换更为快速. G++比GCC快一些.
欢迎大家补充自己更为快速的Hash方法.
*/
/*AC代码:2344ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#define MAXN 100000
#define MOD 99991
using namespace std;
struct Node
{
	int val[7];
};
struct Node Hash[MAXN][20];//hash表
int len[MAXN];//相应hash表的长度
int N;
bool ok;
int hash(Node u)//hash函数
{
	int i,sum=0;
	for(i=1;i<=6;i++)
		sum+=u.val[i];
	return sum%MOD;
}
void Rotate(Node &u)//移动
{
	int i,t=u.val[1];
	for(i=1;i<=5;i++)
		u.val[i]=u.val[i+1];
	u.val[6]=t;
}
void Reverse(Node &u)//翻转
{
	Node v;
	int i,j;
	for(i=1,j=6;i<=6;i++,j--)
		v.val[i]=u.val[j];
	u=v;
}
bool Equal(Node u,Node v)//判断是否相等
{
	int i;
	for(i=1;i<=6;i++)
	{
		if(u.val[i]!=v.val[i])
			return false;
	}
	return true;
}
void Judge(Node u,Node v)
{
	int i;
	for(i=1;i<=6;i++)
	{
		Rotate(u);
		if(Equal(u,v)) {ok=false;return;}
	}
	Reverse(u);
	for(i=1;i<=6;i++)
	{
		Rotate(u);
		if(Equal(u,v)) {ok=false;return;}
	}
}
void Init()
{
	int i,j;
	Node u;
	ok=true;
	memset(len,0,sizeof(len));
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=6;j++)
			scanf("%d",&u.val[j]);
		if(!ok) continue;
		int pos=hash(u);
		for(j=0;j<len[pos];j++)
		{
			Judge(u,Hash[pos][j]);
			if(!ok) break;
		}
		Hash[pos][len[pos]++]=u;
	}
}
void Solve()
{
	if(ok) printf("No two snowflakes are alike.\n");
	else printf("Twin snowflakes found.\n");
}
int main()
{
	while(scanf("%d",&N)!=EOF)
	{
		Init();
		Solve();
	}
	return 0;
}

解题转自:http://blog.csdn.net/allenjy123/article/details/6629320


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1