Bài 2 lớp 11 không biết xài cặp ghép độ phức tạp có ok không nhỉ?

10^8 cạnh --> ko đc

Nghe thầy Hoàng nói hieratic tí là ra. 

Bài 2 lớp 11:

Giả sử M <= N (tức là số nam ít hơn số nữ, trường hợp kia làm tương tự)

Trước hết gọi A[i], B[i] là số nam, số nữ hát bài i

Xét 2 trường hợp:

i) Tồn tại i sao cho A[i] + B[i] > N. Khi đó cách ghép tối ưu là:

+ Nam hát bài i ghép với nữ hát bài khác

+ Nữ hát bài i ghép với nam hát bài khác

ii) Không tồn tại i như trên. Khi đó đáp án là M (số nam) và cách ghép như sau:

Lấy bất kì một người nam, giả sử ở nhóm i, ghép với một người nữ ở nhóm j (j khác i) sao cho có A[j] + B[j] ở thời điểm đó là lớn nhất.

Phần chứng minh để lại cho các bạn :)

Bài 2 lớp 10 mình không dùng sàng nguyên tố mà chạy như thế này:

Có 1 mảng p[] chứa các số nguyên tố từ 2 -> 1e6.
Ban đầu p[] chứa 4 số 2, 3, 5, 7.
for i=0 -> p[i]^2<=n && i<p.size():
    if (n mod p[i]==0) prime=false;

Số số nguyên tố <=1e6 chỉ là khoảng 79k, mà số số nguyên tố <=1e3 chỉ là 168, khá bé.

Như vậy, độ phức tạp để sinh ra các số nguyên tố trong khoảng \([2,10^6]\) là \(O(n*pi(\sqrt{n})) \approx 10^6*168\) (trong lúc chạy có tối ưu 1 chút để đảm bảo chạy ít hơn 10^6 số một chút)

Còn hàm phân tích ra thừa số nguyên tố thì mình chia a cho các số nguyên tố thuộc p[], sau khi được a sau quá trình chia (tệ nhất là \(a \approx 5*10^8\)), rồi chia tiếp cho các số nguyên tố trong đoạn 2 -> \(\sqrt{a}\), lúc này \(\sqrt{a} \approx 22360\) và \(pi(a) \approx { a \over \ln(a) - 1 } \approx { 22360 \over \ln(22360) -1 } = 2480\). Như vậy độ phức tạp tổng là \(O(\sqrt{n} * pi(\sqrt{n}) * \log n)\). Không biết với độ phức tạp này có qua được 2 subtask cuối hay không nhỉ?

P/s: Hàm \(pi(n)\) là số số nguyên tố <= n.

ai có sol bài 3 lớp 10 không nhỉ 

Cách làm của mình : Khi phân tích (ab) ra thừa số nguyên tố các số mũ là k1, k2, k3.. thì kết quả là (2*k1+1)*(2*k2+1)*(2*k3+1)*...

3 sub đầu thì T bé cho nên để phân tích a và b ra thừa số nguyên tố thì cứ chạy đến căn bình thường

sub cuối T = 10^6 , a, b <= 10^6. Trong quá trình sàng nguyên tố từ 1 đến 10^6, m sẽ đánh dấu xem một số nguyên từ

1-> 10^6 chia hết cho những snt nào (tối đa 1 số <= 10^6 chỉ chia hết cho 6 snt thôi) . Một truy vấn a b thì việc phân tích ra thừa số nt chỉ mất đpt là log thôi. 1 cặp ab sẽ có đpt O(loga+logb)

Cách của mình, khá trâu, và mình nghĩ khá dễ chết 2 subtask cuối:

Có 1 nhận xét là a[i]<=1000, tức là khi biểu diễn sang nhị phân thì độ dài tối đa của a[i] khi biểu diễn sang hệ nhị phân là 10 -> kết quả của các phép tính (x op y) (với op là các phép and, or, xor) sẽ có kết quả không quá 1023.

Dùng 2 vector 2 chiều AND và OR để lưu lại kết quả:

