Monthly Archives: December 2014

hihoCoder 1093-最短路径·三:SPFA算法

hihoCoder 1093-最短路径·三:SPFA算法
#1093 : 最短路径·三:SPFA算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
万圣节的晚上,小Hi和小Ho在吃过晚饭之后,来到了一个巨大的鬼屋!
鬼屋中一共有N个地点,分别编号为1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。
不过这个鬼屋虽然很大,但是其中的道路并不算多,所以小Hi还是希望能够知道从入口到出口的最短距离是多少?
提示:Super Programming Festival Algorithm。
输入
每个测试点(输入文件)有且仅有一组测试数据。
在一组测试数据中:
第1行为4个整数N、M、S、T,分别表示鬼屋中地点的个数和道路的条数,入口(也是一个地点)的编号,出口(同样也是一个地点)的编号。
接下来的M行,每行描述一条道路:其中的第i行为三个整数u_i, v_i, length_i,表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据,满足N<=10^5,M<=10^6, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
对于100%的数据,满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
输出
对于每组测试数据,输出一个整数Ans,表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。
样例输入
5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63
样例输出
172


对于边稀疏的图,SPFA算法可以更高效的求解单源最短路径问题。
假设要求S和T的最短路径,该算法使用一个队列,最开始队列中只有(S,0)—表示当前处于点S,从点S到达该点的距离为0,然后每次从队首取出一个节点(i, L)——表示当前处于点i,从点S到达该点的距离为L,接下来遍历所有从这个节点出发的边(i, j, l)——表示i和j之间有一条长度为l的边,在将(j, L+l)加入到队列之前,先判断队列中是否存在点j,如果存在(j,l’),则比较L+l和l’的大小关系,如果L+l>=l’,那么(j,L+l)这条路就没必要继续搜索下去了,所以不将(j,L+l)加入队列;如果L+l<l’,那么原来的(j,l’)没必要继续搜索下去了,把(j,l’)替换成(j,L+l)即可。如果原队列中不存在j点,则直接把(j,L+l)加入队列。
当队列为空时,(T,ans)就是S到T的距离为ans。所以SPFA在某种程度上来说,就是BFS+剪枝。
SPFA的原理不难,写代码的时候要注意几点:1)N的范围是N<=10^5,如果用数组存储的话,内存够呛,所以建议用vector动态分配;2)每次从队列中弹出一个点时,记得将其在队列中的标记清空,即used[i]=0;3)处理好数据结构问题,因为数据输入中2点之间的距离可能有多个值,你可以在输入的时候只存储最小值,你也可以为了方便先把所有数据都存起来,统一在SPFA算法中进行大小判断,本代码使用第二种策略。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N=1e5+10;
const int INF=1e6+10;
int n,m,s,t;
//int path[MAX_N][MAX_N];//数组太大,改用vector动态分配
vector<int> path[MAX_N];//path[i][j]表示第i个点和第path[i][j]个点有路相同,其中j是输入的顺序
vector<int> dist[MAX_N];//dist[i][j]表示和第i个点相连的第j个点的距离是dist[i][j],path[i][j]和dist[i][j]是通过相同的j来共享数据
int used[MAX_N];//used[i]表示第i个点是否在队列中
int s_dist[MAX_N];//s_dist[i]表示第i个点和起始点s的距离
int spfa()
{
	int q1=s;
	used[q1]=1;
	for(int i=1;i<=n;i++)
		s_dist[i]=INF;
	s_dist[s]=0;
	queue<int> Q;
	Q.push(q1);
	while(!Q.empty())
	{
		q1=Q.front();
		Q.pop();
		used[q1]=0;//当弹出队列时记得设置used[i]=0
		int qs=path[q1].size();//和q1点相连的点的个数
		for(int i=0;i<qs;i++)
		{
			int u=path[q1][i];
			if(s_dist[q1]+dist[q1][i]<s_dist[u])//如果u是q1的父节点,肯定不满足这一条,所以不会回溯
			{
				s_dist[u]=s_dist[q1]+dist[q1][i];
				if(used[u]==0)
				{
					used[u]=1;
					Q.push(u);
				}
			}
		}
	}
	return s_dist[t];
}
int main()
{
	//freopen("input.txt","r",stdin);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int u,v,len;
	while(m--)
	{
		scanf("%d%d%d",&u,&v,&len);
		//记录了所有数据,此处还可以优化
		path[u].push_back(v);
		path[v].push_back(u);
		dist[u].push_back(len);
		dist[v].push_back(len);
	}
	printf("%d\n",spfa());
	return 0;
}

本代码提交AC,用时208MS,内存19MB。

hihoCoder 1077-RMQ问题再临-线段树

hihoCoder 1077-RMQ问题再临-线段树
#1077 : RMQ问题再临-线段树
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上回说到:小Hi给小Ho出了这样一道问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品)。
小Ho提出了两种非常简单的方法,但是都不能完美的解决。那么这一次,面对更大的数据规模,小Ho将如何是好呢?
提示:其实只是比ST少计算了一些区间而已
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。
每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi
对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。
样例输入
10
3655 5246 8991 5933 7474 7603 6098 6654 2414 884
6
0 4 9
0 2 10
1 4 7009
0 5 6
1 3 7949
1 3 1227
样例输出
2414
884
7474


