国家集训队2008论文集 hunkshaw

《国家集训队2008论文集 hunkshaw》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、歧路修远，上下求索例谈信息学竞赛分析中的“深”与“广”福州第一中学肖汉骏何为“深”层次性低维高维条件简化条件复杂连续性锲而不舍、步步深入充分利用之前结果要素间关系单调性周期性何为“广”眼界广（解题策略）贪心算法随机化算法思路广（分析角度）综合分析全面把握手段广（分析手段）各有千秋兼收并蓄问题描述Paper第2届广东省大学生程序设计竞赛有N篇文章，每篇文章有一个阅读时间Ti，价值Vi．读一篇文章的代价定义为读完这篇文章的时刻乘上它的价值。求一个文章的阅读顺序，使得总代价最小。另外，有一些文章的

2、作者是相同的，这些文章必须按照作者写文章的先后顺序阅读。数据规模：1≤N≤50 000初步分析这个问题要求的是一个最佳的阅读顺序，使得总代价最小。但又附加了一定限制，即同一作者所写的文章要按时间顺序阅读。由浅入深弱化条件去除限制条件倘若每个作者只写一本书，该如何确定阅读顺序呢？考察相邻的两本书，设它们的阅读时间为T1,T2，价值为V1,V2。V2T2V1T1交换相邻文章之后第一本书的阅读完成时间推迟了T2，第二本书则提前了T1。总代价变化：T2V1-T1V2。对于最优序列，一定有：T2V1>T1

3、V2，也即V1/T1>V2/T2。V2T2V1T1V2T2V1T1特殊情况的解决相邻两项有这个关系，那么，整个序列不就是按照Vi/Ti从大到小的顺序排列么？只要一个简单的排序即可。时间复杂度：O(NlogN)轻松愉快！从特殊到一般如何处理作者因素对阅读顺序的影响？仍然应用从特殊到一般的思想展开分析。只有两个作者的情况。而在所有两个作者的情况中，某位作者只写了一篇文章的情况又最为特殊。最特殊的一般情况考察独立文章应何时阅读。根据刚才的分析，最优序列中相邻的可交换元素满足关系：V1/T1>V2/T2

4、也即，独立文章的比值要小于前面的，大于后面的。以形助数而二元组比值的形式，不禁促使我们联想到直线的斜率。不妨把问题图形化，用广泛的分析手段尝试解决问题。在图形中，独立文章的斜率要介于前后之间。多角度观察，凸点和凹点只注意问题一个方面的性质是有悖于“广”的要求的。容易用反证法证明，凹点是不能被新的文章插入的。而什么图形不包含凹点呢？是的，就是凸包！凸包！最终算法分别处理每一个作者，求出文章形成的凸包。则该作者所写的文章被凸包上的点划分为若干段，每段的斜率单调递减。而后把所有文章段按斜率降序排序，即

5、为所求的最优序列。时间复杂度：O(NlogN)回顾回顾这道题的解决过程：去除限制条件，从特殊情况着眼。在一般情况中，又选取了最为特殊的情况。运用数形结合的分析方法。从正反两个方面考察了凸点和凹点。最后联想到凸包，一气呵成地解决问题。启示可以看到，问题解决过程中的每一步，都或多或少地和“深”和“广”有所联系。在平常的解题实践中，我们往往依靠经验。然而效果时好时坏，难以把握。这正说明了零碎的经验，是不能代替系统的理论的。启示若能在分析过程中遵循一定的规则，做到有理、有序地分析，就能避免凭借经验带来的

6、不稳定性。另一方面，解题的成功并不是问题的结束。在我的论文中还叙述了如何将问题在“深”与“广”的方向延伸、拓展，从而提高分析能力。总结磨刀不误砍柴功知其然知其所以然谋定而后动在智力上有所发展在能力上有所提高TheEnd.