never lost, never will.
Day I
Ministry
题目要求计算本质不同的树的形状. 我们可以给每一种不同的树给一个唯一的编号, 那么两棵树相同的充要条件是两棵树的树根有相同数目的孩子且孩子们的编号一一对应. 由于每个结点的孩子数很小(不超过三个), 我们可以从叶子到树根逐一枚举结点, 将三个孩子排个序, 按他们的编号求出一个Hash值, 并找之前有没有出现过相同的结点, 若没有, 则给这个结点分配一个新编号. 最后输出不同编号的个数即可.
Nasty
尽管老师要求计算的值很多, 但是若最后一个数相同, 那么计算结果也将相同, 所以本质不同的x的值只有b个, 预处理一下就可以了.
Sail
提交答案题, 不想做.. 以后再说.
Read the rest of this article »
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数组中就可以了(再具体的见代码吧).
我的代码写的比较丑, 官方解答写的很漂亮, 看一下就明白了.