这一题是hihoCoder Problem 1070:RMQ问题再临的升级版,数据量提升到10^6,但提示还是用线段树来解决。我原本以为只要把之前的数组大小改为10^6就行了,没想到这次居然给我报CE错。
第一次遇到这种错误,看了半天没明白什么意思,后来多方查找才得知可能是数组太大了,直接编译就不通过,想想看10^6的二维数组:10^6*10^6=10^12,装的是int,则总大小为4*10^12B=3725G,这明显大大超出了内存范围,而之前的10^4二维数组只有4*10^8B=381M,按理说也超出了题目的256MB,不过还是险些AC了,但是这一次就没这么好运了,所以必须优化算法!
怎样优化内存空间呢?先把我们的线段树请出来看看:

上图是线段树的一个例子,每个节点保存了区间范围以及该区间的最小值。总的区间大小是[1,10],仔细看看这个区间树的节点个数只有19个;另外再画一个[1,6]区间上的区间树,节点个数只有11个。可以不加证明的得出一个n的区间长度的线段树的节点个数为2*n-1,这远远小于n*n,所以我们只需要O(n)的空间来存储,而不是O(n^2)。
反观之前hihoCoder Problem 1070:RMQ问题再临的解法,其实没有构造一个真正的线段树,所以浪费了很多空间,那么怎样来构造一个真正的线段树呢?
我们知道常规的树形结构是用链表来实现的,每一个节点都有指向其左右孩子节点的指针,这样就可以很容易的访问孩子节点,如果用数组的结构来表示链表的结果,是不是会简单很多呢?于是我们定义如下树的节点结构:

typedef struct node//线段树节点
{
	int l;//区间左端点
	int r;//区间右端点
	int minv;//区间最小值
};

再定义一个表示树的数组node tree[2*MAX_N];很自然的tree[i]的左右孩子节点分别存储在tree[2i]和tree[2i+1],这样是不是也很容易访问孩子节点了呢。
不论是创建、查询、更新树,都是从树根开始递归往下,这个过程和之前的那个题目类似,这里就不再赘述了。完整的代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=1e6+2;
int w[MAX_N];
int n,q;
typedef struct node//线段树节点
{
	int l;//区间左端点
	int r;//区间右端点
	int minv;//区间最小值
};
node tree[2*MAX_N];
inline int get_min(int a,int b)
{
	return a<b?a:b;
}
//创建树
void build(int l,int r,int pos)
{
	tree[pos].l=l;
	tree[pos].r=r;
	if(l==r)
		tree[pos].minv=w[l];
	else
	{
		int mid=(l+r)/2;
		build(l,mid,pos*2);
		build(mid+1,r,pos*2+1);
		tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv);
	}
}
//查询树
int query(int l,int r,int pos)
{
	if(l==tree[pos].l&&r==tree[pos].r)
		return tree[pos].minv;
	int mid=(tree[pos].l+tree[pos].r)/2;
	if(r<=mid)
		return query(l,r,pos*2);
	else if(l>mid)
		return query(l,r,pos*2+1);
	else
	{
		int left=query(l,mid,pos*2);
		int right=query(mid+1,r,pos*2+1);
		return get_min(left,right);
	}
}
//更新树
void update(int pi,int wi,int pos)
{
	if(tree[pos].l==tree[pos].r&&tree[pos].l==pi)
		tree[pos].minv=wi;
	else
	{
		int mid=(tree[pos].l+tree[pos].r)/2;
		if(pi<=mid)
			update(pi,wi,pos*2);
		else
			update(pi,wi,pos*2+1);
		tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv);
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	build(1,n,1);
	scanf("%d",&q);
	int p,l,r;
	for(int i=0;i<q;i++)
	{
		scanf("%d%d%d",&p,&l,&r);
		if(p==0)
			printf("%d\n",query(l,r,1));
		else
			update(l,r,1);
	}
	return 0;
}

本代码提交AC,用时697MS,内存45MB。
P.S.之前用cin、cout超时,改成scanf、printf就好了,懒得取消同步什么的,以后就打算一直用scanf、printf了。唉,从上一题到这一题,优化是无止境的啊~~

POJ 1061-青蛙的约会

POJ 1061-青蛙的约会
青蛙的约会
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 92723 Accepted: 17043
Description
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
Source
浙江


本题考察数论的相关知识。假设A,B跳了k次后相遇,则有方程(x+km)modL=(y+kn)modL成立,即(x+km-y-kn)=tL,k和t即为我们要求的一组解。
令a=m-n; b=y-x;则上式转换为

ka+tL=b \ \ ---------------(1)


因为t可正可负,所以这里加号减号都可以。
根据裴蜀定理,要使ka+tL=b有整数解,必须满足b是d的倍数,其中d是a和L的最大公约是,即d=gcd(a,L)。所以我们首先利用欧几里得算法求a,L的最大公约d,判断b是否是d的倍数,如果不是,则直接输出Impossible。
如果b是d的倍数,那么怎样来求解ka+tL=b这个二元一次方程呢?
将(1)式同时除以d,得到

