• https://zhuanlan.zhihu.com/p/614019740

Problem C. All Pair Digit Sums

和 #159 的最后那个题 一样，我们也需要考虑容斥，计算进位所带来的代价。
注意枚举每一位的时候，进位可能会产生复杂的后效性（进位再进位…）我们不能仅仅考察那一位。。。
而是需要整个后缀都纳入考虑，比如对于一个末尾是 17 的数那么符合条件的就是末尾 >= 83 的数。。。
可以排序后二分查找或者线性做，复杂度 O(nlognlog(Ai))。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(2e5) + 9;
LL a[N], b[N];
int n;

int f(LL x) {
    int z = 0; while (x) {
        z += x % 10;
        x /= 10;
    }
    return z;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    LL z = 0, c = 0;
    RD(n); REP(i, n) z += f(RD(a[i])); z <<= 1; z *= n;
    LL p10 = 1;
    REP(h, 15) {
        p10 *= 10; REP(i, n) b[i] = a[i] % p10; sort(b, b+n);
        REP(i, n) c += b+n-lower_bound(b, b+n, p10-b[i]);
    }
    cout << z - c*9 << endl;
}

Problem E. All Pair Shortest Paths

非常厉害的题，之前 fhc 出过三列的，这个题虽然只有两列，但是考察的东西更有趣了。

General 的 Floyd 是 O(n3) 的，格点图且没有负数的情况不存在向右又折返的情况，复杂性大为降低，但是状态依然是 O(n2) 的。
不过我们大量转移可以合并，我们只需要考察相邻的情况。

分类讨论后把 min 消掉，实际只有三种情况，且只和之前 dp 状态的差有关、
（这个十分 make sense，因为其实也只有上下，下上，和平推。交叉的情况肯定不存在。就像欧几里得平面里点的匹配一样囧）

于是我们可以开始根据这个差合并同类项！。。。然后惊喜的发现这个题最关键的性质。。。
对于平推的情况。。这些同类项的差依然是不变的！（寻找不变量！）
而对于另外两种情况，新的状态里它们又都被合并到一起了！。。。

于是我们就可以通过简单记录一个 offset 进行整体转移了。。后面就可以平推了。。甚至平衡树都不需要。。deque 即可。。
反而最后这步借助 offset 简化数据结构转移的题倒是非常常见的，甚至比线段树的懒标记还要简单（比如 COT6 里我们就用过）。