首页 > 代码库 > uoj6
uoj6
这道题看起来仿佛有点水
从小到大贪心,舍去左下角和右上角
空间卡得有点紧,用integer/short int
1、30分做法
记录数字的顺序及每个数字的位置,然后对于每个数字的位置与前面已取数字的位置进行判断,时间复杂度(n3)
const maxnm=5000*5000+10;maxn=5000+10; var pre,now,a,b,c,d,i1:int64; n,m,qu,nm,i,j,num,u,v,k:longint; t:array[0..maxnm] of longint; x:array[0..maxnm,1..2] of integer; bool:array[0..maxnm] of boolean; q:array[0..maxn*2] of longint; procedure swap64(var x,y:int64); var t:int64; begin t:=x;x:=y;y:=t; end; procedure swaplong(var x,y:longint); var t:longint; begin t:=x;x:=y;y:=t; end; function check(x1,y1,x2,y2:longint):boolean; begin if (x1<x2)and(y1>y2)or(x1>x2)and(y1<y2) then exit(false); exit(true); end; begin read(pre,a,b,c,d); read(n,m,qu); nm:=n*m; for i:=1 to nm do t[i]:=i; for i:=1 to nm do begin now:=(a*pre*pre+b*pre+c) mod d; i1:=i; swaplong(t[i],t[now mod i1+1]); swap64(now,pre); end; for i:=1 to qu do begin read(u,v); swaplong(t[u],t[v]); end; num:=0; for i:=1 to n do for j:=1 to m do begin inc(num); x[t[num],1]:=i; x[t[num],2]:=j; end; num:=0; for i:=1 to nm do bool[i]:=false; for i:=1 to nm do for j:=1 to num+1 do if j=num+1 then begin bool[i]:=true; write(i,‘ ‘); inc(num); q[num]:=i; end else if check(x[i,1],x[i,2],x[q[j],1],x[q[j],2])=false then break; end.
2、100分做法
对于行,记录比自身大的行的最小列,比自身小的行的最大列,对每个数字进行判断,时间复杂度(n2)
bzoj过,被UOJ卡到60。。。。。。
const maxnm=5000*5000+10;maxn=5000+10;oo=1000000000; var pre,now,a,b,c,d,i1:int64; n,m,qu,nm,i,j,num,u,v:longint; t:array[0..maxnm] of longint; x:array[0..maxnm,1..2] of integer; line:array[0..maxn,0..1] of longint; function min(x,y:longint):longint; begin if x<y then min:=x else min:=y; end; function max(x,y:longint):longint; begin if x>y then max:=x else max:=y; end; procedure swap64(var x,y:int64); var t:int64; begin t:=x;x:=y;y:=t; end; procedure swaplong(var x,y:longint); var t:longint; begin t:=x;x:=y;y:=t; end; function check(x1,y1,x2,y2:longint):boolean; begin if (x1<x2)and(y1>y2)or(x1>x2)and(y1<y2) then exit(false); exit(true); end; begin read(pre,a,b,c,d); read(n,m,qu); nm:=n*m; for i:=1 to nm do t[i]:=i; for i:=1 to nm do begin now:=(a*pre*pre+b*pre+c) mod d; i1:=i; swaplong(t[i],t[now mod i1+1]); swap64(now,pre); end; for i:=1 to qu do begin read(u,v); swaplong(t[u],t[v]); end; num:=0; for i:=1 to n do for j:=1 to m do begin inc(num); x[t[num],1]:=i; x[t[num],2]:=j; end; for i:=1 to n do begin line[i,0]:=0; line[i,1]:=oo; end; for i:=1 to nm do if not((line[x[i,1],0]>x[i,2])or(line[x[i,1],1]<x[i,2])) then begin write(i,‘ ‘); for j:=1 to x[i,1]-1 do line[j,1]:=min(line[j,1],x[i,2]); for j:=x[i,1]+1 to n do line[j,0]:=max(line[j,0],x[i,2]); end; end.
uoj6
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。