10 tháng trước

Đề bài của kỳ thi học sinh giỏi các trường THPT chuyên Khu vực Duyên Hải và Đồng bằng Bắc bộ lần thứ 9, năm học 2015-2016 gồm 2 khối 10 và khối 11 đã được đưa lên mạng.

Các bạn có thể download đề bài tại đây : Link download đề bài

Các bạn cùng đọc qua và thảo luận tại topic này nhé :D

Update 1: Link download bộ test kỳ thi

                                                                                                                        VNOI Admins

10 tháng trước

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 tháng trước
Trả lời anhhungcolao
  Hiện bài gốc

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

10 tháng trước
Trả lời RR
  Hiện bài gốc

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

10 tháng trước

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

10 tháng trước

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.

10 tháng trước

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

10 tháng trước
Trả lời sueruan012
  Hiện bài gốc

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)

10 tháng trước
Trả lời namnguyen123
  Hiện bài gốc

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

10 tháng trước
Trả lời namnguyen123
  Hiện bài gốc

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

 

10 tháng trước
Trả lời sueruan012
  Hiện bài gốc

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.

10 tháng trước

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

10 tháng trước
Trả lời bomeki12345678
  Hiện bài gốc

(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ả).

10 tháng trước
Trả lời zandichip
  Hiện bài gốc

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

10 tháng trước
Trả lời RR
  Hiện bài gốc

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

 

10 tháng trước

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

10 tháng trước

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.

10 tháng trước
Trả lời rfadown
  Hiện bài gốc

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ớ.

10 tháng trước
Trả lời sueruan012
  Hiện bài gốc

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 ≤ 106 .
- 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 ≤ 106 .

Mình cũng thấy giới hạn phần tử chỉ 106, 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.

10 tháng trước
Trả lời rfadown
  Hiện bài gốc

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)