changed 2 months ago  
Linked with GitHub

OLP MTTN 2023 - Sơ loại bảng Không chuyên

Bài 1 - THREE

Ta có: \(3 = 1+1+1 = 1+2\), tức có 3 cách tạo thành tổng bằng 3.

  • Những phần tử \(3\) chỉ tạo thành các tập \(\{3\}\)
  • Những phần tử \(2\) chỉ có thể ghép thêm với \(1\) để tạo thành \(\{1,2\}\)
  • Những phần tử \(1\) có thể ghép với \(2\) (như trên), hoặc ghép thêm 2 số \(1\) khác thành bộ \(\{1, 1, 1\}\).
    Tuy nhiên, cách sau tốn nhiều số hơn, mà muốn tạo thành nhiều tập thì phải ưu tiên tập có ít số hơn

\(\Rightarrow\) thứ tự ưu tiên tạo tập số: \(\{3\}, \{1, 2\}, \{1,1,1\}\).






// nhập a, b, c
int tap3 = c;
int tap12 = min(a, b); a -= tap12, b -= tap12;
int tap111 = a / 3;
int answer = tap3+tap12+tap111;

Bài 2 - TRANSFORM

Với một số \(X\) bất kỳ:

  • nếu chọn phép nhân đôi: \(2X\) là một số chẵn
  • nếu chọn phép viết số 1 đằng sau: \(\overline{X1}=10X+1\) là một số lẻ.

\(\Rightarrow\) để tìm trạng thái liền trước của \(X\):

  • Nếu \(X\) chẵn thì chỉ có thể kết luận trạng thái trước dùng phép nhân đôi để tạo ra \(X\)
  • Nếu \(X\) lẻ thì chỉ có thể kết luận trạng thái trước dùng phép viết số 1 đằng sau để tạo ra \(X\) \(\Rightarrow\) \(X\) chia \(10\) phải dư \(1\).

Vì thế, thay vì tìm cách tạo \(B\) từ \(A\), ta sẽ truy ngược từ \(B\) về \(A\).

  • Nếu trong quá trình truy ngược mà tìm ra \(A\) \(\Rightarrow\) dừng luôn và kết luận tạo được
  • Nếu trạng thái hiện tại lẻ và không có chữ số cuối dùng là \(1\) (tức chia 10 dư 1), và trong cả quá trình không có \(A\) \(\Rightarrow\) không tạo được.














bool check(int a, int b) {
    while (b > 0) {
        if (a == b) return true;
        
        if (b % 2 == 0) b /= 2;
        else {
            if (b % 10 == 1) b /= 10;
            else break; // dừng vòng lặp
        }
    }
    
    // xuống đây tức là không có a
    return false;
}

Bài 3 - SWORD

Hướng nghĩ:

  • Đầu tiên, có những con boss nào có \(p_i \leq S\), thì ta tiêu diệt hết, và \(S \leftarrow S + g_i\) tương ứng.
  • Sau khi diệt hết đợt 1, \(S\) tăng lên, từ đó ta diệt thêm các con boss có độ khó \(p_i\) cao hơn \(\rightarrow\) cho hết các con này vào đợt 2
  • Tương tự, sau đợt 2 sẽ tới đợt 3 với các con boss khó hơn, \(\dots\) cho tới khi không còn boss hợp lý.

\(\Rightarrow\) các con boss sẽ được tiêu diệt theo thứ tự \(p_i\) tăng dần.
\(\Rightarrow\) sắp xếp các boss theo thứ tự \(p\) (nếu cùng \(p\) thì \(g\) như nào không quan trọng, vì cùng \(p\) sẽ cùng bị tiêu diệt một lần, chứ không có chuyện hai boss cùng \(p\) mà một con bị diệt một con thì không)


















struct Boss{int p, g;};
bool operator < (Boss a, Boss b); // sắp xếp theo Boss::p

int n; long long S;
Boss bosses[MAX];

main() {
    // nhập Boss
    sort(bosses + 1, bosses + 1 + n);
    int count = 0;
    for (i = 1 -> n) {
        if (bosses[i].p > S) break; 
        S += bosses[i].g; count++;
    }
    
    cout << count;
}

Bài 4 - COLORBOX

Lưu ý: Không nhất thiết phải giữ lại toàn bộ các màu (các giá trị khác nhau) có trong mảng, tức được phép mất đi một(vài) màu.

Ở đây giả sử ta bắt buộc phải xóa ít nhất một đoạn. Nếu các phần tử khác nhau đôi một, lập tức in ra \(0\) rồi kết thúc chuogw trình.

Subtask 1 - \(n \leq 10^2\)

  1. Chọn ra một đoạn \(l, r\)
  2. Đếm xem phần còn lại (gồm \([1; l-1]\) và \([r+1; n]\)) có hai cây màu nào trùng màu không.
  3. Tìm đoạn \([l;r]\) ngắn nhất trong số các đoạn thỏa mãn điều kiện 2

Để kiểm tra điều kiện 2, ta sẽ tạo một mảng đếm phân phối dpp[] số lần xuất hiện của các màu, và một biến cnt đếm số màu xuất hiện nhiều hơn một lần.

  • Khi dpp[màu]++, nếu dpp[màu] == 2 thì cnt++.

















int dpp[MAX_N], cnt = 0;

