DUT - Train

https://docs.google.com/spreadsheets/d/154ndCLFTvT_dS5o_Dh2ikAJwd4fMo8xC9roMc9q_RAU/edit?usp=sharing

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Check nguyên tố bằng Java

import java.util.*;  import java.math.*;     class Main  {      //Function to check and return prime numbers      static boolean checkPrime(String n)      {          // Converting long to BigInteger          BigInteger b = new BigInteger(n);             return b.isProbablePrime(1);      }         // Driver method      public static void main (String[] args)                           throws java.lang.Exception      {         String n = "1000000000000000000";         System.out.println(checkPrime(n));      }  } Link: https://www.onlinegdb.com/
Đọc thêm

Học về Segment Tree

Hình ảnh
Segment Tree được sử dụng trong trường hợp có nhiều truy vấn phạm vấn phạm vi trên mảng và sửa đổi các phần tử của cùng một mảng. Ví dụ, tìm tổng của tất cả các phần tử trong một mảng từ chỉ số L đến R, hoặc tìm giá trị nhỏ nhất của tất cả các phần tử trong 1 mảng từ chỉ số L đến R. Những vấn đề này có thể được giải quyết dễ dàng với một trong những cấu trúc dữ liệu linh hoạt nhất. Segment Tree. Segment Tree là gì ? Segment Tree cơ bản là một cây nhị phân nhằm lưu trữ một đoạn. Mỗi nút trong Segment Tree đại diện cho một đoạn. Xét mảng A có kích thước N, và 1 cây Segment Tree T tương ứng. 1. Gốc của cây T sẽ đại diện cho cả mảng: A[0:N-1]. 2. Mỗi lá của cây T sẽ đại diện một phần tử A[i] thỏa mãn 0<=i<N. 3. Mỗi nút nút của cây T đại diện cho một đoạn A[i:j] với 0<=i<j<N. Gốc của Segment Tree đại diện cho cả mảng A[0:N-1]. Sau đó nó chia đôi thành một nữa và 2 đứa trẻ của gốc sẽ đại diện cho A[0:(N-1)/2]  và A[(N-1)/2+1;(N-1)]. Vì vậy, ở mỗi bước, Segment lại...
Đọc thêm

Chuyên đề về BIT (Binary Index Tree)

Hình ảnh
Binary Indexed Tree còn gọi là Fenwick Tree cung cấp 1 cách để biểu diễn 1 mảng các số trong 1 mảng, cho phép tổng tiền tố được tính một cách hiệu quả. Ví dụ, 1 mảng [2,3,-1,0,6] được cho, thì tổng tiền tố của 3 phần tử đầu tiên [2,3,-1] là 2+3+(-1)=4. Tính tổng tiền tố một cách hiệu quả là hữu ích trong nhiều hoàn cảnh. Chúng ta hãy bắt đầu với 1 ví dụ đơn giản. Cho 1 mảng a[], và 2 loại phép toán được biểu diễn trên nó. 1. Thay đổi giá trị được lưu tại chỉ số i. (Cái này được gọi là phép toán update điểm). 2. Tìm tổng một tổng của 1 tiền tố có độ dài là k (Cái này được gọi là truy vấn range sum). Một cách tiếp cận theo kiểu implement là: ``` int a [] = { 2 , 1 , 4 , 6 , - 1 , 5 , - 32 , 0 , 1 }; void update ( int i , int v ) //assigns value v to a[i] { a [ i ] = v ; } int prefixsum ( int k ) //calculate the sum of all a[i] such that 0 <= i < k { int sum = 0 ; for ( int i = 0 ; i < k ; i ++) sum += a [ i ]...
Đọc thêm