Discussion Detail

分享
2028 届选拔考试提示
Csvoner SU @ 2025-9-12 19:23:35

二分与猜数

_1. $n$ 。

每个决策点本身对应一个答案，共 $n$ 种答案，所以有 $n$ 个点。

_2. $\text{ }2,8,10$ 。

每个决策点深度对应其答案猜到的次数，所以答案是最深的三个点

_3. 从 $1$ 猜到 $10$ 或者从 $10$ 猜到 $1$ 都可以。

分别当 $x=10$ ， $x=1$ 时猜到次数为 $n$ 次，取到上限。

_4. 证：

第 $k$ 层最多有 $2^{k-1}$ 个点，假设每一层都取满，至少取 $k$ 层，那么有：

1+2^1+2^2+\cdots + 2^{k-1} \geq n

根据提示，有：

2^{k} - 1\geq n

那么 $k = O(\log n)$ ，至少有 $O(\log n )$ 层，所以最劣情况下至少要猜 $O(\log n)$ 次。

_5.

考虑给出排序算法的过程，我们每次能确定选出的中间的数的排名为他左边数 $a_c$ 的个数 $+1$ ，那么我们就能确定第 $k$ 大比 $a_c$ 大还是比 $a_c$ 小，只需要处理包含第 $k$ 大的左区间或者右区间，期望每次这个区间长度除以 $2$ ，所以根据提示，复杂度：

O(n + \frac n 2 + \frac n 4 + ...) = O(n)

易证这个算法最优，因为读取一遍 $a$ 数组都需要 $O(n)$ 。

_6.

考虑重排能构造出的决策树，如果某个决策点所经过的所有决策进行的比较能确定出一个重排 $p$ ，那么他一定不会再继续进行决策，那么他一定是一个叶子节点。

一共有 $n!$ 个重排，每个对应一个叶子，算法的复杂度即为决策树最深点的深度，那么假设我们有一个算法让决策树变成满二叉树，那这个算法的复杂度一定最优。

假设最深的层数即答案是 $k$ ，那么有 $2^{k-1} = n!$ ， $k = O(\log n!)$ ，根据提示， $k=O(n\log n)$ ，我们就证明了基于比较的排序复杂度下限为 $O(n\log n)$ 。

怎么证明提示呢？

2\log n! = \log (n!)^2

那么交换一下有：

(n!)^2 = \prod _{i=1}^n i(n-i+1)

而 $\min_{i=1}^n i(n-i+1) = n$ ，则 $(n!)^2> n^n$ .

根据 $\log$ 的单调性，有：

\log n! < \log n^n < 2\log n!

则： $O(\log n!) = O(n\log n)$ .

位与功能完备 _1.

$$\begin{array}{c c | c} A & B & A \text{ and } B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array} $$$$\begin{array}{c c | c} A & B & A \text{ xor } B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} $$

_2. 16

我们发现一个从二元布尔运算和真值表是双射的，那么我们对真值表计数即可： $A,B$ 共有 $2^2$ 种选法，每种 $A \text{ opt } B$ 有两种选法，所以有 $2^{2^2} = 16$ 种真值表，即有 $16$ 种不同的二元布尔运算。

_3. 证明：

可以用 $\text{nand}$ 构造 $\text{\{not, and, or\}}$ ：

\text{not }A = A \text{ nand }A

A \text{ and B }=\text{not } (A \text{ nand } B )

$$A \text{ or } B = (\text {not } A) \text{ and } (\text{not } B) $$

逐步代入即可，不需要化简。

而 $\text{\{not, and, or\}}$ 能构造出所有二元布尔运算，所以 $\text{nand}$ 也可以。

_4.

考虑一个 $k(k\geq 3)$ 元布尔运算和 $k$ 元真值表双射，而对于一个真值表，我们考虑如何用二元布尔函数构造出其对应的布尔运算。

对于真值表对应的 $k$ 元运算 $opt(x_1,x_2,...,x_k)$ ，假设真值表第 $c$ 行 $x_i = k_{ci}$ ，结果为 $o_c$ ，则当 $x$ 的取值方案与其中一个 $o_c = 1$ 的行相同时运算的结果为 $1$ ，容易写出 $x$ 的取值方法为 $k_{c}$ 的判断式：

