lqdoj

@lqdoj

Private team

Joined on Jul 24, 2022

  • Dãy đèn Đề Có $n$ bóng đèn, lúc đầu tắt hết. Trong mỗi lượt, có thể dùng 1 thao tác để biến một đèn: Từ tắt $\rightarrow$ xanh Từ xanh $\rightarrow$ đỏ Từ đỏ $\rightarrow$ tắt Hỏi dùng đúng $t$ thao tác,có bao nhiêu cách để dãy cuối cùng có $A$ đèn xanh, $B$ đèn đỏ.
     Like  Bookmark
  • BFS Labyrinth Dùng BFS nhưng: trên lưới truy vết: lưu lại hướng đi tới ô $(x,y)$ bất kì. Monsters BFS đa nguồn Tính khoảng cách ngắn nhất từ 1 quái vật tới ô $(x,y)$ bất kì, gọi là $d(x,y)$.
     Like  Bookmark
  • Đệ quy là gì? Thứ tự thực hiện hàm: def f(a,b): print('Xin chao f(',a,b,')') print(a * b) print('Tam biet f') def g(x): print('Xin chao g(',x,')')
     Like  Bookmark
  • Bài 1 - Thập phân Đề bài Cho số thực $x$, làm tròn số $x$ tới số nguyên gần nhất, nếu có nhiều số gần nó thì in ra số nhỏ nhất Solution Tách thành phần nguyên và phần thập phân Để tính phần nguyên ban đầu, ta dùng ép kiểu int(x) Nếu phần thập phân $\le 0.5$ thì giữ phần nguyên Ngược lại, tăng phần nguyên lên 1 đơn vị.
     Like  Bookmark
  • Increasing Array Cứ duyệt và tăng các số từ đầu đến cuối. Nếu gặp $a_i < a_{i-1}$, tăng $a_i$ lên tới bằng $a_{i-1}$ là đủ Permutations Giống dạng bài A,B div.2 Codeforces. Một cách làm: in ra chẵn trước, lẻ sau Bit Strings $2^n$, nhớ $\mod M$ cẩn thận
     Like  Bookmark
  • Lần 2: 26/3 Bảng A Vẽ hình Đặt tâm tại $(0,0)$. Bán kính lấy $r = 1$, khoảng cách giữa tâm 2 hình tròn kề nhau là $2r$ Vẽ từng lớp Giả sử ô đầu tiên tại lớp thứ $i$ là ô ở trái cùng . Xóa xâu Xâu chứa khác $A,B,C \Rightarrow$ No
     Like  Bookmark
  • Link contest. Cần join group CSES trước. Checkpoint 1: Sort, Binary Search, Two Pointer Distinct sort lại hoặc dùng map, hoặc set: cout << s.size() Apartments: Sắp xếp $a,b$ tăng dần rồi ghép (chính là 2-pointer). Ferris
     Like  Bookmark
  • TAB Cơ bản: mảng, for, if Lưu ý: Nếu cộng ba số $10^9$ lại thì có khả năng tràn số (kiểu int chỉ chứa từ $-2^{31} .. 2^{31} - 1)$, tức là tầm 2 tỉ 140 triệu blabla BONUS Trâu Chọn một item muốn thay ra (for), và một item muốn thêm vào. $O(n^2)$ Full
     Like  Bookmark
  • B1: TEAMBUILDING Tóm tắt: Đếm số cách chia mảng $a$ thành các nhóm liên tiếp. Mỗi nhóm thỏa mãn abcxyz. Sub 1: $n \le 20$ Có $n$ người thì sẽ có $n-1$ "khoảng trống" để ta đặt/ không đặt "vách ngăn" vào. Mỗi cách đặt như vậy là một cách chia nhóm. Ví dụ: [Hình vẽ] (soon^TM) Quay lui $O(2^n)$ Sub 2: $n \le 500$
     Like  Bookmark
  • B1: Đường đi có tổng trọng số lớn nhất Vì sao không dùng Dijkstra được? https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag Sol Đặt $dp(u)$ là đường đi dài nhất tới $u$. Để đi tới $u$, thì trước đó ta đã ở một đỉnh $v$ nào đó (mà có cung $v \rightarrow u$ trong input). Công thức: $dp(u) = \max dp(v) + 1$ Vì gọi đệ quy, tính theo chiều ngược thay vì chiều thuận nên chỉ cần
     Like  Bookmark
  • A Đề bảo sao làm vậy (for, if). Vì có dòng này "Đề đảm bảo rằng kết quả luôn luôn là số dương." nên yên tâm làm. B Cần tính số lần xuất hiện của mỗi cặp? Có thể đếm phân phối. Tuy nhiên do không phải là số nên hơi khó đếm. Dùng map là dễ code nhất Hướng khác: chạy trâu $O(n^2)$ để đếm. Hướng 1
     Like  Bookmark
  • QHĐ là gì? Đặt một mảng gì đó ($F$), cần đi tính Tìm một công thức để tính (thường là tính cái sau dựa vào cái trước đó) Ví dụ đơn giản nhất là prefix-sum: S[i] = S[i-1] + a[i] Bài 1: Các bước Tính $a$
     Like  Bookmark
  • C. Nén dãy Cày trâu Full Tính theo lượng đóng góp của mỗi số lúc đầu vào tổng cuối cùng. Ví dụ với số $2$, ta sẽ xem thử nó đã đóng góp bao nhiêu lần để tạo nên số ở hàng $i$, cột $j$? Đây là bài toán QHĐ, số lần đóng góp của mỗi ô bằng hai ô ở trên nó. $F(i,j) = F(i-1,j) + F(i-1,j+1)$. Đây cũng chính là công thức tổ hợp chọn $j$ phần tử trong $i$ số, công thức đếm số đường đi. Ta có đáp án $A=\sum_{i=0}^{n-1}\binom{n-1}{i} \times (i+1)$ Minh họa công thức Theo test ví dụ, ta có $20 = A = 1\cdot 1 + 3\cdot 2 + 3\cdot 3 + 1\cdot 4$
     Like  Bookmark
  • Bài 3 Tóm tắt Số yêu thích = (+/-) Số chính phương Cho trước $k$. Tìm tất cả $A$ mà $A$ và $A+k$ đều là số yêu thích. Tiếp cận Xét $a,b$ dương thì số $k$ có thể rơi vào các TH sau: $a^2 + k = b^2$
     Like  Bookmark
  • Contest SEQ Thật ra không phải là chia để trị mà chỉ là tối ưu QHĐ thôi. $f(l,r) = 1 + \max(f(l,m), f(m+1,r))$ nếu tổng $l..m$ $=$ tổng $m+1..r$. Chứng minh ĐPT? Chia để trị là gì? Có các đặc điểm:
     Like  Bookmark
  • Phương trình: Ăn 87,5% số test Cày trâu, nhớ kiểm tra: chia hết dương Full Giải phương trình diophantine bằng Euclid mở rộng
     Like  Bookmark
  • Day 1, bài 1: Gắp thú bông Bài này đòi hỏi bạn phải có kĩ năng đọc đề tốt. Bắt đầu đọc từ đoạn chợ Helio (Oileh). Tóm tắt Gắp thú bông: Càng nhiều thì càng rẻ (mô tả bởi dãy $s,p$) Những con gấu (thú bông) có trong máy là các đoạn $[l,r]$ Ta biết chính xác thứ tự gắp: bé $\rightarrow$ lớn Cần tìm số lần gáp ít nhất để được $\ge t$ tiền
     Like  Bookmark
  • Bài 1: Bài liên quan Bài 2: blabla Bài 3: Tìm 2 cây khung nhỏ nhất & nhì
     Like  Bookmark
  • author: Bổ Nôm Note Khi học bất kì một ngôn ngữ nào thì tài liệu đầy đủ nhất là tài liệu tham khảo (documentation, referrences) của chính nhà phát hành: https://docs.python.org/3/ (hình thức hơi xấu) Lý thuyết mảng (list) 1. Mảng là 1 tập hợp các phần tử có thể cùng kiểu dữ liệu, hoặc khác kiểu dữ liệu được đặt trong cặp dấu ngoặc $[,]$. Ví dụ
     Like  Bookmark
  • Anh Khá Hints: Exponentation: nhân ấn độ (chia để trị, binary exponentation), định lý Fermat nhỏ Counting Divisor & Common Divisor: sàng nguyên tố. Lưu cnt[x] là số lượng ước của $x$. Sum of Divisors: chia căn đơn giản (xét 2 trường hợp) (x*y) (với mỗi số, đếm số lượng bội) Divisor analysis: Viết dưới dạng PT TSNT để nháp ra công thức. Với phép nhân: cần xử lý code Prime multiples: Bao hàm loại trừ Counting coprime pairs (cũng dùng mảng cnt như trên [nhưng khó hơn vì cần phải nghĩ ra công thức toán & bù trừ ntn]). $f(x)$ :số cặp chia hết cho $x$. $g(x)$: số cặp có GCD đúng bằng $x$
     Like  Bookmark