这是我的第一篇——?
因为我不会写所以有参考题解。(((
救命啊我第一次用LaTeX我真的不会用也不知道哪里该使用。
题目在这里!
A 项链
想到一定是优先处理相邻之和最大的,删除二者中值较大的那个,用链表来实现查找相邻的位置。我一向以容易想作为简单的标准,所以想干脆删掉一个位置后就把其他相关的也删掉,再将新的和放进去,这样用 set 好像方便删一点(明明标记一下删除的位置就可以-_-),所以我用了 set 和成堆的插入删除。
结果超时了。看了题解之后发现好像没太大区别,我改成堆之后标记已经删除的位置并跳过,再交一次好了很多,但还是超时。又把 long long 改成了 int 之后就过了,我写的真的有这么糟糕吗?
后来查了一下,set 似乎确实比堆要慢一些,所以以后一定好好考虑该用哪一个。T^T
B 记树
依旧不会就是 DP(不是)。写了暴力之后一直在围绕着树的结构如何去想,没什么结果。又想写性质分,可是是链的时候好像又要区分有些点不能做叶子,有些点只能做叶子,想得我头晕,就作罢了。
正解是定义 \(f(i,j,k)\) 表示枚举到编号为 \(i\) 的点,有 \(j\) 个没有父节点的点(也就是现在有几棵树),前面 \(i\) 个点还需要补上 \(k\) 个子节点。然后根据该节点可以有的子节点数量分类讨论,若它有 \(s\) 个子节点:
当 \(s=0\) 时,它可以单独开一棵树,则有 \(f_{i,j+1,k}+=f_{i-1,j,k}\) ;它也可以去作为子节点补充前面的空缺(当然是在 \(k>0\) 的时候),则有 \(f_{i,j,k-1}+=f_{i-1,j,k}\) 。
当 \(s=1\) 时,它能做的和 \(s=0\) 时是一样的,但是它的子节点可以是左儿子也可以是右儿子,它们是不同的方案,所以转移时要乘 \(2\) 。和前面不同的是它单开时空缺是多了一个的,也就是它的子节点,则 \(k\) 的值要加一;同理补空时 \(k\) 的值就不用变了。
当 \(s=2\) 时,在以上操作的基础上,它还可以让前面某一棵树的根节点充当自己的子节点,或者在补充前面子节点空缺的同时再接一棵树。(到这里我有一个很蠢的疑惑,怕自己以后又忘了也写一下。我不明白在 \(s=1\) 时为什么不能接前面的树,问了同学之后才明白,因为它只有一个子节点,如果接的是前面的节点,就不能保证题目要求的最大子节点编号大于该点编号了。所以只在 \(s=2\) 时接前面的点以及改变 \(k\) 的值保证后面有点来补充他的空缺实际上就是在维护子节点编号大于其编号。)这两种操作是这样转移的:
\(f_{i,j,k+1}+=2 \times j \times f_{i-1,j,k}\)
\(f_{i,j-1,k}+=2 \times (j-1) \times k \times f_{i-1,j,k}\,(j>1)\)
乘 \(2\) 仍然是为了区分左右儿子。有一点要注意的就是第二个式子中 \(j\) 要减一的原因是该点去补的那一棵树是不能再接在它下面的。
第一维可以通过位运算来实现滚动数组。
还有一个很唐的事情。我多测输出答案没写换行一直以为自己样例输出的不对,找了很久的错。脐橙看了好几遍,指出这个问题之后气笑了,大概是拿我这个唐人没招了。
剩下两个题似乎没什么好说的了。改也改不出来,赛时也没什么思路可言,无非是写个暴力。