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:
9
18
2013
0

【BZOJ2819】Nim【树状数组+LCA+DFS序+手工栈+博弈论】

首先我不得不吐槽一下BZOJ,出这么一道pascal无解的题目有什么意思呢?我就算优化到极限pascal还是TLE,而C++一个复杂度比我没有花之前的程序居然11S就A了,C++秀优越也用不着这样啊。

先搞个DFS序,这样的话就可以用树状数组来维护了。最终的答案就是add_up(s[k1]) xor add_up(s[k2]) xor w[closefather(k1,k2)],s是dfs序中最先出现的位置,w是权值。最近公共祖先就用LCA搞掉。就如题目所说,这道题目要用手工栈,不然会在爆栈OJ爆栈。接下来是我无比惨烈的解题截图。(不要怪我没节操的贴了代码)

 


program p2819;
    type   
        bian=record
            next,point:longint;
        end;
    var
        y:array[1..500000,1..4] of longint;
        x:array[1..1000010] of longint;
        d,w,p,s,e:array[1..500010] of longint;
        f:array[1..500010,0..20] of longint;
        b:array[1..1000010] of bian;
        q,len,i,j,n,k1,k2:longint;
        ch:char;
        bo:boolean;
    function getchar:char;
        var
            ch:char;
        begin
            read(ch);
            while (ch<>'Q') and (ch<>'C') do
                read(ch);
            exit(ch);
        end;
    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 bfs;
        var
            i,j,head,now:longint;
        begin
            head:=1; now:=1; y[1,1]:=1; y[1,2]:=p[1]; y[1,3]:=0; y[1,4]:=1;
            d[1]:=1; f[1,0]:=0; s[1]:=1;
            while now>0 do begin
                i:=y[now,2];
                if (i<>0) and (b[i].point=y[now,3]) then i:=b[i].next;
                if (i=0) then begin
                    inc(head); e[y[now,1]]:=head;
                    dec(now);
                    continue;
                end;
                inc(now); y[now,1]:=b[i].point; y[now,2]:=p[y[now,1]]; y[now,3]:=y[now-1,1]; y[now,4]:=y[now-1,4]+1;
                inc(head); f[y[now,1],0]:=y[now,3]; s[y[now,1]]:=head; d[y[now,1]]:=y[now,4];
                y[now-1,2]:=b[i].next;
            end;
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure add_in(k1,k2:longint);
        var
            i,j:longint;
        begin
            i:=k1;
            while i<=1000010 do begin
                x[i]:=x[i] xor k2;
                i:=i+lowbit(i);
            end;
        end;
    function add_up(k:longint):longint;
        var
            i,num:longint;
        begin
            i:=k; num:=0;
            while i>0 do begin
                num:=num xor x[i];
                i:=i-lowbit(i);
            end;
            exit(num);
        end;
    function go_up(k1,k2:longint):longint;
        var
            i,j,k:longint;
        begin
            for k:=0 to 20 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 find(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 20 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;
    begin
        readln(n);
        for i:=1 to n do
            read(w[i]);
        len:=0;
        fillchar(p,sizeof(p),0);
        fillchar(b,sizeof(b),0);
        for i:=1 to n-1 do begin
            readln(k1,k2);
            add(k1,k2);
        end;
        fillchar(d,sizeof(d),0);
        len:=0;
        bfs;
        fillchar(x,sizeof(x),0);
        for i:=1 to n do begin
            add_in(s[i],w[i]);
            add_in(e[i],w[i]);
        end;
        for i:=1 to 20 do begin
            bo:=false;
            for j:=1 to n do
                if (1 shl i)<d[j] then begin
                    bo:=true; 
                    f[j,i]:=f[f[j,i-1],i-1];
                end;
            if bo=false then break;
        end;
        readln(q);
        for i:=1 to q do begin
            ch:=getchar;
            if ch='Q' then begin
                readln(k1,k2);
                j:=add_up(s[k1]) xor add_up(s[k2]) xor w[find(k1,k2)];
                if j=0 then writeln('No') else writeln('Yes');
            end else begin
                readln(k1,k2);
                add_in(s[k1],w[k1]); add_in(e[k1],w[k1]);
                add_in(s[k1],k2); add_in(e[k1],k2);
                w[k1]:=k2;
            end;
        end;
    end.
Category: 数据结构 | Tags:
9
18
2013
0

【BZOJ3275】Number【最小割】

开始把题目看错了,然后就在纠结要不要拆点。后来仔细一看,发现是‘同时满足’,然后便是赤果果的最小割了。把所有数分成奇数和偶数两组,因为奇数之间不满足1,偶数之间不满足2.然后从源点向偶数连流量为其大小的边,从奇数向汇连流量为其大小的边。如果奇数和偶数之间不能同时选那么就连一条流量无穷大的边。这样做出来的最小割满足矛盾的点对中只选一个,而且其流量就是要舍弃的数字的大小和。于是乎我们用总权值把最小割减减掉即可。

 

program p3275;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		b:array[0..500000] of bian;
		p,dst,x,s:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		len,n,i,j,tot:longint;
	function gcd(k1,k2:longint):longint;
		begin
			if k2=0 then exit(k1);
			exit(gcd(k2,k1 mod k2));
		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+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+1 then exit(true);
						inc(head);
						s[head]:=j;
					end;
					i:=b[i].next;
				end;
			end;
			exit(pd[n+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
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		readln(n);
		tot:=0;
		for i:=1 to n do begin
			read(x[i]);
			tot:=tot+x[i];
		end;
		for i:=1 to n do 
			for j:=1 to n do
				if (x[i] mod 2=0) and (x[j] mod 2=1) and (trunc(sqrt(x[i]*x[i]+x[j]*x[j]))=sqrt(x[i]*x[i]+x[j]*x[j])) and (gcd(x[i],x[j])=1) then
					add(i,j,maxlongint);
		for i:=1 to n do 
			if x[i] mod 2=0 then add(0,i,x[i]) else add(i,n+1,x[i]);
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags:
9
17
2013
0

【BZOJ3132】上帝造题的七分钟【二维树状数组】

这道题是对pascal赤果果的鄙视。。。pascal在tyvj上AC了在BZ上WA。要来数据在CENA上AC了再BZ上接着WA。网上抄来PASCAL标程还TM的WA。最后怒了贴个C++结果A了。。。QAQ

二维树状数组的矩形修改和查找。令D[X,Y]表示在矩形(X,Y)(N,M)上加上D[X,Y]。则点(X,Y)的权值就是SIGMA(D(I,J))。然后就瞎搞搞,维护D[X,Y],D[X,Y]*X,D[X,Y]*Y,D[X,Y]*X*Y。然后就可以了。

代码依然PASCAL。我是P党我骄傲

 

program p3132;
    type
        arr=array[0..2050,0..2050] of longint;
    var
        i,j,n,m,k1,k2,k3,k4,k5:longint;
        a,b,c,d:arr;
        ch:char;
    procedure getchar(var k:char);
        begin
            read(k);
            while ((k<'A') or (k>'Z')) and ((k<'a') or (k>'z'))do
                read(k);
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure add(var x:arr;k1,k2,k3:longint);
        var
            i,j:longint;
        begin
            i:=k1; 
            while i<=n do begin
                j:=k2;
                while j<=m do begin
                    x[i,j]:=x[i,j]+k3;
                    j:=j+lowbit(j);
                end;
                i:=i+lowbit(i);
            end;
        end;
    function find(var x:arr;k1,k2:longint):longint;
        var
            i,j,num:longint;
        begin
            i:=k1; num:=0;
            while i>0 do begin
                j:=k2;
                while j>0 do begin
                    num:=num+x[i,j];
                    j:=j-lowbit(j);
                end;
                i:=i-lowbit(i);
            end;
            exit(num);
        end;
    function findtotal(k1,k2:longint):longint;
        begin
            exit((k1+1)*(k2+1)*find(a,k1,k2) - (k1+1)*find(b,k1,k2) - (k2+1)*find(c,k1,k2) + find(d,k1,k2));
        end;
    procedure addtotal(k1,k2,k3,k4,k5:longint); 
        begin
            add(a,k1,k4,k5); add(a,k1,k2+1,-k5); add(a,k3+1,k4,-k5); add(a,k3+1,k2+1,k5);
            add(b,k1,k4,k5*k4); add(b,k1,k2+1,-k5*(k2+1)); add(b,k3+1,k4,-k5*k4); add(b,k3+1,k2+1,k5*(k2+1));
            add(c,k1,k4,k5*k1); add(c,k1,k2+1,-k5*k1); add(c,k3+1,k4,-k5*(k3+1)); add(c,k3+1,k2+1,k5*(k3+1));
            add(d,k1,k4,k5*k1*k4); add(d,k1,k2+1,-k5*k1*(k2+1)); add(d,k3+1,k4,-k5*(k3+1)*k4); add(d,k3+1,k2+1,k5*(k3+1)*(k2+1));
        end;
    begin
        getchar(ch);
        readln(n,m);
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        while not eof do begin
            getchar(ch);
            if ch='L' then begin
                readln(k1,k2,k3,k4,k5);
                addtotal(k1,k4,k3,k2,k5);
            end else if ch='k' then begin
                readln(k1,k2,k3,k4);
                writeln(findtotal(k3,k4)+findtotal(k1-1,k2-1)-findtotal(k1-1,k4)-findtotal(k3,k2-1));
            end;
        end;
    end.
Category: 数据结构 | Tags:

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