Codeforces 1240D: Stack Exterminable Arrays 题解

主要思路

刚开始看到分治的标签就下定决心用分治做,没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。

首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案,那么我们往左的时候可以合并之,并设置\(nxt[i]\)来进行跳跃;由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG,所以我们可以使用类似 AC 自动机的方式用 Map 合并信息:交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。

继续阅读Codeforces 1240D: Stack Exterminable Arrays 题解

AtCoder Grand Contest 002E – Leftmost Ball 题解

主要思路

我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球,不仅要考虑同质问题,还要考虑具体的颜色排列非常麻烦,不如我们一次性把所有的球都在序列上放好:设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面,我们可以这样转移:

\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]

解释一下:我们固定住该颜色的球的位置为最左能放置的点,然后乘上\(n – j + 1\)进行染色,并给剩余的\(k-2\)个球选位置。

继续阅读AtCoder Grand Contest 002E – Leftmost Ball 题解

HNOI 2018 省队集训 Day 1 – 解题报告

A – Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

继续阅读HNOI 2018 省队集训 Day 1 – 解题报告

「杂题集」- 2019年12月9日

最近都在学些科技,做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。

子集

首先,我们先考虑奇数长度段的情况(\(\{a_n\}\)已经排序):确定中位数为\(a_{mid}\),则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和,并除以元素个数。欲使价值最大,那么显然右侧需要靠近右端点进行选择, 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化:简化对长度的枚举复杂度。

继续阅读「杂题集」- 2019年12月9日