int answer = 0;
for (l = 1 -> n) for (r = l -> n) {
    for (i = 1 -> l-1) {
        ++dpp[a[i]]; if (dpp[a[i]] == 2) cnt++;
        // if (++dpp[a[i]] == 2) cnt++;
        // cnt += (++dpp[a[i]] == 2);
    }
    for (i = r+1 -> n) cnt += (++dpp[a[i]] == 2); // lưu ý: ++a != a++
    
    if (cnt == 0) // không có vi phạm
        answer = max(answer, r-l+1);
    // sau đó nhớ xóa hết dữ liệu trong mảng dpp và biến cnt.
}

cout << answer;

Độ phức tạp: \(\mathcal{O(n^3)}\); gồm cho \(\mathcal{O(n^2)}\) cho việc chọn cặp \((l,r)\) và \(\mathcal{O}(n)\) cho việc đánh dấu màu.

Subtask 2 - \(n \leq 10^3\)

Khi duyệt các cặp \((l, r)\), với \(l\) cố định thì mỗi lần chỉ thay đổi \(r\) đi \(1\) đơn vị \(\Rightarrow\) bỏ bớt một số ra khỏi tập các số còn lại đang xét.

\(\Rightarrow\) thay vì với mỗi cặp \((l, r)\) ta duyệt các số nằm ngoài đoạn, để lợi dụng sự thay đổi nhỏ này:

  • với mỗi \(l\), ban đầu ta xét tất cả các số trong mảng \(A\).
  • khi duyệt \(r\), ta lần lượt bỏ đi \(A[r]\) ra khỏi tập các số còn lại.

Ví dụ:
Giả sử \(n=4\)

l r các số được xét
1 chưa duyệt \(A_1,A_2,A_3,A_4\)
1 1 \(A_2,A_3,A_4\)
1 2 \(A_3,A_4\)
1 3 \(A_4\)
1 4
2 chưa duyệt \(A_1,A_2,A_3,A_4\)
2 2 \(A_1,A_3,A_4\)
2 3 \(A_1,A_4\)
2 4 \(A_1\)
3 chưa duyệt \(A_1,A_2,A_3,A_4\)
3 3 \(A_1,A_2,A_4\)
3 4 \(A_1,A_2\)
4 chưa duyệt \(A_1,A_2,A_3,A_4\)
4 4 \(A_1,A_2,A_3\)

Vì thế, ta cần hỗ trợ thêm phép xóa phần tử:

  • Sau khi --dpp[màu], nếu dpp[mau] == 1 thì cnt--









for (l = 1 -> n) {
    for (i = 1 -> n) cnt += (++dpp[a[i]] == 2)
    
    for (r = l -> n) {
        cnt -= (--dpp[a[i]] == 1);
        
        if (cnt == 0) answer = max(answer, r-l+1);
    }
}

Độ phức tạp: \(\mathcal{O}(n^2)\)
Ta có thể cải tiến thuật toán bằng cách dừng \(r\) ngay khi cnt == 0, khi đó \(r\) là vị trí cuối đoạn tối thiểu để phần ngoài có các phần tử độc nhất, từ đó dựng lên các đoạn ngắn nhất. (*)

Subtask 3+4 - \(n \leq 10^6\)

Nhận thấy: Với một đoạn \((l, r)\) bất kỳ:

  • Nếu \(l\) tăng thì phần ngoài thêm được một phần tử
  • Nếu \(l\) giảm thì phần ngoài giảm đi một phần tử
  • Nếu \(r\) tăng thì phần ngoài giảm đi một phần tử
  • Nếu \(r\) giảm thì phần ngoài thêm được một phần tử.

Từ (*), khi ta thử tìm \(r\) nhỏ nhất thỏa mãn điều kiện của từng giá trị \(l\), ta thấy khi \(l\) tăng thì \(r\) cũng tăng
Vì khi \(l\) tăng thì bên ngoài thêm một phần tử:

  • nếu không trùng thì giữ \(r\)
  • nếu có trùng thì \(r\) phải tăng để xóa bớt phần tử cho tới khi không còn trùng nữa.

Vì thế, cũng như lúc nãy, ta dựng dpp[] và cnt cho toàn mảng \(A\)

  • Đầu tiên, với \(l=1\), ta tìm \(r\) tối thiểu thỏa mãn, tức loại bỏ khỏi mảng đpp như thuật toán ở hai subtask trên cho tới khi cnt==0
  • Tiếp theo, \(l\) tăng thành 2 \(\Rightarrow\) thêm A_1 vào dpp và cập nhật cnt. Nếu cnt!=0 thì ta tăng \(r\) (loại bỏ \(A_r\) rồi tăng \(r\) lên 1đv) cho tới khi cnt==0
  • Tương tự, tăng \(l\) thành 3, 4, 5, … tương ứng với cho \(A_2, A_3, A_4 \dots\) vào mảng rồi cập nhật \(r\), cho tới khi \(r > n\) (tức không có \(r\) thỏa mãn) thì dừng.














for (i = 1 -> n) cnt += (++dpp[a[i]] == 2)

  
r = 0;
for (l = 1 -> n) {
    while (cnt > 0) {
        r++; if (r > n) break;
        cnt -= (--dpp[a[r]] == 1);
    }
    if (r > n) break;
    answer = max(answer, r-l+1);
    
    cnt += (++dpp[a[l]] == 2);
}
Select a repo