👩🏿 🤰🏽 🍖 全面分析SHAD 2020中考试的第一部分 🖖🏼 🧖🏿 🌾

你好！我是ShAD Helper的策展人Azat Kalmykov。我们继续我们的系列文章，其中我们分析了进入ShAD的任务。这次，我们（我，Nikolai Proskurin和Alexander Kurilkin）将考察今年ShAD选拔第一阶段的决定，该决定于最近结束。因此，让我们开始吧。

A.当地最低

在什么参数值下函数反导数

f (x) = (x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x) \exp^{\frac{\sin x^{2} + 2}{5 x^{2} + 2}}

$f(x)=\left(x^{4}-(a+1) x^{3}+(a-2) x^{2}+2 a x\right) \exp ^{\frac{\sin x^{2}+2}{5 x^{2}+2}}$ 最多只有一个本地最小值？

决断

, — . , . , , ( ).

, , , ,

f (x) = x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x

$f(x) = x^4 - (a + 1)x^3 + (a - 2)x^2 + 2ax$ . , :

- 1, 0, 2, a

$-1, 0, 2, a$ . ,

f (x) = (x + 1) x (x - 2) (x - a)

$f(x) = (x + 1)x(x - 2)(x - a)$ .

,

+ \to - \to + \to - \to +

$+ \to - \to + \to - \to +$ , . ,

a = - 1, 0, 2

$a = -1, 0, 2$ . , .

限制

确定什么值

a

$a$ 这个极限是

\frac{1}{e}

$\frac{1}{e}$ ：

lim_{x \to + inf} {(\cos \sqrt{\frac{1}{x}})}^{\frac{x}{a}}

$\lim _{x \rightarrow +\inf }\left(\cos \sqrt{\frac{1}{x}}\right)^{\frac{x}{a}}$

决断

a = 1

$a = 1$ .

\sqrt{\frac{1}{x}} \to 0

$\sqrt{\frac{1}{x}} \to 0$ , :

\cos \sqrt{\frac{1}{x}} = 1 - \frac{1}{2! x} + \frac{1}{4! x^{2}} - \frac{1}{6! x^{3}} + \dots

$\cos{\sqrt{\frac{1}{x}}} = 1 - \frac{1}{2!x} + \frac{1}{4!x^2} - \frac{1}{6!x^3} + \ldots$

. , , , , . , . :

1 - \frac{1}{2 x} < \cos \sqrt{\frac{1}{x}} < 1 - \frac{1}{2 x} + \frac{1}{24 x^{2}}

$1 - \frac{1}{2x} < \cos{\sqrt{\frac{1}{x}}} < 1 - \frac{1}{2x} + \frac{1}{24x^2}$

x \to + \infty

$x \to +\infty$ ,

x

$x$ , . ,

e^{- 1 / 2}

$e^{-1/2}$ . , :

lim_{x \to + \infty} {(1 - \frac{1}{2 x} + \frac{1}{24 x^{2}})}^{x} = \exp (lim_{x \to + \infty} x \ln (1 - \frac{1}{2 x} + \frac{1}{24 x^{2}})) =

$\lim_{x \to +\infty} \left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)^x = \exp\left(\lim_{x \to +\infty} x \ln\left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)\right) =$

= \exp (lim_{x \to + 0} \frac{\ln (1 - \frac{x}{2} + \frac{x^{2}}{24})}{x})

$= \exp\left(\lim_{x \to +0} \frac{\ln\left( 1 - \frac{x}{2} + \frac{x^2}{24} \right)}{x}\right)$

, . :

lim_{x \to + \infty} {(\cos \sqrt{\frac{1}{x}})}^{x} = e^{- 1 / 2} \Rightarrow lim_{x \to + \infty} {(\cos \sqrt{\frac{1}{x}})}^{x / a} = e^{- 1 / 2 a}

$\lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^x = e^{-1/2} \Rightarrow \lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^{x/a} = e^{-1/2a}$

a = \frac{1}{2}

$a = \frac{1}{2}$ .

: , , .

C.当地最低

在什么最小步长处梯度下降找不到最小函数

x^{4} + \cos 2

$x^4+\cos 2$ 如果

x_{0} = 1

$x_0=1$ ？

决断

, :

x_{k} + 1 = x_{k} - λ ▽ f (x_{k})

$x_k+1 = x_k - \lambda \triangledown f(x_k)$

.

— , .

