👩🏽‍🔧 🌮 📔 SHAD中的考试算法 💪🏿 🤷🏻 ♥️

你好！我的名字叫Alexander Kurilkin，我正在ShAD Helper教授算法课程。在这篇文章中，我将分析过去几年的入学考试中的一些任务，以便您可以看到等待的内容，并了解我们在课程中可以教给您什么。希望您与我分享对算法有趣任务的热爱，并通过阅读本文获得真诚的荣幸！所以，让我们开始吧...

2016/05/28，第4期

给出 $n$ 段 $[a_i; b_i]$ 。我们称分段嵌套索引 $[a_i; b_i]$ 包含它的细分的数量。建议一种算法，该算法确定集合中是否存在嵌套索引超过1000的段。时间限制为 $O(n \log n)$ ，以增加内存- $O(n)$ 。

决断

, "". , - , , - , . " ", $a_i$ , " ", $b_i$ . . , 1. , 1000, , — 1000 . — - , , . , (std::multiset C++), . , — 1000 . , , , , *set.begin(), ( 1000 ) . , ! , , . , . , , !

: 1000 ? , - 1000 , 1000 , - , ? , - 1000 , , , , , .

, . $O(n \log n)$ , $O(n \log 1000) = O(n)$ O(n) . , : $O(n \log n)$ . $O(n)$ .

2019/05/25，第4号

给出了一个实数数组 $A$ 。建议为每个元素查找的算法 $A$ 最靠近右边的元素的索引，至少是其大小的两倍。如果没有这样的元素，则应返回该值。 $None$ 。时限 $O(n \log n)$ ，以增加内存- $O(n)$ 。

决断

$(, )$ . ( $None$ ), $(A[n - 1], n - 1)$ , . $i$ . , , , ? , . , , , ? . , . , $(A[i], i)$ . , , ? , ( ) $i$ . (, , std::vector) , $A[i] \cdot 2$ . , ( ), , $None$ .

, , ? , O(n), $n$ , $O(n \log n)$ , . , , , $O(n)$ .

06/10/12，第5号
在该组 $n$ 每个人可能认识也可能不认识对方（如果 $A$ 知道 $B$ ，它并不遵循 $B$ 知道 $A$ ）所有相识均由布尔矩阵给出 $n×n$ . — , , . , , . — $O(n)$ , — $O(1)$ .

$K_{ij} = 1$ , $i$ - $j$ - , 0 .

, $K_{ij} = 1 ~ (i \neq j)$ , $i$ - , - , $j$ - , $K_{ij} = 0$ , $j$ - , $i$ - .

: — . , 1, , $l$ . , ( 0), , , , , - ( , , $l$ ). $l$ - — , $(l, l + 1)$ . 1, , , . , . , , , ( ), , , , . , , , $O(n)$ , , $O(n)$ . : $O(n)$ . , , (, ), $O(1)$ . !

, , !

2019, -, D

, 2
: 2
: 256Mb

$n$ $m$ . $q$ « $i$ 1». .

— , . , .

. , , .

$n$ $m$ — ( $1 \le n, m \le 10^5, 2 \le n)$ . $m$ $u$ , $v$ , $w$ . , $w$ , $u$ $v$ ( $1 \le u, v \le n, 1 \le w \le 10$ ).

$q$ — ( $1 \le q \le 10^5$ ). $q$ $id$ ( $1 \le id \le m$ ). , $id$ . .

$q$ 用空格或换行符分隔的数字-每个请求后最小生成树的权重。

决断

, , 99% . .

" $u$ $v$ ", $k$ . $u$ $v$ $k$ ( . $k+1$ , , $u$ $v$ $> k + 1$ , $k + 1$ , , ́ ), , 1. . , , . $O(n)$ , , , $O(\log n)$ link-cut tree, , ( ). .

1 10, 10 ( , ). $k$ - $\le k$ . . : , ( ) , , . , , , , .

$(u, v)$ 1 $k$ . $k$ - . , $k$ - $u$ $v$ . , $k+1$ , , . , $u$ $v$ $k$ - , 1. $u$ $v$ $k$ - , $\le k$ , .

, , ? $O(\alpha(n))$ , $O(10 \cdot m \log n) = O(m \log n)$ . , Accepted :)

SHAD中的考试算法

More articles: