神仙做法
我看题解之后非常心塞，竟然不用数位 DP ！我们先来考虑部分解。当\(num<10\)时，答案就是\(num\)。如果\(num \geq 10\)，那么答案就是\(9+\frac{x}{10}\)。我们来看，考虑一个数\(1921\)的答案，我们可以考虑\(192-\)部分里有\(\lfloor \frac{1920}{10} \rfloor\)对首尾相同的数。然后再加上位数为一时的答案。
我看题解之后非常心塞，竟然不用数位 DP ！我们先来考虑部分解。当\(num<10\)时，答案就是\(num\)。如果\(num \geq 10\)，那么答案就是\(9+\frac{x}{10}\)。我们来看，考虑一个数\(1921\)的答案，我们可以考虑\(192-\)部分里有\(\lfloor \frac{1920}{10} \rfloor\)对首尾相同的数。然后再加上位数为一时的答案。
我们先来简述一下字符串哈希。首先我们把字符串中的字符转换为数值，比如我们使用以下函数来搞定：
\[toNum(character) = character – numberOf(‘a’) + 1\]
然后，我们来定义一个值\(bitNum\)来作为进位值。所以，我们的前缀哈希函数有一个递推式如下：
\[Hash(i) = Hash(i-1)*bitNum + toNum(S[i])\]
我们可以来探寻这个前缀哈希函数的相减线性性。我们设\(|S|,|T|\)为这两个字符串的长度。我们得出：
\[Hash(|T|) = Hash(|S+T|) – Hash(|S|)*bitNum^{|T|}(1.1)\]
单调队列的主要目标其实跟单调栈的主要目标比较相似，都是在一个单调问题中，直接排除一些可以排除的答案进行运算。
在本题中，我们会采用单调队列来解决。首先，我们采用前缀和来进行快速计算。然后，在前缀的前提下，我们会在本题中使用一个策略，那就是：如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\)，那么处于\(i\)位置的元素对于我们来讲，是毫无用处的。原因是，如果我们要在\(m\)长度内获得和最大的子序列，对于一个这样前缀和又大、又靠前的元素，最优解绝不是由这个元素组成的。
我们来用几个代码块来简述我们的策略。
我最近一直在跟着李煜东写的算法进阶教程写题。这道题的限制条件有以下几个：
思考这两个条件，我们可以得出，只要我们优先选择平均损耗最大的子树进行染色，我们就可以得到最优解；另外，明显的是，如果我们给一个父节点染色，那么它的子节点中平均损耗最大的节点就会被优先染色。
为了让更多人理解，我打算分段代码来解释这个解法。
这道题耗了我一个上午。今天上午因为得知 NOIp 2018 成绩之后无法稳定心态去上课，所以翘课来机房写题。而当我看了半天的书和题解之后，我整合出了一个思路。
我们首先把整个序列存入\(pre[]\)数组之中，然后我们从端点\(L=1\)开始枚举右端点。我们选择倍增来加速。写一个\(check(num)\)函数来检测该区间内的校验值是否符合标准。校验值的计算策略是进行排序之后取最大和最小、次大和次小、…进行计算。我们排序可以使用归并排序的思想，因为我们的区间长度是以\(2\)为底的幂，且是从小到的枚举的，所以我们每次只需要排序区间右半部分，然后进行合并操作即可。具体看代码吧。
这又是一道抄题解的题目。我们先来简要分析一下触发矛盾的几种情况：
之后我们就可以用并查集来进行集合操作。而数据范围非常的大，而答案只需要一个最早解，那么我们就可以尝试二分答案。