▽ f (x_{k}) = 4 x_{k}^{3}

$\triangledown f(x_k) = 4x_k^3$

x_{0}

$x_0$ ,

x_{1}

$x_1$ :

x_{1} = x_{0} - λ 4 x_{0}^{3} = 1 - 4 λ

$x_1 = x_0 - \lambda 4x_0^3 = 1 - 4\lambda$

x_{1} = - 1

$x_1=-1$ ,

x_{0}

$x_0$ , . , , «» -

1

$1$

- 1

$-1$ . , ,

x_{1} = - 1 \Leftrightarrow λ = 0.5

$x_1=-1 \Leftrightarrow \lambda=0.5$ (

0

$0$ ). ,

λ

$\lambda$ .

, .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . ,

0.5 > λ > 0 \Rightarrow | 1 - 4 λ | < 1

$0.5 > \lambda > 0 \Rightarrow |1 - 4\lambda| < 1$

:

| x_{1} | = | 1 - 4 λ | \leq 1 | 1 - 4 λ | = x_{0} | 1 - 4 λ |

$|x_1| = |1 - 4\lambda| \leq 1 |1 - 4\lambda| = x_0 |1-4\lambda|$

.

| x_{n + 1} | = | x_{n} - 4 λ x_{n}^{3} | = | x_{n} | | 1 - 4 λ x_{n}^{2} |

$|x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$ .

x_{n} < 1 \Rightarrow x_{n}^{2} < 1

$x_n < 1 \Rightarrow x_n^2 < 1$ .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . .

, ,

| x_{n} | \leq | x_{0} | | 1 - 4 λ |^{n} = | 1 - 4 λ |^{n}

$|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n$ . ,

| 1 - 4 λ | < 1

$|1-4\lambda| < 1$ ,

| x_{n} |

$|x_n|$ . .

D.自己的载体

确定向量在参数的哪个值

(\begin{array}{l} 1 \\ 1 \\ a \end{array})

$\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ 是矩阵的特征向量

(\begin{array}{ccc} a & 1 & - 1 \\ 1 & 2 & - 1 \\ 0 & 0 & 1 \end{array})

$\left(\begin{array}{ccc} a & 1 & -1 \\ 1 & 2 & -1 \\ 0 & 0 & 1 \end{array}\right)$

决断

v \neq 0

$v \neq 0$

A

$A$ ,

\exists λ

$\exists \lambda$ :

A v = λ v

$Av = \lambda v$ . :

(\begin{matrix} a & 1 & - 1 \\ 1 & 2 & - 1 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 \\ 1 \\ a \end{matrix}) = (\begin{matrix} 1 \\ 3 - a \\ a \end{matrix}) = λ (\begin{matrix} 1 \\ 1 \\ a \end{matrix})

$\begin{pmatrix} a & 1 & -1 \\ 1 & 2 & -1\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 3 - a \\ a \\ \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix}$

λ = 1

$\lambda = 1$ , —

a = 2

$a = 2$ , , . ,

a = 2

$a = 2$ .

E.预选赛

在什么参数值

a

$a$ 矩阵的最大行列式与此成反比？

(\begin{array}{ccc} a & - 7 & - 3 \\ 6 & - 10 & - a^{2} \\ 0 & a & 9 \end{array})

$\left(\begin{array}{ccc} a & -7 & -3 \\ 6 & -10 & -a^{2} \\ 0 & a & 9 \end{array}\right)$

决断

det (a) = | \begin{matrix} a & - 7 & - 3 \\ 6 & - 10 & - a^{2} \\ 0 & a & 9 \end{matrix} | = a | \begin{matrix} - 10 & - a^{2} \\ a & 9 \end{matrix} | - 6 | \begin{matrix} - 7 & - 3 \\ a & 9 \end{matrix} | = a^{4} - 108 a + 376

$\det(a) = \begin{vmatrix} a & -7 & -3 \\ 6 & -10 & -a^2 \\ 0 & a & 9 \\ \end{vmatrix} = a \begin{vmatrix} -10 & -a^2 \\ a & 9 \\ \end{vmatrix} - 6 \begin{vmatrix} -7& -3 \\ a & 9 \\ \end{vmatrix} = a^4 - 108a + 376$

