Difference between revisions of "2018 Multi-University, Nowcoder Day 7"

From EOJ Wiki
Jump to navigation Jump to search
Line 20: Line 20:
  
 
Solved by ultmaster. 03:07 (+1)
 
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 F ==
 
== Problem F ==

Revision as of 12:29, 9 August 2018

Problem A

Solved by zerol. 00:22 (+)

Problem B

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 F

Problem G

Problem H

Unsolved. (-2)

Problem I

Unsolved. (-13)

Problem J

Solved by kblack. 01:38 (+2)