Khởi tạo i, j:  \(AND[a[i]\ and\ a[j]].push\_back(j)\ (i<j \leq n-2)\)
OR[i][] lưu lại các chỉ số j sao cho \(\forall n-1\geq j > AND[k][p]:a[j]\ or\ OR[i][AND[k][p]] = i\ (p \leq AND[k].size())\) (vì sao \( n-2\geq p\) thì các bạn tự hiểu nhé)

Cuối cùng, đếm xem có bao nhiêu chỉ số j mà \(i\ xor\ j \in [l,r]\ (OR[i][k]<j \leq n;\ k \leq OR[i].size())\)

Độ phức tạp là \(O(1024*n^2)\), nhưng vì n<=4000 nên rất dễ TLE.

Có thể đặt cận để giảm thời gian chạy xuống 1 chút :3

Còn 1 cách sol chuẩn (thì phải) là dp 3 chiều, nhưng minh chưa code :3

dp[i][v][typ] Số cách đến vị trí thứ i tạo đc giá trị v loại toán tử cuối cùng sử dụng là typ với 

0 : 0 sử dụng

1 : and

2 : or

3 : xor

kết quả = dp[i][v][3] với i = 1 -> n v = l -> r

Theo mình thấy thì trường hợp xấu nhất có độ phức tạp không lớn như vậy.

Có ai có bảng điểm k ? cho m xin với

(Theo em nghĩ)

Với mỗi số a[i] thì ta tính toán với phép XOR trước với các tổng OR ( cộng thẳng vào biến kết quả) tiếp theo thực hiện phép OR với các tổng AND, và phép AND với các số đằng sau, như vậy thì dữ liệu được giảm đi đáng kể ( Từ mảng 3 chiều giảm xuống còn 2 mảng một chiều và một biến kết quả).

Bạn có thể chỉ cho mình trường hợp xấu nhất không? tks bạn :3

mà dạo này Vnoi không cập nhật điểm nữa hở a :(

Anh up đề bài cùng test lên cho mn cùng làm đi a :)

Mọi người vui lòng cho mình hỏi bài 1 lớp 10 tí ạ. Đây là code do mình viết

https://ideone.com/cdsphK

Khi mình để khai báo

var a: array [1..1000000,1..1000000] of longint;

thì nhận thông báo lỗi Exitcode 216

Khi mình khai báo lại

var a: array [1..1000,1..1000] of longint;

thì không bị lỗi trên.

RAM máy mình chỉ 1GB có phải là vấn đề hay do mình không biết làm chỗ này. Mong mọi người chỉ giúp, mình tự học nên nhiều cái còn mù mờ.

Xin chân thành cám ơn.

Bạn để mảng 10^6*10^6 = 10^12 phần tử thì bị tràn bộ nhớ nhé.

Bình thường mảng không được để quá khoảng 10^8 phần tử, nếu không thì tràn bộ nhớ.

Cám ơn bạn. Theo đề bài thì giới hạn là:

- Có 25% số test ứng với 25% số điểm của bài có m, n ≤ 50;
- Có 25% số test khác ứng với 25% số điểm của bài có m = 1; n ≤ 10⁶ .
- Có 25% số test khác ứng với 25% số điểm của bài có m, n ≤ 1000.
- Có 25% số test còn lại với 25% số điểm của bài có m x n ≤ 10⁶ .

Mình cũng thấy giới hạn phần tử chỉ 10⁶, nhưng để ăn hết test thì mình không biết làm thế nào nên đành khai báo như thế. Bạn vui lòng chia sẽ cách làm với.

Xin chân thành cám ơn.

Có 2 cách:

C1. Dùng vector 2 chiều trong c++.

C2. Đơn giản hơn, đó là biến mảng 2 chiều thành mảng 1 chiều.

Với 1 mảng 2 chiều b[1..m,1..n] ta biến thành mảng 1 chiều a mà a[(i-1)*n+j]:=b[i,j] (1<=i<=m; 1<=j<=n)