{det}^{'} (a) = 4 a^{3} - 108 = 0 \Leftrightarrow a = 3

$\det'(a) = 4a^3 - 108 = 0 \Leftrightarrow a = 3$

, , , , ,

det (a)

$\det(a)$ ,

det (a) \geq det (3) > 0

$\det(a) \geq \det(3) > 0$

a = 3

$a = 3$ . ,

det (A^{- 1}) = det (A)^{- 1}

$\det(A^{-1}) = \det(A)^{-1}$ , ,

a = 3

$a = 3$ .

F.投影

给定分数

B (1, 2, - 3)

$B(1,2,−3)$ 和

C (2, 2, 1)

$C(2,2,1)$ 以及飞机

α

$\alpha$ ：

2 x - 2 y + z = 0

$2x−2y+z=0$ 和

β

$β$ ：

- x + 2 y + 3 z = 0

$−x+2y+3z=0$ 。找到该点的坐标

A

$A$ 如果知道它的正交投影到

α

$\alpha$ 与该点的投影重合

B

$B$ 但是在

β

$\beta$ -带点投影

С

。

决断

A = (x, y, z)

$A = (x, y, z)$ ,

B

$B$ , ,

B

$B$ . , ,

α

$\alpha$

{\bar{n}}_{1} (2, - 2, 1)

$\overline{n}_1(2, -2, 1)$ . :

{\begin{cases} x = 2 t_{1} + 1 \\ y = - 2 t_{1} + 2 \\ z = t_{1} - 3 \end{cases}

$\begin{cases} x = 2t_1 + 1\\ y = -2t_1 + 2\\ z = t_1 - 3\\ \end{cases}$

A

$A$ ,

C

$C$

β

$\beta$ . :

{\bar{n}}_{2} (- 1, 2, 3)

$\overline{n}_2(-1, 2, 3)$ , :

{\begin{cases} x = - t_{2} + 2 \\ y = - 2 t_{2} + 2 \\ z = 3 t_{2} + 1 \end{cases}

$\begin{cases} x = -t_2 + 2\\ y = -2t_2 + 2\\ z = 3t_2 + 1\\ \end{cases}$

t_{1}

$t_1$

t_{2}

$t_2$ , :

{\begin{cases} 2 t_{1} + 1 = - t_{2} + 2 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} 3 = t_{2} + 4 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} t_{2} = - 1 \\ t_{1} = 1 \end{cases}

$\begin{cases} 2t_1 + 1 = -t_2 + 2\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} 3 = t_2 + 4\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} t_2 = -1\\ t_1 = 1\\ \end{cases}$

, ,

A (3, 0, - 2)

$A(3, 0, -2)$ , .

G.多米诺

在遥远的头塞蒂星座，多米诺骨牌的每半指节上

0

$0$ 之前

N

$N$ 点，以及每对数字

(a, b)

$(a,b)$ 这样

a

$a$ 和

b

$b$ 全部来自

0

$0$ 之前

N

$N$ ，正好有一个包含这两个数字的多米诺骨牌。太空旅行者飞进去，随机捡起一个倒着的指节。在什么

N

$N$ 该多米诺骨牌的另一半上点数差的模块的数学期望将相等

2

$2$ ？

决断

ξ

$\xi$ ,

Ω

$\Omega$

ξ (Ω)

$\xi(\Omega)$ . :

E (ξ) = \sum_{k \in ξ (Ω)} k Pr [ξ = k] = 2

$E(\xi) = \sum_{k \in \xi(\Omega)} k \Pr[\xi = k] = 2$

A_{k}

$A_k$ — ,

K

$K$ ,

Pr [ξ = k] = \frac{| A_{k} |}{| Ω |}

$\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$ .

| Ω |

$|\Omega|$ , :

\sum_{k \in ξ (Ω)} k | A_{k} | = 2 | Ω |

$\sum_{k \in \xi(\Omega)} k |A_k|= 2 |\Omega|$

| Ω |

$|\Omega|$ . -, . -, , . ,

| Ω | = n + 1 + \frac{n (n + 1)}{2}

$|\Omega| = n + 1 + \frac{n(n + 1)}{2}$

.

. , 0

n

$n$ .

k

$k$ ?

n - k + 1

$n - k + 1$ : —

(0, k), (1, k + 1), \dots, (n - k, n)

$(0, k), (1, k + 1), \ldots, (n - k, n)$ . :

\sum_{k \in ξ (Ω)} k | A_{k} | = \sum_{k = 0}^{n} k (n - k + 1) = (n + 1) \sum_{k = 0}^{n} k - \sum_{k = 0}^{n} k^{2} = \frac{n (n + 1)^{2}}{2} -

