2019-team321/C006

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(board.png,500px)]]
== 流水账 ==

一开始 ypl 和 yay 都看了 H， ypl 过来写了一下'''H(+0 16)'''， 又给 zkx 确认了 I 的题意，写了一下'''I(+0 28)'''。

zkx 看了 ABCE， 给 yay 说了一下 E 题意， 榜上有人过 K， zkx 去看了一下过了 '''K(+0 48)'''。

zkx 写了一下 '''B(+0 73)'''， ypl 想出了 A。

zkx 和 ypl 讨论 C， zkx 开始写， ypl 推了一下精度有没有问题， yay 想好了 E。

yay 想出了 E， 交给 zkx 写， zkx 写了好久， t 了一发， 发现只 sort 一次这个功能假了， 改了一下 '''E(+1 195)'''。 ypl 这个时候想出了 J。

ypl 上来写 J， 因为有个特殊情况没判 t 了一发， '''J(+1 228)'''。 这个时候 yay 想出了 G。 期间 zkx 和 yay 在讨论 F， 想到了最小树形图但是感觉复杂度不对。

yay 上来写了一下 G， '''G(+0 273)'''， ypl 把 A 的做法告诉了 zkx， 去想 D 和 F。

zkx 上来写了一下 A， '''A(+0 285)'''。


== 总结 ==

1. G 题开场有些人过， 不应该在有些想法的时候搁置， 或许可以和队友说一下帮忙 check。

== YPL ==

A：有 100000 个点 (si, ti)，找到两维都单调不降的 n 个点 (xi, yi)，最小化 Σdist((si, ti), (xi, yi))。
[[BR]]
两维分开处理。容易想起以前见过的一道 BOI 题：给定 100000 个点 xi，找到 yi 最小化 Σ|xi - yi|。如果只选择一个 y，根据几何意义必然令 y 为所有值的中位数。猜想最终的序列一定可以被划分成若干个区间，每个区间取其所有值的中位数，且从左往右的区间的中位数单调递增。然后增量构造，每次先造一个单点区间 [i, i, ai]，若当前取值小于上一个区间的中位数，那么就将两个区间暴力合并，若仍然小于再上一个区间的中位数，那么继续合并，以此类推。
[[BR]]
这道题就直接照葫芦画瓢。如果只选择一个 y，那么就选择合式的二次函数的顶点，其余都一样的，还不需要写什么数据结构了。

B：400000 个点，有依赖关系，构造拓扑序，最小化 max(i + b[ord(i)])。
[[BR]]
拓扑排序，出队顺序的关键字为 max succ。

C：给定 1000 个点的树，在平面上画出来，边不相交且长度为 1。
[[BR]]
场上想着按照 degree 等分然后就不会做了，实际上按照 size 等分就好了。
[[BR]]
万一思路断了，那么应该问问先前的思考能给自己留下了什么有用的东西，并尝试在之后去用来解题。

F：2500 个点，给定 w(i, j)，w(i, 0..n) 递减，另外每个 i 有 w'(c(i), i) = d(i)，d(i) <= w(i, n)，求最小树形图的权值和。
[[BR]]
目前能想到若干个基环外向树，一定是选择一个点然后选完其所有后继，然后还不会 DP。

G：平面有球有障碍，给定操作 LRUDLLRUDLLLR 最终到 (0, 0)，构造障碍。
[[BR]]
从起点构造，每次走出矩形边界，判断合法，坐标平移。
[[BR]]
场上一直在想从终点开始构造然后毫无头绪。这时候应该要学会换一个思路。

J：n = 100000 个人分值为 p1, p2, ..., pn，每次 2 号到 n 号随机猜一个数 0/1，1 号选择除他以外分值最大的人群中选择个数较多的数，猜对的人分值 ++，问 1 号在最坏情况下能保持多少回合不被超过。
[[BR]]
问题转化为将 p 排序，前 M 个最大，那么每次 p[1 .. floor(M / 2)] ++, p[floor(M / 2) + 1, M] 不变，p[M+1 .. n] ++，问 W 能保持多少次最大。先找 1111111 的规律，然后找 111111112 的规律，然后用规律加快模拟可以做到 O(n * n)。再注意到只用维护值的相对大小，每次可以将 W 减小，另外维护一个 suffix_common_delta 就可以优化到线性。

