163 条题解
-
0
rjjacky LV 10 @ 2009-10-03 18:31:13
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 25ms
├ 测试数据 05:答案正确... 9ms
├ 测试数据 06:答案正确... 25ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 9ms
├ 测试数据 09:答案正确... 9ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:102ms直接用mst过了。
数据太弱了? -
02009-09-27 14:53:32@
周长-最大边,错!prim,错!dp不会。。。怎么办哟
-
02009-09-25 13:39:57@
说一下现在的状况:
相信dp,mst有反例,数据没有问题但是题目描述不正确,可以从任意一点开始(不过题目也没说第一个点是哪个点),一开始没考虑,交了n多次只有50分
其实和从一个点开始也差不了多少,只是初始化不同而已,抱着自虐的心态交了一次......竟然ac了 -
02009-09-18 13:12:04@
prim是错的。。
是DP。 -
02009-09-17 21:59:34@
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 196ms
├ 测试数据 05:答案正确... 212ms
├ 测试数据 06:答案正确... 212ms
├ 测试数据 07:答案正确... 228ms
├ 测试数据 08:答案正确... 228ms
├ 测试数据 09:答案正确... 228ms
├ 测试数据 10:答案正确... 212ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:1516ms50.211├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 9ms
├ 测试数据 05:答案正确... 56ms
├ 测试数据 06:答案正确... 9ms
├ 测试数据 07:答案正确... 56ms
├ 测试数据 08:答案正确... 25ms
├ 测试数据 09:答案正确... 25ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:205ms编译通过...
├ 测试数据 01:运行超时|无输出...
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 494ms
├ 测试数据 05:答案正确... 541ms
├ 测试数据 06:答案正确... 509ms
├ 测试数据 07:答案正确... 541ms
├ 测试数据 08:答案正确... 509ms
├ 测试数据 09:答案正确... 525ms
├ 测试数据 10:答案正确... 525ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:90 有效耗时:3644ms三次提交了同样的程序 只是改变了数组的大小,结果是如此ASTONISHING,的超级郁闷。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
-
02009-09-17 18:39:54@
kruscal写出9ms来了..欢迎大家鄙视我
-
02009-09-11 17:30:31@
题目是 凸多边形...............什么方法也一样...............
-
02009-09-06 16:28:37@
希望大牛可以详细解释下方程
-
02009-08-25 23:09:03@
lx 的方程是错误的。
MST绝对是错误的。
周长减去最长边很容易想到反例的。
So 数据太弱了~
贴个方程
f:=min(f+d,f+d);
f:=min(f+d[j-1,j],f+d);
很简单的
1表示在左边i点 0表示在右边j点 -
02009-08-22 00:33:05@
可以证明,路径不能交差
所以DP就很明朗了.时间是O(n^2)这样写好程序交上去后是10分
后来才发现,题目的描述根本不对.
测试数据是可以从任意一点开始的,而不是只大门.
枚举的话时间是O(n^3)就明显不够了.所以只要把点拉成2n个然后DP找状态即可降为O(n^2)
我没用循环而是用的记忆化递归,所以慢了点.
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 103ms
├ 测试数据 05:答案正确... 88ms
├ 测试数据 06:答案正确... 103ms
├ 测试数据 07:答案正确... 88ms
├ 测试数据 08:答案正确... 88ms
├ 测试数据 09:答案正确... 103ms
├ 测试数据 10:答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:661ms -
02009-08-18 20:51:27@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0msDP秒杀,和关路灯类似,走到左边这个点最短路,还是走到右边这个点最短路,
-
02009-08-17 10:44:22@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 25ms
├ 测试数据 05:答案正确... 25ms
├ 测试数据 06:答案正确... 25ms
├ 测试数据 07:答案正确... 25ms
├ 测试数据 08:答案正确... 41ms
├ 测试数据 09:答案正确... 41ms
├ 测试数据 10:答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:207ms没有秒杀不过很不错...
但是也很遗憾..因为是照搬下面大牛的动规方程...提供以下代码
//---|-
program s1069;
var
i,j,k,n:longint;
x,y:array[0..5000] of real;
f:array[0..1800,0..1800,0..1] of real;
ans:real;
function dis(i,j:longint):real;
begin
i:=i mod n; j:=j mod n;
if i=0 then i:=n; if j=0 then j:=n;
dis:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;
function min(a,b:real):real;
begin
if a=0 then exit(b); if b=0 then exit(a);
if a>b then exit(b)
else exit(a);
end;
begin
fillchar(f,sizeof(f),0);
ans:=maxlongint;
read(n);
for i:=1 to n do
read(x[i],y[i]);
for k:=1 to n-1 do
for i:=1 to 2*n-1-k do
begin
j:=i+k;
f:=min(f+dis(i,j),f+dis(i,i+1));
f:=min(f+dis(j,j-1),f+dis(i,j));
end;
for i:=1 to n do ans:=min(min(f,f),ans);
writeln(ans:0:3);
end.//---|---|---|
f:=min(f+dis(i,j),f+dis(i,i+1));
f:=min(f+dis(j,j-1),f+dis(i,j));
//---|---|---| -
02009-08-15 19:08:06@
这题第一个点不是起点阿,被恶搞了,出题的有点不负责任阿
-
02009-08-14 19:34:51@
ws 是什么?
黑书 又是什么? -
02009-08-13 10:24:12@
理论上PRIM绝对是错的,还是老实点DP,虽然我不是很会.
谁给个DP式子,顺便解释下。 -
02009-08-04 12:37:10@
因为所有点正好组成了一个凸多边形;
所以生成树算法生成的一定是一条合法的路线。
还楞着干啥?Prim啊! -
02009-08-04 08:50:16@
Accepted 有效得分:100 有效耗时:127ms
没有秒杀
用dp,但程序比较ws,用了35行,主要是要处理起点不一定是1这个事情
主要参看了黑书,虽然以前看的时候没怎么看懂,不过编一编就懂了
一个很重要的思想就是路径不能交叉,个人的解释是三角形两边之和大于第三边,即四边形中对角线交点和两个端点所组成的三角形中,属于对角线的两条边之和大于第三边。
所以只能走不交叉的路,转移的费用就只需要O(1)了prim我不知道对不对,能ac的话很奇怪……
-
02009-08-01 23:11:19@
好WS....
DP
为什么我的什么慢。。。。。。。 -
02009-07-31 20:28:43@
prime可能所有的点不是只走了一遍,所以会错。错误图论算法。用DP,更正确。
-
02009-07-31 18:03:04@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
图,0MS过(用prim 过了)
经典名言:
“prim (好写),kruscal (好理解)”
————著名中山市纪念中学大牛_冯艺
。。。。。。(虽然我只懂prim )。。。。。。。。。。。。。。。。
用prim ,爽!!!^_^