36 + 8 + 0 + 32 = 76。从分数看我确实写了部分分。
评级难度的人也觉得这个模拟赛比往年难点……不然也不会评三个紫。
注意力涣散的一次模拟赛。下面的思路看似连贯，实际上每行都卡了几分钟，长的十几分钟。
T1 第一眼以为是删不同位置的代价不一样。
- 过了一会儿才知道是删不同数字的代价不一样。
- 考虑把删数字换成加数字。
- 想到了枚举初始状态（最后一次删除的）
- 逐个考虑加数字。
- 加数字的顺序并不重要。
- 只要初始状态确定，整个代价就确定下来了
- 初始状态长度不会超过 5 位数，因为 6 位数里删一个数子可以不会得到更大的代价。
- 暴力枚举肯定不行要 DP 枚举子序列。
- 状态设
$f(r,i)$ 表示以下标$i$ 结尾，前面有$r$ 个数的子序列的……- 代价？
- 初始状态数字？
- 初始状态每位数子对应的代价和？
- ……
- 想到了设三个，$f$ 总代价，$g$ 初始状态数子，$h$ 初始状态每位数子对应的代价和。
- 考虑转移
- 由
$(r-1, j){r-1\le j<i}$ （是不是减一视实现下标起点而变化）转移而来。可以通过一边转移一边更新$j$ 实现线性求解。 - 差不多 1 个小时了看看后面的题。
-
$f(r,i)=\min(10g(r-1,j)+s_i+\sigma-h(r-1,j)-v(s_i))$ ，$s_i$ 是原数字（长达 100000 位的整数）的第$i$ 位，$v(x)$ 是数码$x$ 的代价。这步确定下来犹豫了很久。 -
$$\sigma=\sum_i v(s_i)$$ 这个挺好想的只是因为行间公式换了一行。 -
$$g(r,i)=10g(r-1,j)+s_i$$ $$h(r,i)=h(r-1, j)+v(s_i)$$ $j$ 是使上面最小值成立的下标。这很显然，当时也不知道干吗想这么久。 - 初始化也很显然，但是纠结了很久要不要额外的数组存这两个结果。
$$g(0, i)=s_i$$ $$h(0, i)=v(s_i)$$ - 转移修修改改确定下来后考虑代码实现。
- 多组数据，如果不用初始化的实现方式，只要在合法状态内转移影响不大。
- 要用滚动数组吗，实现有什么区别。
- 设了三个 DP 的话是不是可以简化
$f$ 的表达式$$f(r,i)=g(r,i)+\sigma-h(r,i)$$ - 怎么更新
$j$ （这有什么好想的可是真卡了我好些时间）。 - 这个最小值里的不随
$i$ 变化： $$\begin{align*} &\min(10g(r-1,j)+s_i+\sigma-h(r-1,j)-v(s_i)) \ =&\min[10g(r-1,j)-h(r-1,j)]+s_i+\sigma-v(s_i) \end{align*}$$ - 所以比较
$10g(r-1,j)-h(r-1,j)$ 和$10g(r-1,i)-h(r-1,i)$ 就好…… - 大概写完了，开始调代码，可是怎么调结果都会大一点……
2h 时放弃调试。只过了一个样例，实际得分 36。现在思路都是很自然的不能理解自己当时为什么想那么久。
- T2 开始手算样例。自然看一条链的。
- 一开始以为链都有解。
- 算了好久感觉有点树形 DP 的味道，因为有点子问题的意思。
- 可是怎么处理 -1 的操作啊。
- 考虑每个子树能不能调成一样的温度然后一层层合并？
- 但是链又很特殊……
- 然后一直模拟样例没什么思路。
- 终于意识到操作有交换律，把 +1 和 -1 分开。
- 问题相当于把一棵树的点权分解成两棵树，其中一棵是表示 -1 的点权和，另一棵是 +1 的点权和？
- 尝试很多样例后才意识到列方程。
- 代数式修修补补，设输入的树上点权是
$a(u)$ ，方程、不等式能这样描述：-
$\forall u,\ x(u)\ge\max{a(u),0}$ ：节点$u$ 减少的值非负；减少后不能是正数，不然怎么加都不能加到 0。 -
$x(u)=\sum_{(u,v)\in T} x(v)$ ：减少的值有孩子减少的决定。 -
$\forall(u,v)\in T,\ x(u)-a(u)\le x(v)-a(v)$ ：减少后增加的量中，上级节点要增加的不能多于孩子增加的，因为上级节点的增加都会叠加给孩子。
-
- 找几个样例验证了一下发现没问题。
- 没细想怎么解了，明明都是一次的却想不出实现，我好菜。
T3 要输出方案没想到什么方法暴力，但 T4 的平方时间很好想，就去写 T4 了。
可 T4 也是磕磕绊绊，结束前 2 分钟才调完。
综上，只有 T1 写挂了，后面都是智力因素（确信）。但是我想东西想得好慢啊。