笔者最近意外的发现 笔者的个人网站 http://tiankonguse.com/ 的很多文章被其它网站转载,但是转载时未声明文章来源或参考自 http://tiankonguse.com/ 网站,因此,笔者添加此条声明。
郑重声明:这篇记录《【百度之星2014~初赛解题报告】》转载自 http://tiankonguse.com/ 的这条记录:http://tiankonguse.com/record/record.php?id=671
最近要毕业了,有半年没做比赛了.
这次参加百度之星的初赛娱乐一下.
现在写一下解题报告.
这次比赛还是四道题,最后我只做出一道来,不过还是进级了,只可惜复赛那天有事,不能做复赛了.
还是先看看四道题的类型吧
1.Scenic Popularity 暴力 复杂度O( 100 * 100 * 10000 ) 或者O( T * K * R) 线段树
4.JZP Set 数论或DP 复杂度 O(n * log(n))
第一题过的人最多.
这道题的正解我还不知道.
我是预处理有暴力过的,后来和别人讨论起来,有的直接暴力,有的线段树,有的更高级数据结构了.
题意:n个点,有些点的值固定,没固定的点的值是离自己较近的固定点的值,刚好在中间则取最大的值.
然后有一系列操作,这些操作可能会修改某个固定点的值,然后问小于某个值的点的个数.
方法:暴力或线段树
注意事项:线段树有多种方法,对于这道题怎么写怎么过.
具体解题报告:http://tiankonguse.com/record/record.php?id=666
线段树版的分析:http://tiankonguse.com/record/record.php?id=672
题意:告诉你一个矩阵,以及一个起始坐标.问走k步有多少个不同的路线.
方法:DP
注意事项:无
具体解题报告:http://tiankonguse.com/record/record.php?id=667
题意:告诉你n个时间点,这些时间点你会得到若干的钱.然后告诉你m个时间段,以及时间段对应的利率(百分比).问最后最多可以得到多少钱.
方法:DP
注意事项:钱相互独立就变得简单了
具体解题报告:http://tiankonguse.com/record/record.php?id=670
一个合法集合里任意挑两个数,如果这两个数之和是偶数,这个偶数除以2得到的数也要在这个合法集合里.
方法:DP或数论
注意事项:其实就是推公式
具体解题报告:http://tiankonguse.com/record/record.php?id=668
http://tiankonguse.com/record/record.php?id=666
http://tiankonguse.com/record/record.php?id=667
http://tiankonguse.com/record/record.php?id=670
http://tiankonguse.com/record/record.php?id=668
http://tiankonguse.com/record/record.php?id=672
【百度之星2014~初赛解题报告】,布布扣,bubuko.com
原文:http://blog.csdn.net/tiankonguse/article/details/27200799