$\sum_{k \in \xi(\Omega)} k |A_k| = \sum_{k = 0}^n k(n - k + 1) = (n + 1)\sum_{k = 0}^n k - \sum_{k = 0}^n k^2 = \frac{n(n + 1)^2}{2} -$

- \frac{n (n + 1) (2 n + 1)}{6} = \frac{n (n + 1) (n + 2)}{6}

$- \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6}$

\frac{n (n + 1) (n + 2)}{6} = (n + 1) (n + 2)

$\frac{n(n + 1)(n + 2)}{6} = (n + 1)(n + 2)$

n > 0

$n > 0$ , ,

n = 6

$n = 6$ .

H.考试

两个朋友决定一起在SHAD参加考试，并同意在14:00至15:00在入口处见面，但没有约定什么时间。他们每个人的到来时间在这段时间内是均匀分布的，但是朋友们都没有耐心，所以在等待了15分钟之后，他们感到绝望地等待着独自进入。众所周知，他们见过面。

找出两者都在14:45之前出现的可能性。

决断

, , . , 60x60. x , y — .

« » . « 14:45» 2 . , , , , « 14:45» , « » 3 . ,

\frac{5}{7}

$\frac{5}{7}$ .

一，随机变量

随机变量的分布密度

ξ

$\xi$ 等于

p (x) = \frac{1}{\sin x}

$p(x)=\frac{1}{\sin x}$ 在

x

$x$ 从

π / 2

$\pi/2$ 之前

2 \arctan e

$2 \arctan e$ 对其他所有零

x

$x$ 。

查找该随机变量不超过概率的值

\frac{1}{2}

$\frac{1}{2}$ 。

决断

Pr (ξ \leq x) = \int_{π / 2}^{x} \frac{d t}{\sin t} = \int_{1}^{\tan x / 2} \frac{d u}{u} = \ln \tan \frac{x}{2}

$\Pr(\xi \leq x) = \int\limits_{\pi/2}^x \frac{dt}{\sin{t}} = \int\limits_{1}^{\tan{x/2}} \frac{du}{u} = \ln{\tan{\frac{x}{2}}}$

\ln \tan \frac{x}{2} = \frac{1}{2} \Leftrightarrow \tan \frac{x}{2} = e^{1 / 2} \Leftrightarrow x = 2 \tan^{- 1} e^{1 / 2}

$\ln{\tan{\frac{x}{2}}} = \frac{1}{2} \Leftrightarrow \tan{\frac{x}{2}} = e^{1/2} \Leftrightarrow x = 2 \tan^{-1}{e^{1/2}}$

J.求平均值

健康）状况

	2
	256Mb
	input.txt
	output.txt

. : n

a_{0}, a_{1}, \dots, a_{n - 1}

$a_0, a_1, \dots, a_{n-1}$ .

- !

l r. .

l

$l$

r

$r$ :

\sqrt[r - l + 1]{a_{l} \cdot a_{l + 1} \cdot \dots \cdot a_{r}}

$\sqrt[r-l+1]{a_{l} \cdot a_{l+1} \cdot \ldots \cdot a_{r}}$

n

$n$ (

1 \leq n \leq 300 000

$1 \leq n \leq 300 000$ ).

n

a_{i}

$a_i$ (

0.01 \leq a_{i} \leq 100

$0.01 \leq a_i \leq 100$ ) .

q

$q$ (

1 \leq q \leq 100 000

$1 \leq q \leq 100 000$ ) — .

q

$q$

l_{i}

$l_i$

r_{i}

$r_i$ (

0 \leq l_{i} \leq r_{i} < n

$0 \leq l_i \leq r_i < n$ ) —

i

$i$ - .

6 .

.

1


8 79.02 36.68 79.83 76.00 95.48 48.84 49.95 91.91 10 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 7 2 7	79.020000 53.837288 61.391865 64.756970 69.986085 65.913194 63.352986 66.369195 64.735454 71.164108

2


1 1.00 1 0 0	1.000000

3


8 1.34 1.37 1.40 1.44 1.91 1.95 1.96 1.97 5 1 4 2 7 4 6 0 3 2 6	1.515518 1.752724 1.939879 1.387008 1.712233

x y = e^{\ln x + \ln y}

$xy = e^{\ln x + \ln y}$ . .

