Try   HackMD

Đề HSG9 - BRVT - 2016: Editorial

Bài 1: Đếm số phong phú (7 điểm)

Cho số nguyên dương

n
(n105)
. Đếm số lượng số nguyên dương
x
(xn)
sao cho tổng các ước của
x
(trừ
x
) phải lớn hơn
x
.

Brute - force:

Ta duyệt qua từng số nguyên từ

1n rồi tính tổng các ước của mỗi số.

Độ phức tạp thời gian:

O(nn).

Code
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int res = 0; for (int i = 1; i <= n; i++) { long long sum = 1; //Duyệt qua các ước của i //j <= sqrt(i) <=> j * j <= i for (int j = 2; j * j <= i; j++) { if (i % j == 0) { if (j * j == i) { sum += j; } else { //Nếu j là ước của i thì i/j cũng là ước của i sum += j + i/j; } } } if (sum > i) res++; } cout << res; return 0; }

Accepted:

Gọi

sumi là tổng các ước của
i
trừ chính nó.

Với mỗi số

i từ
1
đến
n
, ta duyệt qua tất cả các bội của
i
(không tính
i
, tức là từ
2i
trở đi), và tăng
sumi
lên
i
đơn vị.

Đáp án của bài toán là số lượng

i từ
1n
sao cho
sumi>i
.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Lưu ý:

Thuật toán trên được gọi là "sàng ước". Nhiều người nhầm tưởng thuật toán này có độ phức tạp thời gian lớn, tuy nhiên, vì số lượng bội số không ngừng giảm khi số tăng lên, nên thực chất thuật toán này chạy rất nhanh.

Nếu coi

n là giới hạn để duyệt
i
, ta có thể tính được độ phức tạp thời gian của thuật toán này như sau:

i=1nninlogn

Độ phức tạp thời gian:

O(nlogn).

Code
#include <bits/stdc++.h> using namespace std; const int N = 1e5; int n, res; int sum[N+5]; int main() { cin >> n; for (int i = 1; i <= n; i++) { //Duyệt qua các bội của i for (int j = i * 2; j <= n; j += i) { sum[j] += i; } } for (int i = 1; i <= n; i++) { if (sum[i] > i) { res++; } } cout << res; return 0; }

Bài 2: Ghép số (7 điểm)

Cho số nguyên dương

n
(n20)
. Đếm số cách tạo ra số có
n
chữ số thỏa mãn các điều kiện sau:

  • Các chữ số là
    0
    ,
    1
    , hoặc
    2
    .
  • Là số chia hết cho
    5
    .
  • Không có
    2
    chữ số liền kề giống nhau.
  • Chữ số đầu tiên lớn hơn
    0
    .

Brute - force:

Quay lui đơn thuần, thử tất cả cả trường hợp, sau đó mới kiểm tra có thỏa điều kiện hay không.

Độ phức tạp thời gian:

O(3n).

Accepted:

Cần đặt thêm nhánh cận vào thuật toán quay lui brute - force (chỉ thử các trường hợp có thể thỏa điều kiện).

Nhánh cận trong thuật toán quay lui được hiểu là những điều kiện để dừng hàm quay lui sớm hơn bình thường hoặc chỉ duyệt qua những trường hợp đúng, nhằm tránh việc duyệt qua những trường hợp thừa (chắc chắn sai). Từ đó giảm thời gian chạy chương trình đáng kể.

Nhánh cận được đặt trong bài trên là các điều kiện của đề bài.

Độ phức tạp thời gian:

O(32n3)

Giải thích độ phức tạp thuật toán:

Nhận xét:

  • Có 2 cách chọn số đầu tiên
    (1,2)
    .
  • Có 1 cách chọn số cuối cùng
    (0)
    .
  • Số cách chọn
    n2
    số còn lại ở giữa là số cách tạo dãy độ dài
    n2
    từ các chữ số
    0,1,2
    sao cho không có 2 số liền kề giống nhau.

Ta có thể tính được số cách chọn

n2 số còn lại bằng quy hoạch động.

Gọi

dpi là số cách tạo dãy độ dài
i
từ các chữ số
0,1,2
sao cho không có 2 số liền kề giống nhau.

Công thức quy hoạch động:

  • dp1=3
    .
  • dpi=2dpi1
    (Do không được điền số giống số trước đó).

dpn2=32n3

Tức là có

32n3 trường hợp phải duyệt trong thuật toán quay lui nhánh cận ở trên.

Bài toán này cũng có thể được giải bằng thuật toán quy hoạch động nói trên.

Code
#include <bits/stdc++.h> using namespace std; const int N = 21; int n; int A[N+5]; long long res; void backTrack(int x) { //Quay lui đến n-1 vì số thứ n luôn luôn là số 0 if (x == n) { res++; return; } for (int i = 0; i < 3; i++) { //Số đầu tiên phải khác 0 if (x == 1 && i == 0) { continue; } //Hai số liên tiếp phải khác nhau if (i == A[x-1]) { continue; } //Số kế cuối phải khác 0 if (i == 0 && x == n-1) { continue; } A[x] = i; backTrack(x+1); } } int main() { cin >> n; if (n == 1) { cout << 0; return 0; } A[0] = -1; backTrack(1); cout << res; return 0; }

Bài 3: Nối xích (6 điểm)

Cho một dãy

n mắt xích có độ bền
A1,A2,...,An
. Nếu nối mắt xích
i
i+1
(1i<n)
thì độ bền của mối nối là
di
với:

di={0khiai>ai+1.ai+1aikhiai<ai+1

Tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối và độ bền của từng mắt xích là lớn nhất.

Brute - force:

Quay lui đơn thuần, thử tất cả cả trường hợp tất cả trường hợp sắp xếp của mảng

A rồi lấy tổng lớn nhất.

Độ phức tạp thời gian:

O(n!).

Accepted:

Nhận xét: Tổng độ bền các mắt xích không đổi, do đó chỉ cần tìm cách sắp xếp các mắt xích sao cho tổng độ bền của các mối nối lớn nhất.

Không mất tính tổng quát, giả sử có bốn mắt xích

x,y,z,t được xếp liền kề nhau thỏa mãn
x<y<z<t
thì ta có tổng độ bền của các mối nối là:

tz+zy+yx=tx

Thay vì thêm mắt xích
y,z
vào giữa
x
t
, ta nên xếp
x
t
vào cùng một mối nối ngay từ đầu, để có thể dùng
y
z
vào một mối nối khác. Khi đó tổng độ bền ta đạt được là:

tx+zy>tx

Vậy để đạt độ bền lớn nhất thì ta sẽ lặp đi lặp lại thao tác lấy mối nối nhỏ nhất chưa được nối và nối với mối nối lớn nhất chưa được nối.

Do đó, ta sắp xếp mảng

A tăng dần:
A1<A2...An1<An
và thực hiện nối như sau:

  • A1
    nối với
    An
    .
  • A2
    nối với
    An1
    .
  • Ai
    nối với
    Ani+1
    .

Nếu sắp xếp dựa theo mối nối, ta được mảng:

B1<B2>B3<B4...

B1 nối với
B2
,
B3
nối với
B4
,

Đáp án:

B2B1+B4B3+=AnA1+An1A2+

Độ phức tạp thời gian:

O(nlogn).

Code
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int n; int A[N+5]; long long res; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> A[i]; res += A[i]; } sort(A+1, A+1+n); int i = 1, j = n; while (i < j) { res += (A[j] - A[i]); i++; j--; } cout << res; return 0; }