10
21
2013
0

【BZOJ1012】【JSOI2008】最大数maxnumber【倍增】

显然,如果使用倍增,用num[i,j]表示从i-2^j+1到i的所有数的最大值,则后面插入的数对前面插入的数是没有影响的。这样就可以使用倍增,插入和查找都是logn的复杂度,妥妥的。

program p1012;
	var
		num:array[1..200000,0..17] of int64;
		i,j:longint;
		m,d,k1,len,k2,now:int64;
		ch:char;
	function max(k1,k2:longint):longint;
		begin	
			if k1<k2 then exit(k2) else exit(k1);
		end;
	begin
		readln(m,d); k1:=0;
		fillchar(num,sizeof(num),$3f);
		for i:=1 to m do begin
			read(ch);
			if ch='A' then begin
				inc(len);
				readln(k2);
				k2:=(k2+k1) mod d;
				num[len,0]:=k2;
				for j:=1 to 17 do
					if 1 shl j<=len then
						num[len,j]:=max(num[len-1 shl (j-1),j-1],num[len,j-1])
					else break;
			end else begin
				readln(k2); k1:=0; now:=len;
				for j:=17 downto 0 do
					if k2 and (1 shl j)>0 then begin
						k1:=max(k1,num[now,j]);
						now:=now-(1 shl j);
					end;
				writeln(k1);
			end;
		end;
	end.
Category: 倍增 | Tags:
9
17
2013
1

【BZOJ3251】树上三角形【倍增】

显然我们要求出每个询问两个点的最近公共祖先。然后我们可以求出其最短路径上的点数。显然,如果要不能构成三角形,那么上面的点权一定是按照大于斐波那契数列排列的,这样在55项左右就超过MAXLONGINT。所以大于等于55一定构成三角形。余下的反正是有50+的点直接SORT一下然后暴力即可。PASCAL的代码又一次又臭又长,居然垫底了。。QAQ

