|
三 12
NOI2000的题目是[瓷片项链][单词查找树][青蛙过河][程序分析器][古城之谜][算符破译]。[瓷片项链][单词查找树][青蛙过河][程序分析器]都是简单题，[古城之谜]难度一般，[算符破译]是较难。 [瓷片项链]是简单的二次函数求最值的问题，数学方法可以直接解决。[单词查找树]是一种基本的字符串处理的数据结构。[青蛙过河]是一个递归的数学问题，可以求出直接的公式。[程序分析器]是个模拟题，需要细心。[古城之谜]是个动态规划问题，但是需要对题意尤其是对范式的深入分析。[算符破译]是个较难的搜索题，需要大量剪枝和优化。 二 23
这是NOI计划的第二份题解。NOI1998的6道题是[个人所得税][免费馅饼][围巾裁剪][SERNET模拟][软件安装盘][并行计算]，相对于NOI1997要稍难一些，不过还都是可以接受的。 [个人所得税]是一个简单题，[免费馅饼][围巾裁剪]是基本的动态规划问题，难度都还算容易。[SERNET模拟]涉及到了图论的最短路算法构造，需要稍稍思考。[软件安装盘]是一个比较困难的搜索题，目前还没有较好的方法。[并行计算]用了随机+贪心的方法，细节非常多，构造也不是很容易。 做这些题花了我8天时间，主要原因是在[并行计算]上浪费了过多的时间，接下来要掌握节奏。 二 15
我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。 其中[竞赛排名]和[最佳游览]是两个最简单的题，但是往往细节是容易忽视的。[积木游戏]和[最优乘车]难度属于中等，分别是动态规划和构造最短路径解题。[卫星覆盖]和[文件匹配]属于较难题，用到了[卫星覆盖]离散化或者立体切割的方法，而[文件匹配]是搜索中的难题，需要很多的优化。 做这些题我花了4天的时间，进度还算正常，希望能继续保持下去。今后做题的宗旨是“不求多，不求快，但求精”。 二 03
本题关键在于挖掘“反质数”的隐含意义，如果一个数X是反质数，则它的约数的个数大于所有Y(X>Y)的约数的个数。根据定义我们可以看出， 在一个具有相同约数个数的正整数集合中，最小的正整数是反质数。例如约数个数为6的正整数集合{12,18,45,75,175…}，只有12是反质 数。因为任何一个比12大且约数个数等于6的数，都不满足反质数定义。所以，寻找不大于N的最大反质数问题可以转化成，寻找不大于N的约数个数最多的最小 正整数。 求一个数的约数个数可以用乘法原理，例如75=3^1*5^2，则75有(1+1)*(2+1)=6个约数。对于这道题我们可以采取搜索的方法。按照质因数从小到大依次枚举指数，找出最多的约数个数情况下最小的正整数。 十二 22
看过这道题，很容易想到用网络流的方法来构建问题模型。但是N<=5000，没有给出明确的边数限制使得我们不能从网络流下手。重新读题，注意到每个点邻接到的点都是按照一个顺序（自东向西）给出的，而且边不会有交叉，这就是解决问题的突破口。 我们采用贪心的策略，每次尽量靠东地深度优先搜索一条到目标的路径，把这条路径上的点都标记为使用过，然后在剩余的顶点构成的图中再次尽量靠东地深度优先搜索一条到目标的路径，直到不能到达目标位置，统计搜索到的路径。 这种贪心策略为什么是正确的？假设图中有M条到达目标的路径，分别为P1,P2,P3…PM，而且Pi在Pi+1的东边。因为所有路径 都是不相交的，所以Pi上的所有顶点也一定在Pi+1上所有顶点的东边。由此可以得出，我们每次尽量靠东搜索，给剩余的路径留下尽量多的位置，才能是路径 的条数最大。 时间复杂度为O(N+E)，N为顶点数，E为边数。另外因为没有给出E的数目限制，而N<=5000，我们只好使用动态开辟的邻接链表的方法来储存这个图。
23 queries. 0.466 seconds.
Designed by NattyWP .
Images by desEXign.
|
Recent Comments