泽泽历险记 数据标程解题报告排名
[color=blue][b]泽泽历险记 数据标程解题报告排名[/b][/color][color=blue]
[b]感谢大家的支持与鼓励，希望大家提出宝贵的意见，谢谢[/b]
[b]个别迟交的选手个别交流[/b][/color]
数据1
数据1数据
数据数据
数据china
china 数据太大论坛不让传，传小的几个给大家测测，注意不要开数组 终于等你发完了~顶一个 = =果然就只AC了前面两题。WS地飘过…… 谢谢lz，china的数据能不能发我邮箱。
[email]easthong@126.com[/email]
再次谢谢。 同求 [email]berniewang90@163.com[/email] 急求[email]378783429@qq.com[/email] 也请将china的数据发[email]tutwo2008@yahoo.cn[/email] 谢谢！ 同求，谢LZ了[email]450643133@qq.com[/email] [email=470823113@qq.com]470823113@qq.com[/email]
谢了 看看
求china数据
lz帮忙发到[email]zhsuperzy@163.com[/email]求china数据
[email]elba@21cn.com[/email] 分享一下做法:england 这题标程用的是递推的方法, 速度快但缺点在于空间太大 (500 万的数组能不大么), 可以采用分治的方法解决.
记 f(l, r) 为第 l..r 座建筑中的最大矩形面积. 考虑 l..r 中最低高度的建筑 lowi, 那么可以计算出 lowi * (r - l) + 1, 这个式子可以理解为最长的矩形. 然后分别处理 f(l, lowi - 1) 和 f(j, r). 这里的 j 是 lowi 往后第一个和 h[lowi] 不等的建筑. 这样子虽然比标程慢了 0.3s - 0.5s, 但空间少了 N 倍, 实现比较简单.[code]program england;
const
filename = 'england';
var
i, n: longint;
h: array[1..100000] of longint;
function max(a, b: longint): longint;
begin
max := a; if b > a then max := b;
end;
function f(l, r: longint): longint;
var
i, j, low, lowi, left, right: longint;
begin
if (l < 1) or (r < 1) or (l > r) then exit(0);
if l = r then exit(h[l]);
low := maxlongint;
for i := l to r do
if h[i] < low then
begin
low := h[i]; lowi := i;
end;
for j := lowi + 1 to r do if h[j] > low then break;
left := 0; right := 0;
left := f(l, lowi - 1);
right := f(j, r);
f := max(left, right);
f := max(f, (r - l + 1) * low);
end;
begin
assign(input, filename + '.in'); reset(input);
readln(n); for i := 1 to n do read(h[i]);
close(input);
assign(output, filename + '.out'); rewrite(output);
writeln(f(1, n));
close(output);
end.[/code]brazil: 标程是 DFS 加剪枝, 我采用的是直接 BFS 就可以... 比标程多 15 行左右, 大牛肯定可以缩到差不多.[code]program brazil;
const
filename = 'brazil';
type
rec = record x, y: longint; end;
rec2 = record x, y: longint; t: real; end;
var
ans: real;
n, m, x, y: longint;
zz: array[1..400] of rec;
lm: array[1..300] of rec;
q: array[1..50000] of rec2;
vis: array[1..300] of boolean;
procedure readp;
var
i: longint;
begin
assign(input, filename + '.in'); reset(input);
readln(x, y, n, m);
fillchar(q, sizeof(q), 0);
readln(zz[1].x, zz[1].y);
for i := 2 to n do readln(zz[i].x, zz[i].y);
for i := 1 to m do readln(lm[i].x, lm[i].y);
close(input);
end;
function f(x1, y1, x2, y2: longint): real;
begin
f := sqrt(sqr(abs(x1 - x2)) + sqr(abs(y1 - y2)));
end;
procedure bfs;
var
t, k, b, tmp: real;
ok, spcx, spcy: boolean;
i, j, tx, ty, open, closed: longint;
begin
fillchar(vis, sizeof(vis), false);
vis[1] := true; ans := 1e20;
open := 1; closed := 0;
q[1].x := zz[1].x; q[1].y := zz[1].y;
repeat
inc(closed); t := f(q[closed].x, q[closed].y, x, y) * 2 + q[closed].t;
if (t < ans) and (t <> 0) then ans := t;
for i := 1 to n do
begin
if vis[i] = true then continue;
tmp := zz[i].x - q[closed].x;
spcx := false; spcy := false;
if abs(tmp) > 0.0001 then k := (zz[i].y - q[closed].y) / tmp
else spcx := true; // the same column
if k = 0 then spcy := true; // the same row
b := zz[i].y - k * zz[i].x;
ok := true;
for j := 1 to m do
begin
if not(spcx) and not(spcy) and (abs(lm[j].y - lm[j].x * k - b) < 0.000001) then
begin
if ((lm[j].y < q[closed].y) and (lm[j].y > zz[i].y))
or ((lm[j].y) < zz[i].y) and (lm[j].y > q[closed].y) then
begin
ok := false; break;
end;
end;
if (spcy) and (lm[j].y = zz[i].y) and
(((lm[j].x < zz[i].x) and (lm[j].x > q[closed].x))
or ((lm[j].x < q[closed].x) and (lm[j].x > zz[i].x))) then
begin
ok := false; break;
end;
if (spcx) and (lm[j].x = zz[i].x) and
(((lm[j].y < zz[i].y) and (lm[j].y > q[closed].y))
or ((lm[j].y < q[closed].y) and (lm[j].y > zz[i].y))) then
begin
ok := false; break;
end;
end;
if ok then
begin
inc(open); vis[i] := true;
q[open].x := zz[i].x; q[open].y := zz[i].y;
q[open].t := q[closed].t + f(zz[i].x, zz[i].y, q[closed].x, q[closed].y);
end;
end;
until closed >= open;
assign(output, filename + '.out'); rewrite(output);
writeln(round(ans));
close(output);
end;
begin
readp;
bfs;
end.[/code]这次出的题目比较灵活, 赞一个 第二题我是用的数学的方法，
用一个数组记录当高度为H 时最大的长度；
从最高的往下依次求出最大的当高度为H时该行最长的长度；
procedure inpu;
var i:longint;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
if a[i]>max then max:=a[i];
end;
end;
procedure ss;
var i,j,k,j1,s1:longint;
begin
for i:=max downto 1 do
begin
j1:=0;
s1:=0;
for j:=1 to n do
begin
if a[j]<i then continue
else begin
if j-j1=1 then begin
inc(s1);
j1:=j;
end
else begin
s1:=1;
j1:=j;
end;
if s1>l[i] then l[i]:=s1;
end;
end;
if l[i]*i>s then s:=l[i]*i;
end;
end; 第二题不是个简单贪心吗。。？
我只用了个存高度的数组。。还有几个辅助变量。。 LZ说句话好么，我等数据等了一早上了
页:
[1]
2