$$\text{and}_{i=1}^k \text{ } k_{ci}\text{ xnor }x_i $$

其中， $A \text{ xnor } B = 1$ 当且仅当 $A=B$ 。

那么对于所有 $o_c = 1$ 的行，和其中一行的取值相等即可，有：

$$opt(x_1,x_2,...,x_k) = \text{or}_{o_c=1}(\text{and}_{i=1}^k \text{ } k_{ci}\text{ xnor }x_i) $$

再把 $\text{nand}$ 构造出的各个二元运算代换掉即可。

OWEN @ 2025-9-12 19:36:44

嘀咕嘀咕
bruce123 @ 2025-9-12 19:31:50

提示谁能看懂
- 北极宦跋焚 LV 5 @ 2025-9-13 11:33:23
  
  没人看懂
gggggg6 @ 2025-9-12 19:30:26

hao nan!
asdfghjkl;' LV 3 @ 2025-9-12 19:30:14

_1. n n。

每个决策点本身对应一个答案，共 n n 种答案，所以有 n n 个点。

_2.

2 , 8 , 10 2,8,10。

每个决策点深度对应其答案猜到的次数，所以答案是最深的三个点

_3. 从 1 1 猜到 10 10 或者从 10 10 猜到 1 1 都可以。

分别当 x

10 x=10， x

1 x=1 时猜到次数为 n n 次，取到上限。

_4. 证：

第 k k 层最多有 2 k − 1 2 k−1 个点，假设每一层都取满，至少取 k k 层，那么有：

1 + 2 1 + 2 2 + ⋯ + 2 k − 1 ≥ n 1+2 1 +2 2 +⋯+2 k−1 ≥n 根据提示，有：

2 k − 1 ≥ n 2 k −1≥n 那么 k

O ( log ⁡ n ) k=O(logn)，至少有 O ( log ⁡ n ) O(logn) 层，所以最劣情况下至少要猜 O ( log ⁡ n ) O(logn) 次。

_5.

考虑给出排序算法的过程，我们每次能确定选出的中间的数的排名为他左边数 a c a c 的个数 + 1 +1，那么我们就能确定第 k k 大比 a c a c 大还是比 a c a c 小，只需要处理包含第 k k 大的左区间或者右区间，期望每次这个区间长度除以 2 2，所以根据提示，复杂度：

O ( n + n 2 + n 4 + . . . )

O ( n ) O(n+ 2 n + 4 n +...)=O(n) 易证这个算法最优，因为读取一遍 a a 数组都需要 O ( n ) O(n)。

_6.

考虑重排能构造出的决策树，如果某个决策点所经过的所有决策进行的比较能确定出一个重排 p p，那么他一定不会再继续进行决策，那么他一定是一个叶子节点。

一共有 n ! n! 个重排，每个对应一个叶子，算法的复杂度即为决策树最深点的深度，那么假设我们有一个算法让决策树变成满二叉树，那这个算法的复杂度一定最优。

假设最深的层数即答案是 k k，那么有 2 k − 1

n ! 2 k−1 =n!， k

O ( log ⁡ n ! ) k=O(logn!)，根据提示， k

O ( n log ⁡ n ) k=O(nlogn)，我们就证明了基于比较的排序复杂度下限为 O ( n log ⁡ n ) O(nlogn)。

怎么证明提示呢？

2 log ⁡ n !

log ⁡ ( n ! ) 2 2logn!=log(n!) 2

那么交换一下有：

( n ! ) 2

∏ i

1 n i ( n − i + 1 ) (n!) 2

i=1 ∏ n i(n−i+1) 而 min ⁡ i

1 n i ( n − i + 1 )

n min i=1 n i(n−i+1)=n，则 ( n ! ) 2

n n (n!) 2

n n .

根据 log ⁡ log 的单调性，有：

log ⁡ n ! < log ⁡ n n < 2 log ⁡ n ! logn!<logn n <2logn! 则： O ( log ⁡ n ! )

O ( n log ⁡ n ) O(logn!)=O(nlogn).

位与功能完备 _1.

A B A and B 0 0 0 0 1 0 1 0 0 1 1 1 A 0 0 1 1

B 0 1 0 1