流水账

一开始 ypl 和 yay 都看了 H， ypl 过来写了一下H(+0 16)， 又给 zkx 确认了 I 的题意，写了一下I(+0 28)。

zkx 看了 ABCE， 给 yay 说了一下 E 题意， 榜上有人过 K， zkx 去看了一下过了 K(+0 48)。

zkx 写了一下 B(+0 73)， ypl 想出了 A。

zkx 和 ypl 讨论 C， zkx 开始写， ypl 推了一下精度有没有问题， yay 想好了 E。

yay 想出了 E， 交给 zkx 写， zkx 写了好久， t 了一发， 发现只 sort 一次这个功能假了， 改了一下 E(+1 195)。 ypl 这个时候想出了 J。

ypl 上来写 J， 因为有个特殊情况没判 t 了一发， J(+1 228)。 这个时候 yay 想出了 G。 期间 zkx 和 yay 在讨论 F， 想到了最小树形图但是感觉复杂度不对。

yay 上来写了一下 G， G(+0 273)， ypl 把 A 的做法告诉了 zkx， 去想 D 和 F。

zkx 上来写了一下 A， A(+0 285)。

总结

1. G 题开场有些人过， 不应该在有些想法的时候搁置， 或许可以和队友说一下帮忙 check。

YPL

A：有 100000 个点 (si, ti)，找到两维都单调不降的 n 个点 (xi, yi)，最小化 Σdist((si, ti), (xi, yi))。

两维分开处理。容易想起以前见过的一道 BOI 题：给定 100000 个点 xi，找到 yi 最小化 Σ|xi - yi|。如果只选择一个 y，根据几何意义必然令 y 为所有值的中位数。猜想最终的序列一定可以被划分成若干个区间，每个区间取其所有值的中位数，且从左往右的区间的中位数单调递增。然后增量构造，每次先造一个单点区间 [i, i, ai]，若当前取值小于上一个区间的中位数，那么就将两个区间暴力合并，若仍然小于再上一个区间的中位数，那么继续合并，以此类推。

这道题就直接照葫芦画瓢。如果只选择一个 y，那么就选择合式的二次函数的顶点，其余都一样的，还不需要写什么数据结构了。

B：400000 个点，有依赖关系，构造拓扑序，最小化 max(i + b[ord(i)])。

拓扑排序，出队顺序的关键字为 max succ。

C：给定 1000 个点的树，在平面上画出来，边不相交且长度为 1。

场上想着按照 degree 等分然后就不会做了，实际上按照 size 等分就好了。

万一思路断了，那么应该问问先前的思考能给自己留下了什么有用的东西，并尝试在之后去用来解题。

F：2500 个点，给定 w(i, j)，w(i, 0..n) 递减，另外每个 i 有 w'(c(i), i) = d(i)，d(i) <= w(i, n)，求最小树形图的权值和。

目前能想到若干个基环外向树，一定是选择一个点然后选完其所有后继，然后还不会 DP。

G：平面有球有障碍，给定操作 LRUDLLRUDLLLR 最终到 (0, 0)，构造障碍。

从起点构造，每次走出矩形边界，判断合法，坐标平移。

场上一直在想从终点开始构造然后毫无头绪。这时候应该要学会换一个思路。

J：n = 100000 个人分值为 p1, p2, ..., pn，每次 2 号到 n 号随机猜一个数 0/1，1 号选择除他以外分值最大的人群中选择个数较多的数，猜对的人分值 ++，问 1 号在最坏情况下能保持多少回合不被超过。

问题转化为将 p 排序，前 M 个最大，那么每次 p[1 .. floor(M / 2)] ++, p[floor(M / 2) + 1, M] 不变，p[M+1 .. n] ++，问 W 能保持多少次最大。先找 1111111 的规律，然后找 111111112 的规律，然后用规律加快模拟可以做到 O(n * n)。再注意到只用维护值的相对大小，每次可以将 W 减小，另外维护一个 suffix_common_delta 就可以优化到线性。