合作站点账号登陆

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 19:49:34 | 显示全部楼层

romanosovsky 发表于 2013-4-6 19:24

登录/注册后可看大图

居然都不讨论第3题……伤心
第3题不会啊……先LCA，然后……

LCA是什么？最近公共祖先？。。。额。。这个问题我还没过的说。。。尝试下穷举过小数据吧。。。

等死星人

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 20:48:24 | 显示全部楼层

m13890 发表于 2013-4-6 19:46

登录/注册后可看大图

我明白了，是我一开始的思路就歪了。思维习惯了正方形是最完美的。

可能是需要穷举一下吧，反正我把1-n和1-m的情况（排除n*m<k）都试了一遍就能勉强通过小数据了。不过更好的算法肯定是存在的，只不过不是作为凡人的我能看到的……

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 20:54:26 | 显示全部楼层

computingbear 发表于 2013-4-6 20:48

登录/注册后可看大图

可能是需要穷举一下吧，反正我把1-n和1-m的情况（排除n*m

恩。。。同是穷举过的。。。卡在第三题了。。。穷举居然WA了。。。找错中。。。

等死星人

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 20:54:38 | 显示全部楼层

romanosovsky 发表于 2013-4-6 19:24

登录/注册后可看大图

居然都不讨论第3题……伤心
第3题不会啊……先LCA，然后……

第三题我想的一个比较挫的方法就是先找到一条路径，然后对上面的边进行排序，然后再逐次判断是不是三角形。仅供参考

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 20:56:14 | 显示全部楼层

foodszhu 发表于 2013-4-6 20:54

登录/注册后可看大图

恩。。。同是穷举过的。。。卡在第三题了。。。穷举居然WA了。。。找错中。。。 ...

噢，Fighting！

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 21:00:55 | 显示全部楼层

computingbear 发表于 2013-4-6 20:54

登录/注册后可看大图

第三题我想的一个比较挫的方法就是先找到一条路径，然后对上面的边进行排序，然后再逐次判断是不是三角形 ...

差不多吧，先最短路，再排序，再比。。。但是。。。wa了。。。。

等死星人

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 21:04:11 | 显示全部楼层

本帖最后由 computingbear 于 2013-4-6 21:05 编辑

foodszhu 发表于 2013-4-6 21:00

登录/注册后可看大图

差不多吧，先最短路，再排序，再比。。。但是。。。wa了。。。。

嗯……至少这个思路应该是正确的，路径找对了吗？或者判断三角形的条件对了吗？
继续Fighting

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 21:06:42 | 显示全部楼层

computingbear 发表于 2013-4-6 21:04

登录/注册后可看大图

嗯……至少这个思路应该是正确的，路径找对了吗？或者判断三角形的条件对了吗？
继续Fighting ...

最短路很久很久没写过了。。不清楚写的对不。。。判断三角形不就是a【i] + a[j] > a[j+1]么。。。。

等死星人

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 21:09:51 | 显示全部楼层

foodszhu 发表于 2013-4-6 21:06

登录/注册后可看大图

最短路很久很久没写过了。。不清楚写的对不。。。判断三角形不就是a【i] + a[j] > a[j+1]么。。。。 ...

对的，!((a+b) <= c || (a+c) <= b || (b+c) <= a)

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 21:15:07 | 显示全部楼层

computingbear 发表于 2013-4-6 21:09

登录/注册后可看大图

对的，!((a+b)

既然已经排序就不用这么麻烦么。。。

等死星人

回复支持反对

该用户从未签到

30 主题	127 好友	2万积分

重度中二患者

积分: 28325

楼主| 发表于 2013-4-6 21:17:14 | 显示全部楼层

computingbear 发表于 2013-4-6 21:09

登录/注册后可看大图

对的，!((a+b)

不写了。。。打游戏去了

等死星人

回复支持反对

_Nozomi

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

荣誉会员

积分: 66622

发表于 2013-4-6 22:00:21 | 显示全部楼层

我也注册了一个号，第二题莫名其妙的就AC了…等我再看看
QQ截图20130406215906.png

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

romanosovsky

该用户从未签到

1 主题	11 好友	1715 积分

Continue

积分: 1715

发表于 2013-4-6 22:08:47 | 显示全部楼层

computingbear 发表于 2013-4-6 21:04

登录/注册后可看大图

嗯……至少这个思路应该是正确的，路径找对了吗？或者判断三角形的条件对了吗？
继续Fighting ...

不对……这个是树不需要求最短路。只要找到LCA就可以找到一条路径了。
但是找到路径以后怎么判断三角形……如果排序每一次都是nlogn的，肯定会超
也许还是要用到线段树的什么性质……？

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

该用户从未签到

1 主题	5 好友	467 积分

积分: 467

发表于 2013-4-6 22:31:28 | 显示全部楼层

romanosovsky 发表于 2013-4-6 22:08

登录/注册后可看大图

不对……这个是树不需要求最短路。只要找到LCA就可以找到一条路径了。
但是找到路径以后怎么判断三角形 ...

对小生来说有点高深了

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对