A and B 0 0 0 1

A B A xor B 0 0 0 0 1 1 1 0 1 1 1 0 A 0 0 1 1

B 0 1 0 1

A xor B 0 1 1 0

_2. 16

我们发现一个从二元布尔运算和真值表是双射的，那么我们对真值表计数即可： A , B A,B 共有 2 2 2 2 种选法，每种 A opt B A opt B 有两种选法，所以有 2 2 2

16 2 2 2

=16 种真值表，即有 16 16 种不同的二元布尔运算。

_3. 证明：

可以用 nand nand 构造 {not, and, or} {not, and, or}：

not A

A nand A not A=A nand A A and B

not ( A nand B ) A and B =not (A nand B) A or B

( not A ) and ( not B ) A or B=(not A) and (not B) 逐步代入即可，不需要化简。

而 {not, and, or} {not, and, or} 能构造出所有二元布尔运算，所以 nand nand 也可以。

_4.

考虑一个 k ( k ≥ 3 ) k(k≥3) 元布尔运算和 k k 元真值表双射，而对于一个真值表，我们考虑如何用二元布尔函数构造出其对应的布尔运算。

对于真值表对应的 k k 元运算 o p t ( x 1 , x 2 , . . . , x k ) opt(x 1 ,x 2 ,...,x k )，假设真值表第 c c 行 x i

k c i x i =k ci ，结果为 o c o c ，则当 x x 的取值方案与其中一个 o c

1 o c =1 的行相同时运算的结果为 1 1，容易写出 x x 的取值方法为 k c k c 的判断式：

and i

1 k

k c i xnor x i and i=1 k k ci xnor x i

其中， A xnor B

1 A xnor B=1 当且仅当 A

B A=B。

那么对于所有 o c

1 o c =1 的行，和其中一行的取值相等即可，有：

o p t ( x 1 , x 2 , . . . , x k )

or o c

1 ( and i

1 k

k c i xnor x i ) opt(x 1 ,x 2 ,...,x k )=or o c =1 (and i=1 k k ci xnor x i ) 再把 nand nand 构造出的各个二元运算代换掉即可。

🤡 3
- OWEN @ 2025-9-12 19:34:51
  
  别发了
qsq LV 5 @ 2025-9-12 19:30:01

~~看不懂~~思密达~

❤️ 2

🤡 2

👎 1
OWEN @ 2025-9-12 19:28:51

e
OWEN @ 2025-9-12 19:28:34

e

🤡 2

👎 1
com @ 2025-9-12 19:27:34

🤡 5

👎 5
201211110076 @ 2025-9-12 19:25:32

宿梓陈说话

👎 6

🤡 5

2028 届选拔考试提示

9 comments

分别当 x

10 x=10， x

2 k − 1 ≥ n 2 k −1≥n 那么 k

O ( n + n 2 + n 4 + . . . )

假设最深的层数即答案是 k k，那么有 2 k − 1

n ! 2 k−1 =n!， k

O ( log ⁡ n ! ) k=O(logn!)，根据提示， k

2 log ⁡ n !

( n ! ) 2

∏ i

1 n i ( n − i + 1 ) (n!) 2

i=1 ∏ n i(n−i+1) 而 min ⁡ i

1 n i ( n − i + 1 )

log ⁡ n ! < log ⁡ n n < 2 log ⁡ n ! logn!<logn n <2logn! 则： O ( log ⁡ n ! )

我们发现一个从二元布尔运算和真值表是双射的，那么我们对真值表计数即可： A , B A,B 共有 2 2 2 2 种选法，每种 A opt B A opt B 有两种选法，所以有 2 2 2

not A

A nand A not A=A nand A A and B

not ( A nand B ) A and B =not (A nand B) A or B

对于真值表对应的 k k 元运算 o p t ( x 1 , x 2 , . . . , x k ) opt(x 1 ,x 2 ,...,x k )，假设真值表第 c c 行 x i

k c i x i =k ci ，结果为 o c o c ，则当 x x 的取值方案与其中一个 o c

and i

其中， A xnor B

1 A xnor B=1 当且仅当 A

那么对于所有 o c

o p t ( x 1 , x 2 , . . . , x k )

or o c

1 ( and i

Status

Development

Support