2018 Multi-University, Nowcoder Day 7

Problem A

Solved by zerol. 00:22 (+)

Problem C

Solved by ultmaster. 02:14 (+3)

题意：给一个长度为 $2^n$ 的字符串，每次用 AND, OR, XOR 中的一种操作把相邻的两个合并。求最后合并结果是 1 的操作方案数。

题解：暴力就好了，维护一个可选的集合，和集合中每个产生的方案数。复杂度是 $\sum_{x=0}^{18} 2^{18 - x} \cdot \min(3^x, 2^{18-x}) \approx 1.4 \times 10^7$。由于还要带上数据结构的常数 / log，可能时限很紧。需要常数优化，能少开的地方尽量少开，unordered_map 可以卡过。

Problem D

Unsolved. (-1)

Problem E

Solved by ultmaster. 03:07 (+1)

题意：构造一个不超过 75 个点的图，使得刚好有 $n$ 个 $K_4$ 子图。

题解：不失一般性，我们只讨论最大的情况。分成 70 个点，和 5 个点。70 个点构成完全图有 $\binom{70}{4}$，然后五个点分别射进去 $x_1,x_2,\ldots,x_5$ 个，就可以多得到 $\binom{x_1}{3}, \ldots, \binom{x_5}{3}$ 个 $K_4$。故 $\binom{70}{4} + \binom{x_1}{3} + \cdots + \binom{x_5}{3} = n$，其中 $0 \le x_i \le 70$。暴力验证表明，这个方程刚好可以 cover 所有的不超过 $\binom{71}{4}$ 的整数。然后五个未知数就是一个经典套路，中途相遇就好了。

ultmaster: 这个题做法大概很多，假做法大概更多。一上来看到这题，智障的某人以为是签到。

Problem H

Unsolved. (-2)

Problem I

Unsolved. (-13)

Problem J

Solved by kblack. 01:38 (+2)