决断

О (1)

$(1)$ ,

O (1)

$O(1)$ .

. sums,

s u m s [i] = a [0] + a [1] + \dots + a [i]

$sums[i] = a[0] + a[1] + \dots + a[i]$ .

s u m s [i] = s u m s [i - 1] + a [i]

$sums[i] = sums[i - 1] + a[i]$ ,

O (n)

$O(n)$ .

l

$l$

r

$r$ —

s u m s [r] - s u m s [l - 1]

$sums[r] - sums[l - 1]$ . ,

r - l + 1

$r - l + 1$ .

O (1)

$O(1)$

O (n)

$O(n)$ .

. , , , . , ,

e

$e$ . ,

\ln ((a [l] \cdot . . . \cdot a [r])^{\frac{1}{r - l + 1}}) = \frac{\ln a [l] \cdot \dots \cdot a [r]}{r - l + 1} = \frac{\ln a [l] + \dots + \ln a [r]}{r - l + 1}

$\ln ((a[l] \cdot ... \cdot a[r])^{\frac{1}{r - l + 1}}) = \frac{\ln a[l] \cdot \dots \cdot a[r]}{r - l + 1} = \frac{\ln a[l] + \dots + \ln a[r]}{r - l + 1}$ ,

О (1)

$(1)$ .

: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

K.最后删除

健康）状况

	2
	256Mb
	input.txt
	output.txt

a

$a$

n

$n$ . .

, .

, , .

n

$n$ (

1 \leq n \leq 300 000

$1 \leq n \leq 300 000$ ).

n

$n$

a_{i}

$a_i$ (

0 \leq a_{i} \leq 1 000 000 000

$0 \leq a_i \leq 1 000 000 000$ ).

m

$m$ (

0 \leq m < n

$0 \leq m < n$ ) — , .

m

$m$ — , . , , .

1


10 1 1 5 2 4 3 3 4 2 5	5 1 5 2 4 3

2


1 1000000000	0

3


10 1 2 3 3 2 1 4 1 2 0	5 1 2 3 2 1

决断

unordered_set (C++) / HashSet (Java) / set (Python), . , , . , . , -. reverse

O (n)

$O(n)$ . -

О (1)

$(1)$ ,

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L.公告栏

健康）状况

	3
	256Mb
	input.txt
	output.txt

, .

W \times H

$W × H$ , a b. , . , .

. , , . , .

.

(0, 0)

$(0, 0)$ , —

(W, H)

$(W, H)$ . .

, .

W

$W$ ,

H

$H$

a

$a$ ,

b

$b$ (

1 \leq W

$1 \leq W$ ,

H \leq 100 000

$H \leq 100 000$ ,

1 \leq a \leq W

$1 \leq a \leq W$ ,

1 \leq b \leq H

$1 \leq b \leq H$ ).

n

$n$ (

0 \leq n \leq 100

$0 \leq n \leq 100$ ) — .

n

$n$

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ (

0 \leq x_{l d} < x_{r u} \leq W, 0 \leq y_{l d} < y_{r u} \leq H

$0 \leq x_{ld} < x_{ru} \leq W, 0 \leq y_{ld} < y_{ru} \leq H$ ). , .. .

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ , .

a

$a$ (,

b

$b$ ). .

.

, .

1


11 8 2 7 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	9 0 11 8

2


11 8 7 3 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	4 0 11 3

3


11 8 4 4 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	7 4 11 8

决断

, . ,

W * n

$W * n$ .

x

$x$ (

0

$0$

W - a

$W - a$ ), . ,

x

$x$

x + a

$x + a$ , . , «»

x

$x$

x + a

$x + a$ ,

y

$y$ - . ,

(y_{1}, y_{2})

$(y_1, y_2)$ ,

y_{1}

$y_1$

y_{2}

$y_2$ —

y

$y$ - , .

y_{2}

$y_2$ —

y_{1}

$y_1$ .

,

(0, 0)

$(0, 0)$

(h, h)

$(h, h)$ , . , , , . , , . , , .

.

O (W * n * \log n)

$O(W * n * \log n)$

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7

全面分析SHAD 2020中考试的第一部分

A.当地最低

限制

C.当地最低

D.自己的载体

E.预选赛

F.投影

G.多米诺

H.考试

一，随机变量

J.求平均值

1

2

3

K.最后删除

1

2

3

L.公告栏

1

2

3

More articles: