👨‍👨‍👧 👨🏿‍💼 🌻 Algoritma untuk ujian di SHAD 💫 🐝 👭

Halo! Nama saya Alexander Kurilkin, dan saya mengajar kursus tentang algoritma di ShAD Helper. Dalam posting ini saya akan menganalisis beberapa tugas dari ujian masuk beberapa tahun terakhir, sehingga Anda dapat melihat apa yang menanti Anda dan memahami apa yang bisa kami ajarkan pada Anda di kursus kami. Saya harap Anda berbagi cintaku untuk tugas-tugas menarik pada algoritma dan akan menerima kesenangan yang tulus dari membaca posting ini! Jadi, mari kita mulai ...

28/05/2016, No. 4

Diberikan $n$ segmen $[a_i; b_i]$ . Kami menyebutnya indeks bersarang segmen $[a_i; b_i]$ jumlah segmen yang mengandungnya. Sarankan algoritma yang menentukan apakah ada segmen di set dengan indeks bersarang melebihi 1000. Batas waktu adalah $O(n \log n)$ , dengan memori ekstra - $O(n)$ .

Keputusan

, "". , - , , - , . " ", $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)$ .

05/25/2019, No.4

Array bilangan real diberikan $A$ . Sarankan algoritma yang ditemukan untuk setiap elemen $A$ indeks dari elemen yang paling dekat ke kanan, setidaknya dua kali ukurannya. Jika tidak ada elemen seperti itu, maka nilainya harus dikembalikan. $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)$ .

10.06.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$ ). Ini berarti Anda perlu mengurangi berat iga satu per satu. $id$ . Tepi diberi nomor dari satu dalam urutan dalam file input.

Format output

Mencetak $q$ nomor dipisahkan oleh spasi atau jeda baris - berat pohon rentang minimum setelah setiap permintaan.

Keputusan

, , 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 :)

Algoritma untuk ujian di SHAD

More articles: