10
21
2013
2

【BZOJ2697】特技飞行【贪心】

开始以为是DP,但是仔细一想,动作k创造的价格只取决于它第一次出现的时间Sk和最后一次出现的时间Ek,则它创造的价值只可能为(Ek+Sk)*Ck。所以我们每次找最大价值的动作放在两侧直到放不下为止。

program p2697;
	var
		x:array[1..500] of longint;
		i,j,k,n,k1,max,where,tot:longint;
	begin
		readln(n,k);
		for i:=1 to k do
			read(x[i]);
		k1:=n+1; tot:=0;
		for i:=1 to k do begin
			k1:=k1-2;
			if k1<=0 then break;
			max:=-1;
			for j:=1 to k do
				if max<x[j] then begin
					max:=x[j]; where:=j;
				end;
			x[where]:=-1; tot:=tot+k1*max;
		end;
		writeln(tot);
	end.
Category: 贪心 | Tags:
10
21
2013
0

【BZOJ3280】小R的烦恼【费用流】

类似于那道BZOJ1221软件开发,把每天拆成两个,分别记为Xi,Yi,从S向Yi连一条流量Ai,费用为0的边。从Yi向Yi+1连一条流量maxint。对于每一个医院从Yi向Xi+Dk+1连一条流量为maxint,费用为Qk的边。从Xi向T连一条流量为k,费用为0的边。再对于每个大学都建一个节点Mi,从Mi向X1连一条流量为maxint,费用为Pi的边,从S向Mi连一条流量为Li,费用为0的边。这个网络的最小费用最大流的费用就是答案。开始数组开太大,估计是fillchar花了太多时间就T了。后来把数组改小就A了。

