2018 Multi-University, HDU Day 9

两个半小时签完到，最后两个 Last Hour。人生大起大落真刺激。

Problem A

Solved by zerol & kblack. 02:33 (+)

题意：在 n×m 的方格中填 1~nm 的数，使得只有一个数是它所在行列的最大值。

题解：显然那唯一一个数就是 nm。考虑从大到小依次填数，每个数肯定得填在一个之前填过的数的同一行或者同一列。dp[i][j][k] 表示已经填了 k 个数，已经有 i 行 j 列有数字的方案。转移有两种，一种是新开一行，一种是新开一列，还有就是填到 i 行 j 列的交叉处。

无比艰难的签到。

Problem B

Solved by kblack. 04:43 (+3)

Problem D

Solved by kblack. 01:29 (+1)

Problem J

Solved by ultmaster. 04:44 (+2)

题意：比较两个 $\log \cdots \log n ^{(\log \cdots \log n)^{(\log \cdots \log n)}}$ 的阶数。

题解：比赛的时候一通操作，动用了 Mathematica 观察了若干式子之后得出来一张图。在修了一堆 bug 之后发现算法根基就不大对，然后改改改，勉强 AC。

比赛后回顾了一下发现了半天的结论是显然的，如果更进一步的话，会发现完全没有这么复杂。

首先记 $\log \cdot \log n$ ($i$ 个 log) 为 $l(i)$ 两个式子都取 log 之后阶数的关系是不变的，会得到 $l(a) ^ {l(b)} l(c)$ 的形式。

记 $f(a,b) = l(a)^{l(b)}$，注意到 $l(c)=f(c,\infty)$。考虑一个更普适的问题比较两个 $f(a,b)f(c,d)$ 的阶数。只要两个里面阶数比较大的那个 $f$ 拿出来比较，如果相等，再比较小的即可。这又带来另一个问题就是如果比较两个 $f(a,b)$ 的阶数。注意到 $f(a,b) = l(a)^{l(b)}$，再取一次 log 即可。

注意处理一下 $\infty + 1 = \infty$。

Problem K

Solved by zerol. 00:47 (+)

温暖的签到。

zerol：那么迟才签到是因为看错题了。