Together: Find's Blog

Balkan 2007 简明解题报告

Day I
Cipher
好像应该拿Hash做吧, 标程写的很离奇, 看不懂凭什么可以这么做. 自己也没能写出一个可以AC的程序.

Dream
一道组合数学的题. 分析题目, 实际上是要我们从第一个盒子和最后一个盒子中取一个数, 其他盒子取两个数, 使乘积可以被k整除, 问有多少种方案.
首先求出k的所有因子集合S, 再为盒子中每一个数a在S中找到最大的数b使a mod b = 0. 这两个都需要预处理掉, 还有一个next[a][b]数组, 表示若一个数是k的第a和第b个因子的公倍数, 则它在S中最大的因子是第next[a][b]个因子. 之所以要最大, 在后面的运算中, 方案会优先累计到最大的因子, 即k本身上.
我们用total[a][b]表示到第a行为止, 累计到多少种方案可以使取数之乘积可以被k的被b个因子整除, 需要注意的是, 这里只是累计到的方案, 也就是实际的方案可能比累计到的多, 正如我们之前提到的, 如果某种方案所得到的乘积既能被第a个因子整除, 又能被第b个因子整除, 那么会优先记在记b个因子所表示的total单元中, 即较大的因子头上(假设b>a). 我们先用累加的方法统计第一个盒子中的数字可以被哪个因子整除. 从第二行开始, 先统计单这一行得到的乘积可以被哪个因子整除, 之后再根据乘法原理计到total数组中去. 具体的说, 先用cur1表示只取一个数时可以被哪个因子整除(当然要尽可能大的因子), cur2表示取两个数后乘积可以被哪个因子整除(自然也要尽可能大的因子), cur1用与求第一个盒子相同的方法求出, 再枚举两个因子a,b, 若是相同的因子, 则cur2的next[a][b]单元(即乘积的最大因子)累加cur1[a]*(cur[a]-1) (乘法原理), 若不相同, 则cur2的next[a][b]单元累加cur1[a]*cur1[b]*2 (两种不同的取数顺序). 注意最后一行就不需要这样分两步统计了. 然后再用类似的方法将统计结果累加入total数组中就可以了(再具体的见代码吧).
我的代码写的比较丑, 官方解答写的很漂亮, 看一下就明白了.

Points
如果三个点共线, 那么它们的向量也必然共线. 我们可以以一个点为标准求出所有到其他点的向量, 然后将这些向量转换成同方向的x=1的向量 ( 如果x=0, 则让y=1, 以此类推 ), 这样如果两个方向相同, 那么它们的(x,y,z)一定相等. 我们只在这条直线最侧端的点上计数这条直线, 也就是说, 如果存在从点A, B, C使AB=-AC, 那么我们不在点A处计这条直线, 否则只要存在两个以上的向量相等, 那么计数器累加1. 这样每条直线会被累加两次, 最后答案除以2就可以了. 寻找相反向量的过程可以用二分查找. 时间复杂度 O( n^2logn ).

Day II
Mokia
线段树就搞定了. 据说可以用后缀数组做, 但我不会二维的.. 不可以一下就把所有结点建好, 用一个建一个.

Stairway
比较让人头疼的贪心题. 策略是这样的: 建立一个表, 每次读数一个数字C, 将它插入最一行最后一个位置, 并保证第一行仍是非递减的. 如果不能保证, 则用二分查找找到不比C小的最小的数字, 用C替换它, 并把它插入到第二行的末尾去. 如果被踢到第二行的数字不能满足第二行非递送, 就按第一行的策略把另一个数字踢到第三行去, 以此类推. 最后表中第一行的数字个数就是一个不下降序列的最大长度, 前两行的总个数是两个不下降序列的最大长度, 以此类推.
证明这个策略的正确性有点麻烦. 需要证明两点: 策略产生的是最优值; 通过合理的排序前n行可以组成n个不下降序列. 前者的证明大概是证明这种策略不会让结果更差, 后者的排列方法是从新插入数字处断开, 连到上一行新插入数字之前输出.

Toponyms
用树做就可以了. 把每一个字母作为结点, 并记录匹配的单词个数, 做法很像USACO DEC的sec. 但是会超空间.. 标程的做法是用一个字符指针来记录每个结点表示的字符串, 即在一个结点中保存若干的字母而非仅一个字母, 当匹配一个新的单词, 到这个结点时只能匹配一半, 则把这个字符串再拆开成两部分( 匹配上的部分A和没匹配上的部分B ), B是A的孩子, 再把正在插入结点的未被匹配上部分作为A的孩子. 尽管可以构造出使这种方法mle的数据, 但实践证明没有出这种数据.. (我的代码是会mle的, 懒的写标程的代码了..)

附题目, 数据, 官方标程和我的程序. ( 数据比较大, 所以压缩了一下, 结果没太大效果.. )
猛击这里下载吧!