level 12
昨天tyvj不是挂了么O.O
2012年11月10日 04点11分
level 12
level 3
膜拜ak神牛
2012年11月10日 04点11分
3
我AK不能.. 第三题挂了
2012年11月10日 05点11分
回复 wyl8899 :+号换成*号后难了很多…… 如果是+号，二分答案一下就可以了，不影响复杂度…… 今天题目二分答案只有60分。。。
2012年11月10日 05点11分
回复 sillycross :乘法取log就变成加法了吧，因为a,b>=1，log以后肯定是非负的~
2012年11月10日 06点11分
回复 a6687543 : 乘法就不能直接二分了，因为有精度问题…… 不知道先二分到一定精度，然后在附近枚举能不能混过去
2012年11月10日 11点11分
level 13
![[吐舌]](/static/emoticons/u5410u820c.png)
感谢堆积木，你懂的
level 12
wyl8899
楼主
昨天欢乐赛的第二题.
原题是求和,按照ai+bi排序.
这题是求积,所以按照ai*bi排序.(直觉上当然就是这样,如果要说比较严谨的话,取对数就可以得到证明.)至于那个国王,可以完全忽略掉,因为n个大臣的方案最优了,加上个国王当然也是最优的,反之亦然.
这个贪心没见过原题真的比较难想...反正我想不出.
然后说一下原题的证明吧,假设我们有a[i],b[i],a[i+1],b[i+1],满足a[i]+b[i]<=a[i+1],b[i+1],再记S=∑(j=1..i-1,a[i]),应当有max{S-b[i],S+a[i]-b[i+1]}<=max{S-b[i+1],S+a[i+1]-b[i]}.为了证明这个关系式,按照右端的两个值的大小关系分类讨论,然后用分析法推一下就差不多了.
2012年11月10日 05点11分
13
原题是求和,按照ai+bi排序.
这题是求积,所以按照ai*bi排序.(直觉上当然就是这样,如果要说比较严谨的话,取对数就可以得到证明.)至于那个国王,可以完全忽略掉,因为n个大臣的方案最优了,加上个国王当然也是最优的,反之亦然.
这个贪心没见过原题真的比较难想...反正我想不出.
然后说一下原题的证明吧,假设我们有a[i],b[i],a[i+1],b[i+1],满足a[i]+b[i]<=a[i+1],b[i+1],再记S=∑(j=1..i-1,a[i]),应当有max{S-b[i],S+a[i]-b[i+1]}<=max{S-b[i+1],S+a[i+1]-b[i]}.为了证明这个关系式,按照右端的两个值的大小关系分类讨论,然后用分析法推一下就差不多了.
手误,应该是"满足a[i]+b[i]<=a[i+1]+b[i+1]".虽然比较繁琐但是确实可以证明的...
2012年11月10日 05点11分
Orz。。。想不到只有骗点分了。。。
2012年11月10日 05点11分
我考场猜的按ai*ai*bi贪的这道题有前途吗。。。
2012年11月10日 05点11分
我去 我就按ai*bi排序的 话说ai*bi一样咋办？再按啥排？双关键字？ 看到了希望
2012年11月10日 05点11分
level 9
![[我错了]](/static/emoticons/u6211u9519u4e86.png)
level 12
level 7
2012 ACM/ICPC Asia Regional Chengdu Online Problem I - Buildinghttp://acm.hdu.edu.cn/showproblem.php?pid=4296，印象非常深刻。
2012年11月10日 05点11分
16
其实不完全一样～ 你这题以及tyvj的那题，二分答案后就有非常显然的贪心做法了，但这个做法在今天考试中只能60分.
2012年11月10日 05点11分
回复 sillycross :我没看到题目，只是根据前面人的描述来看，似乎和这个题目有点相似。
2012年11月10日 05点11分
level 9
![[揉脸]](/static/emoticons/u63c9u8138.png)
如果能拿1=就给Tyvj捐钱
level 1