k(a/d)+t(L/d)=(b/d) \ \ ---------------(2)


(1)式和(2)式的解是完全等价的。
因为d=gcd(a,L),且b是d的倍数,所以a/d, L/d, b/d都是整数,并且gcd(a/d, L/d)=1。所以我们可以先求得

k(a/d)+t(L/d)=gcd(a/d, L/d)=1 \ \ ---------------(3)


的解,再将解乘以(b/d)不就是式(2)的解了吗,那么怎样求(3)式的解呢,这时候要用到扩展欧几里得算法,维基百科上有具体的演算例子,不懂的可以参考,下图是《算法导论》上关于扩展欧几里得算法算法的描述,也非常清晰易懂:

设利用扩展欧几里得算法求到的式(3)的解为k_0t_0,那么式(2)的解为k=(b/d)k_0t=(b/d)t_0。那么最小的k是多少呢?
又因为根据数论中的相关定理,如果ax+by=m有一组解(x0,y0),则整个解系为x=x0+ub; y=y0+ua; 其中u为整数,所以对照等式(2)可得k的解系为k=(b/d)k_0+u(L/d),它的最小值就是这个解系中的最小正整数。
理清了上述关系后,可以开始写代码了,如下:

#include<stdio.h>
#define LL long long
LL x,y,m,n,L,k0,t0,d;//k0,t0为某一组解,d为最大公因数
//求a,b的最大公因数
LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
//扩展欧几里得算法求ax+by=gcd(a,b)的一组解(x,y)
void extended_euclid(LL a,LL b,LL& x,LL& y)
{
	if(b==0)
	{
		x=1;
		y=0;
	}
	else
	{
		extended_euclid(b,a%b,x,y);
		LL tmp=x;
		x=y;
		y=tmp-(a/b)*y;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	LL a,b;
	while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF)
	{
		if(m==n)//因为青蛙起点不一样,如果速度一样,肯定不可能相遇
		{
			printf("Impossible\n");
			continue;
		}
		a=m-n;
		b=y-x;
		if(a<0)//扩展欧几里得需要非负数
		{
			a=-a;
			b=-b;
		}
		d=gcd(a,L);
		if(b%d!=0)
		{
			printf("Impossible\n");
			continue;
		}
		a/=d;
		L/=d;
		b/=d;
		extended_euclid(a,L,k0,t0);
		k0*=b;
		t0*=b;//无需求解,没用到
		if(k0>0)
			k0=k0%L;
		else
			k0=k0%L+L;
		printf("%lld\n",k0);
	}
	return 0;
}

本代码提交AC,用时0MS,内存132K。
因为扩展欧几里得算法包含了欧几里得算法,所以该代码还可以稍微优化一下。

hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临
#1070 : RMQ问题再临
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢?
于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢?
提示:平衡乃和谐之理
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。
每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi
对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。
样例输入
10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5
样例输出
1923
2009
1020
1923


本题的数据量比hihoCoder Problem 1068: RMQ-ST 算法这题要小,虽然

用O(N)的时间进行计算——扫描一遍整个区间找到最小值,然后对于每一个更改操作,使用O(1)的时间直接进行修改,这样也就是O(NQ)的总时间复杂度!在这种数据量下完全是可以通过的!

但是本题希望我们用线段树来解决。
我曾在《数据结构》的改造红黑树中看到过区间树,但是本题的线段树和书中的区间树有所区别,区间树由红黑树改造而来,结构更复杂些,这里只需要使用线段树即可。
常规的线段树如下图所示:

从图中可以看到构造线段树的过程就是一个二分的过程,不断将区间分成两半,直到只有一个元素。图中的线段树每一个节点是一个区间[l,r],本题我稍微改造了一下,改成了数组int seg_tree[left][length],比如seg_tree[i][j]表示从下标i开始,长度为j的这样一个区间上的最小值,这样就可以利用线段树来解决RMQ问题了。比如改造后的线段树就成了下面的样子:

