68 条题解
-
0wyc4662 LV 10 @ 2009-07-24 14:11:26
样例为什么是80???!!!
应该是90!
矩形左上角(1,1),右下角(10,9) -
02009-07-19 14:43:18@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 119ms
├ 测试数据 06:答案正确... 150ms
├ 测试数据 07:答案正确... 103ms
├ 测试数据 08:答案正确... 150ms
├ 测试数据 09:答案正确... 134ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:656ms尽管不是0MS,但是……本人的第60个AC达成,自我庆祝一下
-
02009-07-14 16:53:33@
极大化处理
没有0Ms!!
5555555555 -
02009-07-14 16:46:21@
有某人傻到直接for i,j=1 to L,W
怎么处理?
无视掉]
还是]
拖出去]
弹]Boom..Boom像弹棉花一样清脆悦耳哦~
-
02009-06-10 15:41:09@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 41ms
├ 测试数据 09:答案正确... 41ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:82msN^2加剪枝。。。。。。
-
02009-03-28 19:28:12@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 244ms
├ 测试数据 06:答案正确... 291ms
├ 测试数据 07:答案正确... 212ms
├ 测试数据 08:答案正确... 275ms
├ 测试数据 09:答案正确... 275ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:1322ms。。。分下边界和x轴有无相接考虑,加上move和O(N^2)DP,看来这个方法不好啊。
-
02009-03-16 20:26:14@
极大化思想
可以参考WC2003wzk论文,写的很好 -
02009-02-14 19:33:32@
脑残的又把调试输出交上去了..
做法是
把所有点加上4个顶点按横坐标排序
然后枚举左边界,向右拓展,随时调整上下边界,当UP -
02008-11-13 13:54:13@
├ 测试数据 01:答案正确... 999ms
├ 测试数据 02:答案正确... 999ms
├ 测试数据 03:答案正确... 999ms
├ 测试数据 04:答案正确... 999ms
├ 测试数据 05:答案正确... 999ms
├ 测试数据 06:答案正确... 999ms
├ 测试数据 07:答案正确... 999ms
├ 测试数据 08:答案正确... 999ms
├ 测试数据 09:答案正确... 999ms
├ 测试数据 10:答案正确... 999ms
---|---|---|---|---|---|---|---|-好危险的时间啊~~~
-
02008-11-07 07:58:48@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
Ho~Ho~ o(s^2)加上剪枝就0s了! -
02008-11-06 20:11:19@
16
-
02008-11-04 21:37:49@
给个数据
大家报下答案.
5 5
2
3 4
4 3 -
02008-10-29 20:34:01@
有人比我更菜么?此题我做了四天,先后提交了N多次,得分10到50都有,最后A了,而且A的稀里糊涂……
我想问一下是不是评测机有问题?这个题我从开始一直是用取中快排,老是WA,最后改成随机快排就对了,然后重新试了试取中快排居然又对了,怎么回事?
-
02008-10-04 17:57:30@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 9ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:9ms -
02008-10-04 15:58:14@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
最优子矩形O(S^2)算法 -
02008-09-27 19:27:09@
DP。数据类型longint,否则要挂掉。
我的代码在http://dfs35123.spaces.live.com/blog/cns!6CB032EC0980F16!374.entry
-
02008-09-20 19:35:37@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 509ms
├ 测试数据 06:答案正确... 447ms
├ 测试数据 07:答案正确... 400ms
├ 测试数据 08:答案正确... 603ms
├ 测试数据 09:答案正确... 541ms
├ 测试数据 10:答案正确... 119ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:2619ms用Temper测的。。时间好久。。
看wzk2003论文吧。一开始我用方法二,结果严重超时。。后来改方法一,Ac了。。
-
02008-10-23 14:18:53@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 259ms
├ 测试数据 06:答案正确... 228ms
├ 测试数据 07:答案正确... 322ms
├ 测试数据 08:答案正确... 369ms
├ 测试数据 09:答案正确... 369ms
├ 测试数据 10:答案正确... 103ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:1650ms
........................................
Ft... 看来后面的测试点的牛还是很多的....早知道些N*M内算法了...编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 119ms
├ 测试数据 06:答案正确... 119ms
├ 测试数据 07:答案正确... 134ms
├ 测试数据 08:答案正确... 166ms
├ 测试数据 09:答案正确... 197ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:760ms换了测试机 就是不一样!!!!
Program CowBath;
Const
Maxn = 30100;
Type
Arr = Record
x, y: Longint;
End;Var
G: Array [0..Maxn] Of Arr;
P: Array [0..Maxn] Of Longint;
B: Array [0..Maxn] Of Boolean;
i, j, k, n, m, s, L, r, x: Integer;
Ans, Max1, t: Longint;Function Max(a, b: Longint): Longint;
Begin
If a > b Then Max := a Else Max := b;
End;
Procedure QuickSortG(l, r: Integer);
Var
i, j: Integer;
y, x: Arr;Begin
i := l;
j := r;
x := G[(l + r) Div 2];Repeat
While G[i].y < x.y Do Inc(i);
While G[j].y > x.y Do Dec(j);If i j;
If l < j Then QuickSortG(l, j);
If i < r Then QuickSortG(i, r);End;
Begin
Ans := 0;
ReadLn(n, m);
ReadLn(s);
For i:= 1 To s Do Read(G[i].x, G[i].y);QuickSortG(1, s);
For i:= 1 To s Do Begin
L := 0;
r := n;For j:= i+1 To s Do If G[i].y G[j].y Then Begin
Ans := Max(Ans, (G[j].y - G[i].y) * (r - L));
If (G[j].x l) Then l := G[j].x;
If (G[j].x >= G[i].x) And (G[j].x < r) Then r := G[j].x;
End;Ans := Max(Ans, (m - G[i].y) * (r - l));
End;FillChar(B, SizeOf(B), False);
k := 2;
P[1] := 0;
P[2] := n;
B[0] := True;
B[n] := True;
Max1 := n;For i:= 1 To s Do Begin
Ans := Max(Ans, Max1 * G[i].y);If Not B[G[i].x] Then Begin
x := k;
While P[x] >= G[i].x Do Dec(x);t := x + 1;
For j:= k DownTo t Do P[j + 1] := P[j];
P[t] := G[i].x;
Inc(k);
B[G[i].x] := True;Max1 := 0;
For j:= 1 To k-1 Do Max1 := Max(Max1, P[j + 1] - P[j]);
End;End;
Ans := Max(Ans, Max1 * m);
WriteLn(Ans);
End.
-
02008-09-15 17:25:28@
编译通过...
-
02008-09-09 16:13:32@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 478ms
├ 测试数据 06:答案正确... 369ms
├ 测试数据 07:答案正确... 338ms
├ 测试数据 08:答案正确... 525ms
├ 测试数据 09:答案正确... 509ms
├ 测试数据 10:答案正确... 103ms汗,王知昆论文果然强,一看便知。。。。
不过有点慢,不知道楼下的牛人怎么写的