CEOI 2007 简明解题报告 (不完整)
Day I
Ministry
题目要求计算本质不同的树的形状. 我们可以给每一种不同的树给一个唯一的编号, 那么两棵树相同的充要条件是两棵树的树根有相同数目的孩子且孩子们的编号一一对应. 由于每个结点的孩子数很小(不超过三个), 我们可以从叶子到树根逐一枚举结点, 将三个孩子排个序, 按他们的编号求出一个Hash值, 并找之前有没有出现过相同的结点, 若没有, 则给这个结点分配一个新编号. 最后输出不同编号的个数即可.
Nasty
尽管老师要求计算的值很多, 但是若最后一个数相同, 那么计算结果也将相同, 所以本质不同的x的值只有b个, 预处理一下就可以了.
Sail
提交答案题, 不想做.. 以后再说.
Day II
Airport
dp. 用 f[i][j] 表示第一个表现进行到第i步, 第二个表演进行到第j步可不可行, 若进行到 (i,j) 时没有哪个跑道被两场表演同时占据(这个可以在 (i,j-1) 的基础上维护), 且 f[i-1][j] 和 f[i][j-1] 中至少有一个为真, 则 f[i][j] 为真, 否则为假. 题目要我们求有没有 f[i][j]=true 且 f[i+1][j]=f[i][j+1]=false 的情况, 至于方案记录一下决策就好了.
Treasury
用 g[i] 表示以 id=i 的结点为根的树, 树根不与其孩子匹配的情况下的最大匹配个数, cg[i] 是这种情况下的方案总数; f[i] 表示以 id=i 的结点为根的树的最大匹配个数(树根可能匹配, 也不能不匹配), cf[i] 是这种情况下的方案总数. 则
g[i]=sum( f[k] ), k是i的孩子
cg[i]=cf[k1]*cf[k2]*cf[k3]*…*cf[kn]
f[i]=max( g[i], sum( f[k] )+g[t]+1 ) = max( g[i], g[i]-f[t]+g[t]+1 ), t是当前枚举的i的孩子, k是其他孩子
cf[i]=sum(cf[k1]*cf[k2]*cf[k3]*…*cf[kn]*cg[t]) = sum( cg[i]/cf[t]*cg[t] )
另外, 当 g[i]=f[i] 时, cf[i] 还应加上cg[i]. 特别应注意 cf[i] 还应在有多解时用到加法原理.
Necklace
非传统题最近都不太想做..
照例附上题目, 数据和我的程序.
猛击这里下载.