program p3280;
    const
        maxn=1000000000;
		modd=100000;
    type
        bian=record
            next,point,w,f:longint;
        end;
    var
		ii,t,tt,i,j,n,m,k,len,totpoint,totflow,totw,totnum:longint;
        a,l,pp,q,d:array[1..10000] of longint;
        b:array[0..200000] of bian;
        p,after,dis:array[0..10000] of longint;
        x:array[1..100000] of longint;
        pd:array[0..10000] of boolean;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    procedure ade(k1,k2,k3,k4:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].f:=k3;
            b[len].w:=k4;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3,k4:longint);
        begin
            ade(k1,k2,k3,k4);
            ade(k2,k1,0,-k4);
        end;
    function spfa:boolean;
        var
            head,i,j,now:longint;
        begin
            fillchar(x,sizeof(x),0);
            fillchar(pd,sizeof(pd),false);
            fillchar(dis,sizeof(dis),$3f);
            fillchar(after,sizeof(after),-1);
            x[1]:=0; head:=1; now:=0; pd[0]:=true; dis[0]:=0;
            while head<>now do begin
                now:=now mod modd+1;
                i:=p[x[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (b[i].f>0) and (b[i].w+dis[x[now]]<dis[j]) then begin
                        dis[j]:=b[i].w+dis[x[now]];
                        after[j]:=i;
                        if pd[j]=false then begin
                            pd[j]:=true;
                            head:=head mod modd+1;
                            x[head]:=j;
                        end;
                    end;
                    i:=b[i].next;
                end;
                pd[x[now]]:=false;
            end;
            if after[totpoint]>-1 then exit(true) else exit(false);
        end;
    function change:longint;
        var
            k,ans,tot,num,i,j:longint;
        begin
            i:=totpoint; j:=after[i]; k:=maxn;
            while j<>-1 do begin
                k:=min(k,b[j].f);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            ans:=0; i:=totpoint; j:=after[i];
            while j<>-1 do begin
                ans:=ans+k*b[j].w;
                dec(b[j].f,k);
                inc(b[j xor 1].f,k);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            totflow:=totflow+k;
            exit(ans);
        end;
    function dinic:longint;
        var
            ans:longint;
        begin
            ans:=0;
            while spfa do
                ans:=ans+change;
            exit(ans);
        end;
    begin
        readln(t);
        for tt:=1 to t do begin
            totnum:=0;
            readln(n,m,k);
            len:=-1;
            fillchar(p,sizeof(p),-1);
            fillchar(b,sizeof(b),0);
            for i:=1 to n do begin
                read(a[i]);
                totnum:=totnum+a[i];
            end;
            for i:=1 to m do
                read(l[i],pp[i]);
            for i:=1 to k do
                read(d[i],q[i]);
			for i:=m+1 to m+n-1 do
				add(i,i+1,maxn,0);
            for i:=1 to m do begin
                add(0,i,l[i],0);
				add(i,m+1,maxn,pp[i]);
            end;
            for i:=1 to n do begin
                add(0,i+n+m,a[i],0);
                for j:=1 to k do
                    if i+d[j]+1<=n then
						add(i+n+m,m+i+d[j]+1,maxn,q[j]);
            end;
            totpoint:=n+n+m+1;
            for i:=1 to n do
                add(m+i,totpoint,a[i],0);
            totflow:=0;
            totw:=dinic;
            if totflow<totnum then
                writeln('Case ',tt,': impossible')
            else
                writeln('Case ',tt,': ',totw);
        end;
    end.
Category: 费用流 | Tags:
10
21
2013
1

【BZOJ2190】【SDOI2008】仪仗队【欧拉函数】

线性筛一下欧拉函数,然后加起来×2加3即可。

program p2190;
	var
		x:array[1..400000] of boolean;
		prime,phi:array[1..400000] of longint;
		len,n,i,j,tot:longint;
	begin
		readln(n);
		dec(n);
		fillchar(x,sizeof(x),false);
		len:=0;
		for i:=2 to n do begin
			if x[i]=false then begin
				inc(len);
				phi[i]:=i-1;
				prime[len]:=i;
			end;
			j:=1;
			while (j<=len) and (prime[j]*i<=n) do begin
				x[i*prime[j]]:=true;
				if i mod prime[j]=0 then begin
					phi[prime[j]*i]:=phi[i]*prime[j]; break;
				end else
					phi[prime[j]*i]:=phi[i]*(prime[j]-1); 
				inc(j);
			end;
		end;
		tot:=0;
		for i:=1 to n do
			tot:=tot+phi[i];
		tot:=tot*2+3;
		writeln(tot);
	end.
Category: 欧拉函数 | Tags:
10
21
2013
0

【BZOJ1800】【Ahoi2009】fly 飞行棋【暴力】

看起来很神,看到数据范围就呵呵了。

program p1800;
	var
		x:array[1..4] of longint;
		d:array[1..20,1..20] of int64;
		i,j,n,tot:longint;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			if k2>4 then begin
				if (d[x[1],x[2]]=d[x[3],x[4]]) and (d[x[2],x[3]]=d[x[4],x[1]]) then
					inc(tot);
				exit;
			end;
			for i:=k1 to n do begin
				x[k2]:=i;
				dfs(i+1,k2+1);
			end;
		end;
	begin
		readln(n);
		for i:=1 to n do
			read(d[i,i mod n+1]);
		for i:=1 to n do begin
			j:=(i+1) mod n+1;
			while j<>i do begin
				d[i,j]:=d[i,(j-2+n) mod n+1]+d[(j-2+n) mod n+1,j];
				j:=j mod n+1;
			end;
		end;
		tot:=0;
		dfs(1,1);
		writeln(tot);
	end.
Category: 未分类 | Tags:
10
21
2013
0

【BZOJ2111】【ZJOI2010】Perm 排列计数【数学题】

先画成一个堆,然后就可以YY出递推式F[I]=F[I*2]*F[I*2+1]*C(C[I]-1,C[I*2]),C[I]是指以I为根的子树的节点个数,然后只需要把阶乘预处理出来,然后用逆元瞎搞搞就水过了。

program p2111;
	var
		c:array[0..2000000] of longint;
		x,num:array[0..2000000] of int64;
		i,j,n,q:longint;
	function quick(k1,k2:int64):int64;
		var
			i,j,tot:int64;
		begin
			i:=k2; j:=k1; tot:=1;
			while i<>0 do begin
				if i and 1=1 then
					tot:=tot*j mod q;
				i:=i shr 1; j:=j*j mod q;
			end;
			exit(tot);
		end;
	function dfs(k1:longint):int64;
		begin
			if num[c[k1]]<>-1 then exit(num[c[k1]]);
			if (c[k1]<=1) then begin
				num[c[k1]]:=1; exit(1);
			end;
			num[c[k1]]:=x[c[k1]-1]*quick(x[c[k1*2]],q-2) mod q*quick(x[c[k1]-1-c[k1*2]],q-2) mod q;
			num[c[k1]]:=num[c[k1]]*dfs(k1*2) mod q*dfs(k1*2+1) mod q;
			exit(num[c[k1]]);
		end;
	begin
		readln(n,q);
		fillchar(c,sizeof(c),0);
		fillchar(x,sizeof(x),0);
		for i:=n downto 2 do begin
			inc(c[i]);
			inc(c[i div 2],c[i]);
		end;
		inc(c[1]);
		fillchar(num,sizeof(num),-1);
		x[0]:=1; 
		for i:=1 to n do 
			x[i]:=x[i-1]*i mod q;
		writeln(dfs(1));
	end.
Category: 数学题 | Tags:
10
20
2013
0

【BZOJ3142】【Hnoi2013】数列【数学题】

YY一下就可以得到最后的答案(因为有些并一起啊什么的全部都喜闻乐见消掉)为N*M^(K-1)-M*(M+1)/2*M^(K-2)*(K-1),开始推了个式子貌似跪了,原因是中途要DIV个二好像有点问题,然后就索性重推了一遍。然后就A了,喜闻乐见。

 

program p3142;
	var
		n,m,k,p,i,j:int64;
	function quick(k1,k2:int64):int64;
		var
			i,j,k,tot:int64;
		begin
			k:=k1; j:=k2; tot:=1;
			while j<>0 do begin
				if j and 1<>0 then 
					tot:=tot*k mod p;
				j:=j shr 1; k:=k*k mod p;
			end;
			exit(tot);
		end;
	begin
		readln(n,k,m,p);
		dec(k);
		i:=quick(m,k-1); 
		writeln(int64(n mod p*m-m*(m+1) div 2 mod p*k+p*1000000000) mod p*i mod p);
	end.
Category: 数学题 | Tags:
10
16
2013
1

【BZOJ2007】【Noi2010】海拔【最小割+最短路】

语文挂科了,所以来除草了。

program p2007;

	type
		d=record
			w,po:int64;
		end;
		bian=record
			next,point,w:int64;
		end;
	var
		b:array[1..1000000] of bian;
		i,j,n,k1,k2,len:longint;
		x:array[1..1000000] of d;
		p,f:array[0..1000000] of int64;
		pd:array[0..1000000] of boolean;
		maxn:int64;
	procedure add(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].next:=p[k1];
			b[len].point:=k2;
			b[len].w:=k3;
			p[k1]:=len;
		end;
    function mi(k1,k2:longint):longint;
        begin
            if x[k1].w>x[k2].w then exit(k2) else exit(k1);
        end;
    function min(k1,k2,k3:longint):longint;
        begin
            exit(mi(mi(k1,k2),k3));
        end;
    procedure press(k:longint);
        var
            k1:longint;
            k2:d;
        begin
            k1:=min(k,k*2,k*2+1);
            if k1=k then exit;
            k2:=x[k1];
            x[k1]:=x[k];
            x[k]:=k2;
            press(k1);
        end;
    procedure find(k:longint);
        var
            k1:d;
        begin
            if k=1 then exit;
            if x[k div 2].w>x[k].w then begin
                k1:=x[k];
                x[k]:=x[k div 2];
                x[k div 2]:=k1;
                find(k div 2);
            end;
        end;
    function dijstra:longint;
        var
            k1,k2,k3,i,j,now,len:longint;
            k:d;
        begin
            fillchar(pd,sizeof(pd),true);
            fillchar(x,sizeof(x),$7f);
            maxn:=x[1].po; len:=1;
            fillchar(f,sizeof(f),$3f);
            x[1].po:=0; x[1].w:=0; f[0]:=0;
            while len>0 do begin
                len:=len-1;
                k:=x[1];
                if len>0 then begin
                    x[1]:=x[len+1];
                    x[len+1].w:=maxn;
                    press(1);
                end;
                if pd[k.po]=false then continue;
                pd[k.po]:=false;
                k2:=p[k.po];
                while k2>0 do begin
                    k1:=b[k2].point;
                    if f[k.po]+b[k2].w<f[k1] then begin
                        f[k1]:=f[k.po]+b[k2].w;
                        inc(len);
                        x[len].po:=k1; x[len].w:=f[k1];
                        find(len);
                    end;
                    k2:=b[k2].next;
                end;
            end;
            exit(f[n*n+1]);
        end;
	begin
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		len:=0;
		readln(n);
		for i:=1 to n+1 do
			for j:=1 to n do begin
				readln(k1);
				if i=1 then 
					add(j,n*n+1,k1)
				else if i=n+1 then
					add(0,n*(n-1)+j,k1)
				else add(n*(i-1)+j,n*(i-2)+j,k1);
			end;
		for i:=1 to n do begin
			readln(k1);
			add(0,n*i-n+1,k1);
			for j:=1 to n-1 do begin
				readln(k1);
				add(n*i-n+j,n*i-n+j+1,k1);
			end;
			readln(k1);
			add(n*i,n*n+1,k1);
		end;
		for i:=1 to n+1 do
			for j:=1 to n do begin
				readln(k1);
				if (i<>1) and (i<>n+1) then add(n*(i-2)+j,n*(i-1)+j,k1);
			end;
		for i:=1 to n do begin
			readln(k1);
			for j:=1 to n-1 do begin
				readln(k1);
				add(n*i-n+j+1,n*i-n+j,k1);
			end;
			readln(k1);
		end;
		fillchar(x,sizeof(x),$3f);
		fillchar(f,sizeof(f),$3f);
		maxn:=x[1].po;
		writeln(dijstra);
	end.

一眼就可以看出来是最小割,因为显而易见每个点的高度只可能是0或1,那么它们必有一个交接面,而这个就需要用最小割了。但是最小割会T80,所以要用对偶图+最短路来解决最小割问题,就如BZOJ1001。而这题恶心的把SPFA卡了,我又都比的把DJ+堆敲炸了,这道题就坑了我一个晚上QAQ(虽然有OSU和CS的因素)。

 

Category: 最短路 | Tags:
9
21
2013
0

【BZOJ2431】【HAOI2009】逆序对数列【DP】

O(NK^2)的算法是果果的,O(NK)的算法只要用一个TOT来计算前缀和就可以了,边界+-1搞了一会儿就A了。

program p2431;
	var
		x:array[0..1,0..1000] of longint;
		n,k,i,j,tot,k1,k2:longint;
	begin
		readln(n,k);
		fillchar(x,sizeof(x),0);
		x[0,0]:=1;
		for i:=1 to n do begin
			k1:=i mod 2; k2:=1-k1;
			x[k1,0]:=x[k2,0]; tot:=x[k2,0];
			for j:=1 to k do begin
				if j<i then tot:=(tot+x[k2,j]) mod 10000 else tot:=(tot-x[k2,j-i]+x[k2,j]+10000) mod 10000;
				x[k1,j]:=tot;
			end;
		end;
		writeln(x[k1,k]);
	end.
			
Category: DP | Tags:
9
20
2013
1

【BZOJ1007】【HNOI2008】水平可见直线【计算几何+栈】

我的第一道计算几何,OLE了好多次。先以A为第一关键字,B为第二关键字SORT一下。从小到大进栈,然后每次比较头三条直线L1,L2,L3如果L1L2交点不在L2L3交点之后则删除L2,再比较删除L2以后的头三条直线直到不满足条件或者无法再删除则停止。最后留在栈中的直线就是可以看见的直线。接下来是我惨烈无比的AC历程

program p1007;
	type
		line=record
			k,b:extended;
			num:longint;
		end;
	var
		x,s:array[0..50100] of line;
		pd:array[0..50100] of boolean;
		i,j,n,head:longint;
		k1,k2:extended;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[i];
			while i<j do begin
				while (i<j) and ((x[j].k>x[0].k) or ((x[j].k=x[0].k) and (x[j].b<x[0].b))) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and ((x[i].k<x[0].k) or ((x[i].k=x[0].k) and (x[i].b>x[0].b))) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	function find(k1,k2:line):extended;
		begin
			exit((k2.b-k1.b)/(k1.k-k2.k));
		end;
	begin
		readln(n);
		for i:=1 to n do begin
			readln(x[i].k,x[i].b);
			x[i].num:=i;
		end;
		sort(1,n);
		head:=0; 
		fillchar(pd,sizeof(pd),true);
		for i:=1 to n do begin
			if head=0 then begin
				inc(head); s[head]:=x[i]; continue;
			end;
			if (x[i].k=s[head].k)  then begin
				pd[x[i].num]:=false; continue;
			end;
			if head=1 then begin
				inc(head); s[head]:=x[i]; continue;
			end;
			while true do begin
				if head=1 then begin
					inc(head); s[head]:=x[i]; break;
				end;
				k1:=find(x[i],s[head]); k2:=find(s[head-1],s[head]);
				if k1<=k2 then begin
					pd[s[head].num]:=false; dec(head);
				end else begin
					inc(head); s[head]:=x[i]; break;
				end;
			end;
		end;
		for i:=1 to n do
			if pd[i]=true then write(i,' ');
	end.
Category: 计算几何 | Tags:
9
20
2013
0

【BZOJ2150】部落战争【网络流】

由于只能向下走,这样路线就不可能达成一个环,而且又鉴于每个点只能到达一遍,每一次的代价只存在于重设出发点,于是很容易的就想到了最小路径覆盖,赤果果的网络流。把每个节点拆成两个,i入和i出。如果i可以到达j,那么就连一条i出到j入的边,再由源向每一个出连一条边,由入向汇连一条边。上述边的流量都为1。答案就是总的点数减最大流。当然这道题也可以用匈牙利算法做。

program p03;
    type
        bian=record
            next,point,f:longint;
        end;
    var
        b:array[0..5000000] of bian;
        p,dst,s:array[0..500000] of longint;
        pd:array[0..500000] of boolean;
        bo:array[1..600,1..600] of boolean;
        tot,len,i,j,n,m,r,c:longint;
        ch:char;
    procedure getchar(var ch:char);
        begin
            read(ch);
            while (ch<>'.') and (ch<>'x')do
                read(ch);
        end;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function change(k1,k2:longint):longint;
        var
            i,j,k,num:longint;
        begin
            if (k1=n*m*2+1) or (k2=0) then exit(k2);
            num:=0;
            i:=p[k1];
            while i<>-1 do begin
                j:=b[i].point;
                if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
                    k:=change(j,min(k2,b[i].f));
                    k2:=k2-k; num:=num+k;
                    dec(b[i].f,k); inc(b[i xor 1].f,k);
                    if k2=0 then break;
                end;
                i:=b[i].next;
            end;
            if num=0 then dst[k1]:=-1;
            exit(num);
        end;
    function bfs:boolean;
        var
            i,j,head,now:longint;
        begin
            fillchar(dst,sizeof(dst),-1);
            fillchar(pd,sizeof(pd),false);
            head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
            while head>now do begin
                inc(now);
                i:=p[s[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (pd[j]=false) and (b[i].f>0) then begin
                        dst[j]:=dst[s[now]]+1;
                        pd[j]:=true;
                        if j=n*m*2+1 then exit(true);
                        inc(head);
                        s[head]:=j;
                    end;
                    i:=b[i].next;
                end;
            end;
            exit(pd[n*m*2+1]);
        end;
    procedure ade(k1,k2,k3:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].f:=k3;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3:longint);
        begin
            ade(k1,k2,k3);
            ade(k2,k1,0);
        end;
    function dinic:longint;
        var
            num:longint;
        begin
            num:=0;
            while bfs=true do
                num:=num+change(0,maxlongint);
            exit(num);
        end;
    begin
        readln(n,m,r,c);
        fillchar(p,sizeof(p),-1);
        fillchar(b,sizeof(b),0);
        len:=-1;
        for i:=1 to n do
            for j:=1 to m do begin
                getchar(ch);
                if ch='.' then bo[i,j]:=true else bo[i,j]:=false;
            end;
        for i:=1 to n do
            for j:=1 to m do begin
                if (i+c<=n) and (j+r<=m) and (bo[i,j]=true) and (bo[i+c,j+r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j+r+n*m,1);
                if (i+r<=n) and (j+c<=m) and (bo[i,j]=true) and (bo[i+r,j+c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j+c+n*m,1);
                if (i+c<=n) and (j-r>0) and (bo[i,j]=true) and (bo[i+c,j-r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j-r+n*m,1);
                if (i+r<=n) and (j-c>0) and (bo[i,j]=true) and (bo[i+r,j-c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j-c+n*m,1);
            end;
        tot:=0;
        for i:=1 to n do
            for j:=1 to m do
                if bo[i,j]=true then begin
                    inc(tot);
                    add(0,i*m-m+j,1);
                    add(i*m-m+j+n*m,n*m*2+1,1);
                end;
        writeln(tot-dinic);
    end.       
Category: 最大流 | Tags:

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