因为树形这种特殊的结构,我们可以用一个DFS来对树实现二分构造,当DFS到某个节点长度为1时,其最小值就是w[i]本身,在回溯到父节点时,父节那个区间的最小值又是所有子节点最小值中的最小值。因为树的总节点数大约为2*n,所以复杂度O(n)。
当需要查询区间[l,r]的最小值时,只需对数组seg_tree二分搜索。具体来说,假设我们搜索到了节点[s_l,s_len],如果r<(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的左边,我们递归在[s_l,s_len/2]区间找;如果l>=(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的右边,我们递归在[s_l+s_len/2,s_len-s_len/2]区间找;如果以上两者都不是,说明[l,r]跨界了,而且中点下标一定是s_l+s_len/2,所以我们分别在二两半区间找,然后求这两者的最小值。复杂度O(lgn)。
当需要更新某个下标为pos的值为value时,也是DFS查找线段树,直到找到叶子seg_tree[pos][1],更新它的值,以及所有我们在查找过程经过的父节点的值。复杂度O(lgn)。
所以线段是的性质使得无论是构造、查询、更新操作,复杂度都只要O(lgn),这就是题目中所说的把总的复杂度平均分配到不同操作:平衡乃和谐之理。
完整代码如下:

#include<iostream>
using namespace std;
const int MAX_N=1e4+2;
int w[MAX_N];//每个商品重量
int n,m;
int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]:起点为i,长度为j的区间的最小值
inline int get_min(int a,int b)
{
     return a<b?a:b;
}
//深度优先遍历以构造线段树
void dfs(int left,int length)
{
     if(length==1)
     {
          seg_tree[left][1]=w[left];
          return;
     }
     dfs(left,length/2);
     dfs(left+length/2,length-length/2);
     seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值
}
//在区间[s_left,s_len]搜索区间[left,length]的最小值
int search_min(int s_left,int s_len,int left,int length)
{
     if((s_left==left)&&(s_len==length))
          return seg_tree[s_left][s_len];
     if((left+length-1)<(s_left+s_len/2))//全在左半部分
     {
          return search_min(s_left,s_len/2,left,length);
     }
     else if(left>=(s_left+s_len/2))//全在右半部分
     {
          return search_min(s_left+s_len/2,s_len-s_len/2,left,length);
     }
     else//左右分开搜索
     {
          int left_len=s_left+s_len/2-left;
          int right_len=length-left_len;
          int min_left=search_min(s_left,s_len/2,left,left_len);
          int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len);
          return get_min(min_left,min_right);
     }
}
//从区间[s_left,s_len]开始更新下标pos的值为value
void update(int s_left,int s_len,int pos,int value)
{
     if((s_left==pos)&&(s_len==1))
     {
          seg_tree[s_left][1]=value;
          return ;
     }
     int mid=s_left+s_len/2;
     if(pos<mid)
          update(s_left,s_len/2,pos,value);
     else
          update(mid,s_len-s_len/2,pos,value);
     seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     for(int i=1;i<=n;i++)
          cin>>w[i];
     dfs(1,n);
     cin>>m;
     int p,l,r;
     for(int i=0;i<m;i++)
     {
          cin>>p>>l>>r;
          if(p==0)//查询
          {
               cout<<search_min(1,n,l,r-l+1)<<endl;
          }
          else//修改
          {
               update(1,n,l,r);
          }
     }
     return 0;
}

本代码提交AC,用时151MS,内存42MB。

hihoCoder 1050-树中的最长路

hihoCoder 1050-树中的最长路
#1050 : 树中的最长路
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。
但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手中的这棵玩具树现在由N个小球和N-1根木棍拼凑而成,这N个小球都被小Ho标上了不同的数字,并且这些数字都是出于1..N的范围之内,每根木棍都连接着两个不同的小球,并且保证任意两个小球间都不存在两条不同的路径可以互相到达。总而言之,是一个相当好玩的玩具啦!
但是小Hi瞧见小Ho这个样子,觉得他这样沉迷其中并不是一件好事,于是寻思着再找点问题让他来思考思考——不过以小Hi的水准,自然是手到擒来啦!
于是这天食过早饭后,小Hi便对着又拿着树玩具玩的不亦乐乎的小Ho道:“你说你天天玩这个东西,我就问你一个问题,看看你可否知道?”
“不好!”小Ho想都不想的拒绝了。
“那你就继续玩吧,一会回国的时候我不叫上你了~”小Hi严肃道。
“诶!别别别,你说你说,我听着呢。”一向习惯于开启跟随模式的小Ho忍不住了,马上喊道。
小Hi满意的点了点头,随即说道:“这才对嘛,我的问题很简单,就是——你这棵树中哪两个结点之间的距离最长?当然,这里的距离是指从一个结点走到另一个结点经过的木棍数。”。
“啊?”小Ho低头看了看手里的玩具树,困惑了。
提示一:路总有折点,路径也不例外!
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第一行为一个整数N,意义如前文所述。
每组测试数据的第2~N行,每行分别描述一根木棍,其中第i+1行为两个整数Ai,Bi,表示第i根木棍连接的两个小球的编号。
对于20%的数据,满足N<=10。
对于50%的数据,满足N<=10^3。
对于100%的数据,满足N<=10^5,1<=Ai<=N, 1<=Bi<=N
小Hi的Tip:那些用数组存储树边的记得要开两倍大小哦!
输出
对于每组测试数据,输出一个整数Ans,表示给出的这棵树中距离最远的两个结点之间相隔的距离。
样例输入
8
1 2
1 3
1 4
4 5
3 6
6 7
7 8
样例输出
6


本题要求一棵树中相距最远两点之间的距离,也就是`树的直径`。
求树的直径有多种方法,我这里介绍两种。
第一种方法
第一种方法很好理解,我们随机的从某个节点s对树深度优先遍历(广度优先遍历也行),找到深度最大的叶子节点node1;然后再从node1点对树DFS,找到深度最大的叶子节点node2;则node1和node2即为这棵树中相距最远的两个点,它们之间的距离即为树的直径。
关于这种方法的简要证明,可以看这篇博客
这种方法简单易懂,可以很快的写出代码,如下:

