F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4852 >> 求助管理员
save_code @ 2017-09-17 19:00:15
[ Quote ] [ Edit ] [ Delete ] 1#
能不能把这题数据也放出来啊
save_code @ 2017-09-17 19:04:22
[ Quote ] [ Edit ] [ Delete ] 2#
AC了,测试数据再也没用了,不过我还有很多疑问啊。。。。
test_tset @ 2017-09-17 19:07:45
[ Quote ] [ Edit ] [ Delete ] 3#
本来的算法复杂度是 O((n+m)^2*log(n+m)+O(m^2*n*log(m))的
然后狂WA。。

后来把一个地方的二分改成线性扫描 复杂度就变成了O((n+m)^2*log(n+m))+m^3*n)) 然后就AC了。。。。
kczno1 @ 2018-06-25 11:15:04
[ Quote ] [ Edit ] [ Delete ] 4#
请问这题怎么多项式啊..网上题解都是随机化
test_tset @ 2018-06-25 14:34:23
[ Quote ] [ Edit ] [ Delete ] 5#
我记得好像是这样的, 先算出 半径为r的覆盖区域,然后枚举 敌人和 建筑物,对于每一对 敌人和建筑物选择 枚举另外一个 敌人或者建筑物,然后选择 最大的半径作为候选半径 进行比较

复杂度好像是 O(n^2*m^2)的 正确性 不祥没有证明,也没举出返利
test_tset @ 2018-06-25 14:35:58
[ Quote ] [ Edit ] [ Delete ] 6#
话说表算考的全是我不会的算法啊
test_tset @ 2018-06-25 14:45:53
[ Quote ] [ Edit ] [ Delete ] 7#
不过 半径的合法性 和大小 不是单调的 开始写的 二分WA到怀疑人生,然后改成线性枚举过了。。。
Claris @ 2018-06-25 16:52:37
[ Quote ] [ Edit ] [ Delete ] 8#
我写过一个多项式的题解啊。

http://www.cnblogs.com/clrs97/p/8025819.html

A题
lavendir @ 2018-06-25 17:29:28
[ Quote ] [ Edit ] [ Delete ] 9#
https://www.lydsy.com/JudgeOnline/upload/4852.rar
kczno1 @ 2018-06-25 17:30:52
[ Quote ] [ Edit ] [ Delete ] 10#
谢谢
话说网上的退火程序好像都很辣鸡,跑几组随机数据马上就出错
kczno1 @ 2018-06-25 17:37:06
[ Quote ] [ Edit ] [ Delete ] 11#
我好像可以把他们hack掉
kczno1 @ 2018-06-25 17:45:52
[ Quote ] [ Edit ] [ Delete ] 12#
我搞了个数据,把我看到的三个题解都hack了
kczno1 @ 2018-06-25 17:46:44
[ Quote ] [ Edit ] [ Delete ] 13#
这题直接退火就是假算法吧..
Claris @ 2018-06-25 18:11:32
[ Quote ] [ Edit ] [ Delete ] 14#
原题官方数据非常强的,在这里:
http://serjudging.vanb.org/wp-content/uploads/areaofeffect.zip
test_tset @ 2018-06-25 20:48:56
[ Quote ] [ Edit ] [ Delete ] 15#
@ Claris 官方数据 有 M>1000的点啊
Claris @ 2018-06-25 20:54:51
[ Quote ] [ Edit ] [ Delete ] 16#
原题数据范围是1<=n<=10,1<=m<=2000,1<=r<=20000
test_tset @ 2018-06-25 21:26:48
[ Quote ] [ Edit ] [ Delete ] 17#
哦,原来是这样,我刚测了一下,我貌似挂掉了一组小数据,其他都是对的
test_tset @ 2018-06-25 21:28:28
[ Quote ] [ Edit ] [ Delete ] 18#
2 9 100
0 0 1
10 0 1
5 -4
5 -3
5 -2
5 -1
5 0
5 1
5 2
5 3
5 4

这组数据 我跑出来的结果是5, 官方结果好像是9,。、。。不知道我有没有复制错
test_tset @ 2018-06-25 21:43:01
[ Quote ] [ Edit ] [ Delete ] 19#
很多时候 正因为算法的正确性有悬念才有意思。。。
Claris @ 2018-06-25 21:47:34
[ Quote ] [ Edit ] [ Delete ] 20#
注:
如果炸弹的爆炸范围仅接触到了JYY建筑的边界,则不会对JYY的建筑造成损伤

所以9应该是正确的
test_tset @ 2018-06-25 21:48:36
[ Quote ] [ Edit ] [ Delete ] 21#
啊是的,删掉一句话 就 跑过了
if(hav[i][j])
continue;
test_tset @ 2018-06-25 21:49:30
[ Quote ] [ Edit ] [ Delete ] 22#
这句话加上貌似 对时间也什么帮助。。。
EdwardForg @ 2018-06-25 22:04:54
[ Quote ] [ Edit ] [ Delete ] 23#
orz
[Top] [Previous Page] [Next Page]

HOME Back