program p3251;
	type
		bian=record
			next,point:int64;
		end;
		arr=array[0..500] of int64;
	var
		f:array[1..111111,0..17] of int64;
		w,d,p:array[1..111111] of int64;
		b:array[1..111111] of bian;
		way:arr;
		len,i,j,q,n,k1,k2,k3:longint;
		ch:char;
		pd:boolean;
	procedure add(k1,k2:int64);
		begin
			inc(len); 
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure find(k1,k2:int64);
		var
			i,j:longint;
		begin
			d[k1]:=k2;
			i:=p[k1];
			while i<>0 do begin
				find(b[i].point,k2+1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:int64):int64;
		var
			i,j,k:longint;
		begin
			if k2=0 then exit(k1);
			for k:=0 to 17 do
				if 1 shl k>k2 then break;
			dec(k);
			for i:=0 to k do 
				if k2 and (1 shl i)>0 then k1:=f[k1,i];
			exit(k1);
		end;
	procedure sort(var x:arr;first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				while (i<j) and (w[x[j]]>=w[x[0]]) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (w[x[i]]<w[x[0]]) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(x,first,i-1);
			if i<en-1 then sort(x,i+1,en);
		end;	
	function answer(k1,k2:int64):char;
		var
			k,i,j,k3,k4,k5,l:longint;
		begin
			if d[k1]>d[k2] then begin
				i:=k1; k1:=k2; k2:=i;
			end;
			k3:=go_up(k2,d[k2]-d[k1]);
			for k:=0 to 17 do
				if 1 shl k>=d[k3] then break;
			dec(k);
			k4:=k1;
			if k3<>k4 then begin
				for i:=k downto 0 do
					if f[k3,i]<>f[k4,i] then begin
						k3:=f[k3,i];
						k4:=f[k4,i];
					end;
				k3:=f[k3,0];
			end;
			l:=d[k1]-d[k3]+d[k2]-d[k3]+1;
			if (l<3) then exit('N');
			if (l>=55) then exit('Y');
			l:=0;
			i:=k1; 
			while i<>k3 do begin
				inc(l); way[l]:=i; i:=f[i,0];
			end;
			i:=k2; inc(l); way[l]:=i;
			while i<>k3 do begin
				i:=f[i,0]; inc(l); way[l]:=i;
			end;
			sort(way,1,l);
			for i:=3 to l do
				if w[way[i-2]]+w[way[i-1]]>w[way[i]] then exit('Y');
			exit('N');
		end;
	begin
		readln(n,q);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		fillchar(f,sizeof(f),0);
		for i:=1 to n do
			read(w[i]);
		for i:=1 to n-1 do begin
			readln(k1,k2);
			f[k2,0]:=k1;
			add(k1,k2);
		end;
		find(1,1);
		for i:=1 to 17 do begin
			pd:=false;
			for j:=1 to n do
				if 1 shl i<d[j] then begin
					pd:=true;
					f[j,i]:=f[f[j,i-1],i-1];
				end;
			if pd=false then break;
		end;
		for i:=1 to q do begin
			readln(k1,k2,k3);
			if k1=0 then
				writeln(answer(k2,k3))
			else 
				w[k2]:=k3;
		end;
	end.
Category: 倍增 | Tags:
8
27
2013
0

【BZOJ2783】【JLOI2012】树【倍增+二分】

很容易就可以想到时间复杂度为nlog2n的算法。即用类似于求最近公共祖先的预处理。令f[i][j]为i的第2j祖先。w[i][j]为i到f[i][j]路径不包括i的权值和。则可以得到递推式:f[i][j]=f[f[i,j-1]][j-1],w[i][j]=w[f[i,j-1]][j-1]+w[i][j-1]。然后对于节点i,二分路径向上走多少层,如果可以二分得到其路径权值和s恰好相等则方案数加一,不要忘了只有节点i的情况。速度比较慢,存在复杂度为nlogn的算法,但是要用set或者treap,这对于pascal党太痛苦了,所以上述方法简单实用!laugh

 

program p2783;
	type
		bian=record
			next,point:longint;
		end;
	var
		f,w:array[1..100000,0..25] of longint;
		d,x,p:array[0..100000] of longint;
		b:array[1..100000] of bian;
		l,r,mid,s,tot,len,n,i,j,k1,k2:longint;
		bo:boolean;
	procedure add(k1,k2:longint);
		begin
			inc(len);
			b[len].next:=p[k1];
			b[len].point:=k2;
			p[k1]:=len;
		end;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			f[k1,0]:=k2; d[k1]:=d[k2]+1;
			w[k1,0]:=x[k2];
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				dfs(j,k1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			for k:=1 to 30 do
				if 1 shl k>k2 then break;
			dec(k); j:=0;
			for i:=k downto 0 do
				if k2 and (1 shl i)>0 then begin
					j:=j+w[k1,i];
					k1:=f[k1,i];
				end;
			exit(j);
		end;
	begin
		readln(n,s);
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to n do
			read(x[i]);
		x[0]:=0;
		len:=0;
		for j:=1 to n-1 do begin
			readln(k1,k2);
			add(k1,k2);
		end;
		fillchar(d,sizeof(d),0);
		fillchar(f,sizeof(f),0);
		dfs(1,0);
		bo:=true; j:=0;
		while bo=true do begin
			inc(j);
			bo:=false;
			for i:=1 to n do begin
				if 1 shl j>=d[i] then continue;
				f[i,j]:=f[f[i,j-1],j-1];
				bo:=true;
				w[i,j]:=w[f[i,j-1],j-1]+w[i,j-1];
			end;
		end;
		tot:=0;
		for i:=1 to n do begin
			if x[i]=s then begin
				inc(tot);
				continue;
			end;
			l:=1; r:=d[i]; 
			while l<r do begin
				mid:=(l+r) div 2;
				k1:=go_up(i,mid)+x[i];
				if k1>s then r:=mid
					else if k1<s then l:=mid+1
						else begin
							inc(tot);
							break;
						end;
			end;
		end;
		writeln(tot);
	end.
Category: 倍增 | Tags:
8
27
2013
1

【BZOJ1787】【Ahoi2008】Meet 紧急集合【倍增(最近公共祖先)】

如果只有两个点,我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不TLE,需要用倍增算法来确保NLOGN时间复杂度的在线查询。

 

program p1787;
	type
		bian=record
			point,next:longint;
		end;
	var
		b:array[1..1000005] of bian;
		p,d:array[0..500005] of longint;
		f:array[1..500005,1..30] of longint;
		len,n,m,i,j,k1,k2,k3,w1,w2,w3:longint;
		extra:array[1..3,1..2] of longint;
		bo:boolean;
	procedure ade(k1,k2:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2:longint);
		begin
			ade(k1,k2);
			ade(k2,k1);
		end;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			d[k1]:=d[k2]+1;
			f[k1,0]:=k2;
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if j<>k2 then dfs(j,k1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			for k:=0 to 30 do
				if 1 shl k>k2 then break;
			dec(k); if k<0 then exit(k1);
			j:=k1;
			for i:=0 to k do
				if k2 and (1 shl i)>0 then
					j:=f[j,i];
			exit(j);
		end;
	function fcf(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			if d[k1]>d[k2] then begin
				i:=k1; k1:=k2; k2:=i;
			end;
			k2:=go_up(k2,d[k2]-d[k1]);
			if k1=k2 then exit(k1);
			for k:=1 to 30 do
				if 1 shl k>=d[k1] then break;
			dec(k);
			for i:=k downto 0 do
				if f[k1,i]<>f[k2,i] then begin
					k1:=f[k1,i]; k2:=f[k2,i];
				end;
			exit(f[k1,0]);
		end;
	function pay(k1,k2,k3:longint):longint;
		begin
			exit(d[k1]-d[k3]+d[k2]-d[k3]);
		end;
	begin
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		readln(n,m);
		len:=0;
		for i:=1 to n-1 do begin
			readln(k1,k2);
			add(k1,k2);
		end;
		fillchar(d,sizeof(d),0);
		fillchar(f,sizeof(f),0);
		d[0]:=0;
		dfs(1,0);
		j:=1; bo:=true;
		while bo=true do begin
			bo:=false;
			for i:=1 to n do begin
				if d[i]<=1 shl j then continue;
				f[i,j]:=f[f[i,j-1],j-1];
				bo:=true;
			end;
			inc(j);
		end;{
		for i:=0 to 3 do begin
			for j:=1 to n do
				write(f[j,i],' ');
			writeln;
		end;}
		for i:=1 to m do begin
			readln(k1,k2,k3);
			extra[1,1]:=fcf(k1,k2);
			extra[1,2]:=fcf(extra[1,1],k3);
			extra[2,1]:=fcf(k1,k3);
			extra[2,2]:=fcf(extra[2,1],k2);
			extra[3,1]:=fcf(k2,k3);
			extra[3,2]:=fcf(extra[3,1],k1);
			w1:=pay(k1,k2,extra[1,1])+pay(extra[1,1],k3,extra[1,2]);
			w2:=pay(k1,k3,extra[2,1])+pay(extra[2,1],k2,extra[2,2]);
			w3:=pay(k2,k3,extra[3,1])+pay(extra[3,1],k1,extra[3,2]);
			if w1<w2 then begin 
				k1:=extra[1,1]; k2:=w1;
			end else begin	
				k1:=extra[2,1]; k2:=w2;
			end;
			if k2>w3 then begin
				k1:=extra[3,1]; k2:=w3;
			end;
			{for j:=1 to 3 do
				writeln(extra[j,1],' ',extra[j,2]);
			writeln(w1,' ',w2,' ',w3);}
			writeln(k1,' ',k2);
		end;
	end.
Category: 倍增 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com