#include<iostream>
#include<vector>
using namespace std;
const int MAX_N=1e5+2;
int n;//节点数
int longest;//最远距离
int node1,node2;//node1,node2分别为为第一、二次DFS找到的最远点
vector<vector<int> > f_s(MAX_N);//father-son和son-father关系,存储双边
//参数分别为当前节点,深度,父亲节点
void dfs(int root,int depth,int father)
{
     if(depth>longest)//更新
     {
          longest=depth;
          node1=root;
     }
     int sons=f_s[root].size();
     for(int i=0;i<sons;i++)
     {
          if(f_s[root][i]!=father)//不能回溯
               dfs(f_s[root][i],depth+1,root);
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     int a,b;
     for(int i=0;i<n-1;i++)
     {
          cin>>a>>b;
          f_s[a].push_back(b);//记录双边关系
          f_s[b].push_back(a);//记录双边关系
     }
     longest=0;
     dfs(1,0,-1);//随机选一个点(1)找到第一个最远点node1
     longest=0;
     dfs(node1,0,-1);//以node1找第二个最远点node2,则node1到node2即为整棵树的直径
     cout<<longest;
     return 0;
}

本代码提交AC,用时255MS,内存9MB。
有一点需要提醒的是,因为不仅需要从s开始DFS,还需要从node1开始DFS,所以需要存储双向边,即不仅要存储(v,u),还需要存储(u,v);这样存了之后,为了防止DFS时回溯到父节点造成死循环,在DFS时要判断下一个节点是不是父节点,如果是则不继续DFS。
第二种方法
第一种方法虽然简单易懂,但不是hiho题目中给出的方法,那么hiho给出的又是什么方法呢?且看官方提示:

“没错,我枚举每一个点作为转折点t,求出以t为根节点的子树中的‘最长路’以及与‘最长路’不重合的‘次长路’,用这两条路的长度之和去更新答案,那么最终的答案就是这棵树的最长路长度了!”小Hi道。
“原来是这样,也就是说我只要以类似后序遍历的方式依次访问每个结点,从下往上依次计算每个结点的first值和second值,我就能够用O(N)的时间复杂度来解决这个问题咯!”

这提示的第一句话我倒是理解了,但是第二句一直不懂,为什么只要O(N)就可以解决问题呢。不管了,先看看只用第一句话能否AC吧。
我一开始的理解是这样的:尝试枚举每一个点为树的根节点t,然后从t开始DFS,找到以t为根的树的最长路径和次长路径(最长和次长路径不能有重复边),然后把他们加起来就是以t为根节点的树找到最长路径,而且这条最长路径肯定经过了根节点t。
比如样例输入,分别以节点1、2、3为根构成的树如下:

因为我们默认以t为根的树的最长路径一定经过节点t,所以上图最长路径分别为图中红色路线所示,长度分别为6,5,6(因为节点1和3都在最长路径上,所以他们求得的最长路径相等)。同理我们还可以求出以4,5...n为根(路径转折点)的最长路径,最后求这些最长路径中的最大值。
这个版本的代码如下:

#include<iostream>
#include<vector>
using namespace std;
const int MAX_N=1e5+2;
int n;//节点数
vector<vector<int> > f_s(MAX_N);//father-son和son-father关系,存储双边
vector<int> first,second;//first[i]和second[i]分别表示以i节点为根节点时(i节点以下构成的子树)的最大和次大长度
//参数分别为当前节点,父亲节点
void dfs(int root,int father)
{
     int sons=f_s[root].size();
     for(int i=0;i<sons;i++)
     {
          if(f_s[root][i]!=father)//不能回溯
          {
               dfs(f_s[root][i],root);
               if(first[f_s[root][i]]+1>first[root])
               {
                    second[root]=first[root];
                    first[root]=first[f_s[root][i]]+1;
               }
               else if(first[f_s[root][i]]+1>second[root])
                    second[root]=first[f_s[root][i]]+1;
          }
     }
}
void init_first_second()
{
     first.clear();
     first.assign(n+1,0);
     second.clear();
     second.assign(n+1,0);
}
int main()
{
     freopen("input.txt","r",stdin);
     cin>>n;
     int a,b;
     for(int i=0;i<n-1;i++)
     {
          cin>>a>>b;
          f_s[a].push_back(b);//记录双边关系
          f_s[b].push_back(a);//记录双边关系
     }
     int ans=0;
     for(int i=1;i<=n;i++)//枚举每一个节点为根节点(转折点)
     {
          init_first_second();
          dfs(i,-1);
          if(first[i]+second[i]>ans)
               ans=first[i]+second[i];
     }
     cout<<ans;
     return 0;
}

但是很遗憾,提交后TLE。
后来我仔细想了想,无论我们从哪个点s开始对树DFS,我们求得的first[i]和second[i]都是以点i为根构成的子树中它的最长和次长距离,那么first[i]+second[i]不就代表了从i开始DFS时得到的最长距离吗?比如图中以2为根的树中,我们在DFS的过程中肯定已经求到了first[1]和second[1],然后才能求first[2]和second[2],而这里的first[1]和second[2]和图中以1为根时求得的first[1]和second[1]是完全一样的。而对于以3为根的树,因为3正好在最长路径上,所以这里的first[1]和second[1]要小于前面两种情况,但是first[3]+second[3]和前面两种情况的first[1]+second[1]是相等的。
说了这么多,不知道同学们有没有发现,不管从哪个点开始DFS,只要一遍DFS结束,最长路径总会出现在某个first[i]+second[i]中。
至此,可以省略上一个版本中的for循环,只要一个DFS即可:

#include<iostream>
#include<vector>
using namespace std;
const int MAX_N=1e5+2;
int n;//节点数
vector<vector<int> > f_s(MAX_N);//father-son和son-father关系,存储双边
vector<int> first,second;//first[i]和second[i]分别表示以i节点为根节点时(i节点以下构成的子树)的最大和次大长度
int longest=0;//最终结果
//参数分别为当前节点,父亲节点
void dfs(int root,int father)
{
     int sons=f_s[root].size();
     for(int i=0;i<sons;i++)
     {
          if(f_s[root][i]!=father)//不能回溯
          {
               dfs(f_s[root][i],root);
               if(first[f_s[root][i]]+1>first[root])//更新最大和次大
               {
                    second[root]=first[root];
                    first[root]=first[f_s[root][i]]+1;
               }
               else if(first[f_s[root][i]]+1>second[root])//只更新次大
                    second[root]=first[f_s[root][i]]+1;
          }
     }
     if(first[root]+second[root]>longest)//更新全局最大
          longest=first[root]+second[root];
}
void init_first_second()
{
     first.assign(n+1,0);
     second.assign(n+1,0);
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     int a,b;
     for(int i=0;i<n-1;i++)
     {
          cin>>a>>b;
          f_s[a].push_back(b);//记录双边关系
          f_s[b].push_back(a);//记录双边关系
     }
     init_first_second();
     dfs(1,-1);//使用任意一个节点DFS,结果都是一样的。
     /*int ans=0;
     for(int i=1;i<=n;i++)//该循环可在DFS时完成
     {
          if(first[i]+second[i]>ans)
               ans=first[i]+second[i];
     }*/
     cout<<longest;
     return 0;
}

本代码提交AC,用时224MS,内存9MB。
第二种方法不太好理解,所以还是建议大家用第一种方法。
网上关于树的直径介绍了3种方法,可以参考这篇文章

hihoCoder 1069-最近公共祖先·三

hihoCoder 1069-最近公共祖先·三
#1069 : 最近公共祖先·三
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上上回说到,小Hi和小Ho使用了Tarjan算法来优化了他们的“最近公共祖先”网站,但是很快这样一个离线算法就出现了问题:如果只有一个人提出了询问,那么小Hi和小Ho很难决定到底是针对这个询问就直接进行计算还是等待一定数量的询问一起计算。毕竟无论是一个询问还是很多个询问,使用离线算法都是只需要做一次深度优先搜索就可以了的。
那么问题就来了,如果每次计算都只针对一个询问进行的话,那么这样的算法事实上还不如使用最开始的朴素算法呢!但是如果每次要等上很多人一起的话,因为说不准什么时候才能够凑够人——所以事实上有可能要等上很久很久才能够进行一次计算,实际上也是很慢的!
“那到底要怎么办呢?在等到10分钟,或者凑够一定数量的人两个条件满足一个时就进行运算?”小Ho想出了一个折衷的办法。
“哪有这么麻烦!别忘了和离线算法相对应的可是有一个叫做在线算法的东西呢!”小Hi笑道。
小Ho面临的问题还是和之前一样:假设现在小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁?
提示:最近公共祖先无非就是两点连通路径上高度最小的点嘛!
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,且每个输入文件中第一个出现的名字所确定的人是其他所有人的公共祖先。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。
样例输入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin
样例输出
Sam
Adam
Adam


这应该是最近公共祖先的最后一种算法了吧,hihoCoder还真是循序渐进啊,昨天刚刚学了RMQ-ST算法hihoCoder Problem 1068: RMQ-ST 算法,今天就用上了。
本题的解题思路也是非常的赞,首先把族谱树结构展开成一个数组B,当询问a,b节点的最近公共祖先时,在B中找到a,b最后出现的位置(也就是离开a,b节点的时候)an,bn,在区间[an,bn]上利用RMQ-ST算法求解区间深度最小的节点c,则c即为a,b的最近公共祖先,下面来具体讲解。
将族谱树展开成一个数组
为了利用RMQ-ST算法,需要将树形结构展开成一个数组,展开的方式是深度优先遍历树,将访问的节点顺序记录下来,不管是进入这个节点还是离开这个节点,都需要记录下来。比如下面一棵树:

是样例输入构成的一个家谱树,我们常规DFS这个树的序列是这样的:ASJMK。但是本题在进入和离开某个节点时都需要记录下来,而且每访问完一个子节点,要访问下一个子节点时,也需要记录当前父节点。比如访问完J准备访问M时,需要记录S,由此形成的序列为:ASJSMSAKA。
DFS生成的数组B长度大概为边数的两倍,所以复杂度级别只是O(n)的。
DFS之后就把树转换为了数组B[],因为使用RMQ-ST算法需要求某个区间的最小深度节点,所以在DFS的时候还需要记录每个节点的深度信息,而且还要记录每个节点最后访问的下标,这两点都不难,大家直接看代码即可。
RMQ-ST算法
得到数组B后就好办了,可以利用昨天学习的RMQ-ST算法求解2的幂区间长度间深度最小的节点,不过因为我们这题最终输出的是节点的名字而不是节点的深度,所以RMQ-ST比较的是深度,但存储的是节点名。
观察RMQ-ST算法的二重循环知道其复杂度为O(nlgn)。
在线求解
一切准备就绪后就可以求解了,首先根据字符串名字找到对应数字序号,然后查看两节点最后出现在树中的下标l,r,再讲[l,r]区间分成能覆盖[l,r]的2的幂的长度的半区间[l,t]和[t+1,r],最后求这两个区间最小深度的节点,输出其名称。
完整代码如下:

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int n,m,k;//k全部记录将树转换成数组tree[]是的下标,转换结束时k即为tree[]的长度
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
int tree[2*MAX_N];//DFS将树转换为的数组
int depth[MAX_N];//每个点在树中的深度
int rmq[MAX_N][30];//区间深度最低值
int last_show[MAX_N];//某个元素最后出现在tree中的位置(下标)
//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}
//深度遍历树
void DFS(int root,int deep)
{
     tree[k++]=root;//进入即记录
     depth[root]=deep;//记录深度
     int sons=f_s[root].size();
     for(int i=0;i<sons;i++)
     {
          DFS(f_s[root][i],deep+1);
          tree[k++]=root;//每返回一次都要记录一次根节点
     }
     last_show[root]=k-1;//root节点最后出现的位置
}
//求a,b最小值
inline int get_min(int a,int b)
{
     return a<b?a:b;
}
void init_rmq()
{
     for(int j=0;j<k;j++)
          //rmq[j][0]=depth[tree[j]];
          rmq[j][0]=tree[j];//保存的是这个节点,而不是它的深度,方便最后输出
     int q=floor(log((double)k)/log(2.0));
     for(int i=1;i<=q;i++)
     {
          for(int j=k-1;j>=0;j--)
          {
               rmq[j][i]=rmq[j][i-1];
               if(j+(1<<(i-1))<k)
               {
                    if(depth[rmq[j+(1<<(i-1))][i-1]]<depth[rmq[j][i]])//+优先级高于<<,所以改j+1<<(i-1)为j+(1<<(i-1))
                         rmq[j][i]=rmq[j+(1<<(i-1))][i-1];
               }
                    //rmq[j][i]=get_min(rmq[j][i],rmq[j+1<<(i-1)][i-1]);
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     string name1,name2;
     int index1,index2;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
     }
     k=0;//开始时树的下标为0,DFS完之后正好是tree[]数组的长度,可以作为rmq-st的n
     DFS(0,0);
     init_rmq();
     cin>>m;
     int l,r,t;
     while(m--)
     {
          cin>>name1>>name2;
          if(name1==name2)
          {
               cout<<name1<<endl;
               continue;
          }
          index1=store_name(name1);
          index2=store_name(name2);
          l=last_show[index1];
          r=last_show[index2];
          if(l>r)//保证l<=r
          {
               int tmp=r;
               r=l;
               l=tmp;
          }
          t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
          cout<<index_name[get_min(rmq[l][t],rmq[r-(1<<t)+1][t])]<<endl;//r-(1<<t)+1,记得+1
     }
     return 0;
}

本代码提交AC,用时202MS,内存8MB。
相比于hihoCoder Problem 1067: 最近公共祖先·二,本题的的DFS+RMQ-ST算法是在线算法,也就是每来一个询问可以立即回答,而且复杂度为O(nlgn)还不错。
至此,hihoCoder的最近公共祖先问题完整结束,共使用三种算法,后两种算法都利用DFS,阅读时可以互相参照:最近公共祖先问题

hihoCoder 1068-RMQ-ST算法

hihoCoder 1068-RMQ-ST算法
#1068 : RMQ-ST算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。
但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。
(虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!)
提示一:二分法是宇宙至强之法!(真的么?)
提示二:线段树不也是二分法么?
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。
每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。
对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,0<weight_i<=10^4。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。
样例输入
10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10
样例输出
1640
981
1556
981
981


给出n个数字,连续q次问[l,r]区间的最小值是多少。如果每询问一次都用遍历的方式求最小值,则总的时间复杂度为O(nq)。
本题给出了一个新的算法--RMQ-ST算法,它的时间复杂度为O(nlogn+q),如果q很大,比如接近n时,RMQ-ST算法就有优势了。
RMQ-ST算法的基本思想是先计算某个小区间a的最小值,当需要计算大区间b的最小值时,把它分成两个小区间a1,a2,因为小区间的最小值之前已经计算出来了,也就是a1,a2已知,则b=min{a1,a2}。这样每次询问[l,r]区间的最小值时,我们也只需要把[l,r]分成两个[l,t]和[t+1,r]区间,取这两个区间最小值的最小值,这样的时间复杂度是O(1)。
所以关键就在于怎么求所有小区间的最小值。
根据提示,为了简便,我们只求2的幂的长度区间的最小值,设数组int pre_calc[i][j]为区间[i,i+2^j-1]的最小值(从i开始,长度为2^j的区间最小值),因为长度为1的区间的最小值就是其本身,所以有pre_calc[i][0]=weight[i]。
因为pre_calc[i][j]的长度为2^j,所以我们正好可以将其分成2个长度为2^(j-1)的区间,也就是说pre_calc[i][j]=min{pre_calc[i][j-1],pre[i+2^(j-1)][j-1]}。
这样我们就找到了pre_calc的递推公式(实质是DP里的状态转换方程),那么j的取值范围是怎样的呢?因为长度为n的数组其最大子区间长度就是n,所以j的最大值就是log(n),下面只需一个二重循环就可求解。
当来了一个询问[l,r]时,我们也需要将其分成两个长度为2的幂的子区间a和b,假设这个幂为t,为了使两个子区间完全覆盖[l,r],两个子区间甚至可以重叠,所以a的右边缘需要大于等于b的左边缘,即l+2^t>=r-2^t+1,得到t>=log(r-l+1)-1,所以我们可以取t=log(r-l+1)。
完整代码如下:

#include<stdio.h>
#include<math.h>
#define MAX_N 1000010
int n,q;
int weight[MAX_N];
int pre_calc[MAX_N][30];
//求a,b最小值
int get_min(int a,int b)
{
     return a<b?a:b;
}
//初始化
void init_pre()
{
     for(int j=1;j<=n;j++)
          pre_calc[j][0]=weight[j];
     int m=floor(log((double)n)/log(2.0));//指数最大值
     for(int i=1;i<=m;i++)
     {
          for(int j=n;j>0;j--)
          {
               pre_calc[j][i]=pre_calc[j][i-1];
               if(j+(1<<(i-1))<=n)//如果另一半也存在的话。//1<<(i-1)其实就是2^(i-1)
                    pre_calc[j][i]=get_min(pre_calc[j][i],pre_calc[j+(1<<(i-1))][i-1]);
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     scanf("%d",&n);
     for(int i=1;i<=n;i++)
          scanf("%d",&weight[i]);
     init_pre();
     scanf("%d",&q);
     int l,r,t;
     while(q--)
     {
          scanf("%d%d",&l,&r);
          t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
          printf("%d\n",get_min(pre_calc[l][t],pre_calc[r-(1<<t)+1][t]));
     }
     return 0;
}

代码中求pre_calc时需要注意二重循环的顺序不要搞反了,因为我们是先求得小区间的最小值才能求大区间的最小值,所以第一重循环应该是区间的长度,而不是区间的起点。
本代码提交AC,用时875MS,内存138MB。(用cin,cout超时。。。)
这篇文章介绍了用RMQ-ST算法求解区间最大值和最小值的方法。

POJ 1163-The Triangle

POJ 1163-The Triangle
The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 38525 Accepted: 23126
Description

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
IOI 1994


DP水题一个,如果将等边三角形转换成Sample Input里的等腰直角三角形,设则某一点的路径和为sum[i][j],则因为只能从(i-1,j)和(i-1,j-1)这两个点到达(i,j),所以sum[i][j]=max{sum[i-1][j],sum[i-1][j-1]}+triangle[i][j]。如果为了节省空间,j可以从i downto 0循环,也就是DP表从右往左填,这样只需要一行空间。
不多说,简单题,直接上代码。

#include<iostream>
using namespace std;
const int MAX_N=101;
int triangle[MAX_N][MAX_N];
int sum[MAX_N]={0};
int DP(int n)
{
     int rs=0;
     for(int i=0;i<n;i++)
     {
          for(int j=i;j>=0;j--)//从右往左填表,只需一行空间
          {
               if(j>0)
               {
                    sum[j]=(sum[j]>sum[j-1]?sum[j]:sum[j-1])+triangle[i][j];
               }
               else if(j==0)
               {
                    sum[j]+=triangle[i][j];
               }
               if(sum[j]>rs)//记录最大值
                    rs=sum[j];
          }
     }
     /*int rs=0;
     for(int i=0;i<n;i++)
          if(sum[i]>rs)
               rs=sum[i];*/
     return rs;
}
int main()
{
     //freopen("input.txt","r",stdin);
     int n;
     cin>>n;
     for(int i=0;i<n;i++)
          for(int j=0;j<=i;j++)
               cin>>triangle[i][j];
     cout<<DP(n);
     return 0;
}

本代码提交AC,用时0MS,内存260K。