这是NOI2009的所有题目的解题报告，虽然很久以前就写好了，还是留到今天才放出来，不算太晚，也不早了。有些题的参考程序是比赛现场写的，直接AC了或作为非完美算法，原封不动地贴了上来。
打包下载
Day1
NOI 2009 变换序列
NOI 2009 诗人小G
NOI 2009 二叉查找树
Day2
NOI 2009 植物大战僵尸
NOI 2009 管道取珠
NOI 2009 描边
平面上有一些笔画，笔画两端为半圆，中部为矩形，笔画可以互相重叠。任务是求平面上笔画的总面积。 阅读更多
有上下两个管道，管道内排列着两种颜色的珠。从两个管道中按照某种次序取出珠，可以形成一个输出序列。显然不同的取珠方法可以形成相同的输出序列，设某种输出序列的取珠方法数为a[i]，任务是求出所有输出序列的∑a[i]2。 阅读更多
有一些植物，每个植物携带有一定的资源（可正可负），且有一个攻击范围，可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物，僵尸不能走到植物的攻击范围内。任务是求一个进攻方案，使得僵尸获得的资源尽可能多。 阅读更多
有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为K。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。 阅读更多
问题简述
有N个诗句需要被排版为若干行，顺序不能改变。一行内可以有若干个诗句，相邻诗句之间有一个空格。定义行标准长度L，每行的不协调度为|实际长度-L|P，整首诗的不协调度就是每行不协调度之和。任务是安排一种排版方案，使得整首诗的不协调度最小。 阅读更多
对于0,1,…,N-1的N个整数，给定一个距离序列D0,D1,…,DN-1，定义一个变换序列T0,T1,…,TN-1使得每个i,Ti的环上距离等于Di。一个合法的变换序列应是0,1,…,N-1的一个排列，任务是要求出字典序最小的那个变换序列。 阅读更多
最近评论