Đề HSG9 - BRVT - 2015: Editorial

Bài 1: Thừa kế (7 điểm)

Tính tổng các số chẵn và tổng các số lẻ trong đoạn

$[a,b]$

$(a,b\le {10}^9)$

Ký hiệu toán học cần biết:

$\lceil \frac{a}{b}\rceil$: Phép tính

$\frac{a}{b}$ làm tròn lên.

$\lfloor \frac{a}{b}\rfloor$: Phép tính

$\frac{a}{b}$ làm tròn xuống

$\sum _{i=a}^{b}i$ : Tổng các số từ a đến b

Brute - force:

Duyệt tuần tự từ a đến b và cộng các số chẵn hoặc lẻ vào tổng tương ứng.

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

$O(b-a+1)$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int sumOdd = 0, sumEven = 0;
    for (int i = a; i <= b; i++) {
        if (i % 2 == 0) {
            sumEven += i;
        }
        else {
            sumOdd += i;
        }
    }

    if (sumEven > sumOdd) {
        cout << 1 << "\n";
    }
    else {
        cout << 2 << "\n";
    }

    cout << abs(sumEven - sumOdd);
    
    return 0;
}

Accepted:

Xét đoạn

$[a,b]$, đặt:

• $sE$: Tổng các số chẵn.
• $sO$: Tổng các số lẻ.
• $sTotal$: Tổng các số.

Ta có

$sO=sTotal-sE$. Vậy chỉ cần tính

$sE$ và

$sTotal$!

$$\begin{array}{rl}sTotal& =\sum _{i=a}^{b}i\\ & =\sum _{i=1}^{b}i-\sum _{i=1}^{a-1}i\\ & =\frac{b(b+1)}{2}-\frac{(a-1)a}{2}\end{array}$$

Tổng các số từ

$a$ đến

$b$ bằng tổng các số từ

$1$ đến

$b$ trừ đi tổng các số từ

$1$ đến

$a-1$

Những số chẵn trong đoạn

$[a,b]$ có thể viết lại thành

$2i$ với

$\lceil \frac{a}{2}\rceil \le i\le \lfloor \frac{b}{2}\rfloor$

$$\begin{array}{rl}sE& =\sum _{i=\lceil \frac{a}{2}\rceil }^{\lfloor \frac{b}{2}\rfloor }2i\\ & =2\ast \sum _{i=\lceil \frac{a}{2}\rceil }^{\lfloor \frac{b}{2}\rfloor }i\\ & =2\ast (\sum _{i=1}^{\lfloor \frac{b}{2}\rfloor }i-\sum _{i=1}^{\lceil \frac{a}{2}\rceil -1}i)\\ & =2\ast (\frac{\lfloor \frac{b}{2}\rfloor (\lfloor \frac{b}{2}\rfloor +1)}{2}-\frac{(\lceil \frac{a}{2}\rceil -1)\lceil \frac{a}{2}\rceil }{2})\end{array}$$

sE được tính bằng cách lấy tổng các số từ

$\lceil \frac{a}{2}\rceil$ đến

$\lfloor \frac{b}{2}\rfloor$ nhân đôi lên

Sau khi đã tính được

$sE$ và

$sTotal$, ta tính

$sO$. Như vậy, bài toán đã được giải quyết!

VD: Trong đoạn

$[3,10]$ có những số chẵn sau:

$4,6,8,10$.
Tương ứng với:

$2\ast 2,2\ast 3,2\ast 4,2\ast 5$.

$sTotal=\frac{10\ast (10+1)}{2}-\frac{(3-1)\ast 3}{2}=52$

$\lfloor \frac{a}{2}\rfloor =\lfloor \frac{10}{2}\rfloor =5$

$\lceil \frac{b}{2}\rceil =\lceil \frac{3}{2}\rceil =2$

$sE=2\ast (\frac{5\ast (5+1)}{2}-\frac{(2-1)\ast 2}{2})=28$

$sO=sTotal-sE=52-28=24$

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

$O\left(1\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    
    long long l = (a + 1) / 2, r = b / 2;

    //Lấy max với 0 phòng trường hợp l = r
    long long sE = max(0LL, (r * (r + 1) / 2 - l * (l - 1) / 2) * 2);

    long long sTotal = b * (b + 1) / 2 - a * (a - 1) / 2;

    long long sO = sTotal - sE;

    if (sE > sO) {
        cout << 1 << "\n";
    }
    else {
        cout << 2 << "\n";
    }

    cout << abs(sE - sO);
    
    return 0;
}

Bài 2: Chọn quà (7 điểm)

Cho dãy số nguyên dương

$A_1,A_2,A_3,\dots ,A_n$

$(n\le {10}^6)$.
Đếm số cách chọn cặp

$A_i,A_j$

$(i<j)$ sao cho tổng các số còn lại là chẵn.

Brute - force:

Tính trước tổng của dãy số và lưu vào biến

$sum$.

Duyệt tuần tự để cố định

$A_i$, tương ứng với mỗi giá trị lại duyệt tuần tự một lần nữa để tìm

$A_j$. Kiểm tra nhanh cặp số hiện tại có thỏa mãn hay không bằng cách kiểm tra

$sum-(A_i+A_j)$ có chẵn hay không.

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

$O(b-a+1)$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += A[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if ( (sum - (A[i] + A[j]) ) % 2 == 0) {
                res++;
            }
        }
    }

    cout << res;
    
    return 0;
}

AC:

Nhận thấy tính chẵn lẻ của

$sum-(A_i+A_j)$ phụ thuộc vào tính chẵn lẻ của

$(A_i+A_j)$ do

$sum$ đã cố định, ta có thể chia ra các trường hợp như sau:

Trường hợp 1:

$sum$ chẵn

$\to$

$(A_i+A_j)$ phải chẵn.

Bài toán quy về "Đếm số cặp số có tổng chẵn", chỉ có hai trường hợp như sau:

• Chẵn - Chẵn.
• Lẻ - Lẻ.

Trường hợp 2:

$sum$ lẻ

$\to$

$(A_i+A_j)$ phải lẻ.

Bài toán quy về "Đếm số cặp số có tổng lẻ", chỉ có duy nhất trường hợp sau:

• Chẵn - Lẻ.

---

Như vậy để xử lý bài toán chỉ cần đếm số lượng số chẵn và số lẻ trong dãy.

Khi đó, đặt:

• $cn{t}_0$: số lượng số chẵn.
• $cn{t}_1$: số lượng số lẻ.

Ta có các công thức tính như sau:

• Số cặp chẵn - chẵn:
  $\frac{cn{t}_0\cdot (cn{t}_0-1)}{2}$.
• Số cặp lẻ - lẻ:
  $\frac{cn{t}_1\cdot (cn{t}_1-1)}{2}$
• Số cặp chẵn - lẻ:
  $cn{t}_0\cdot cn{t}_1$

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

$O\left(n\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    long long res = 0, sum = 0, cnt[2] = {0, 0};

    cin >> n;
    for (int i = 0; i < n; i++) {
        int x; 
        cin >> x;
        
        sum += x;
        cnt[x % 2]++;
    }

    if (sum % 2 == 0) {
        cout << cnt[0] * (cnt[0] - 1) / 2 + cnt[1] * (cnt[1] - 1) / 2;
    }
    else {
        cout << cnt[0] * cnt[1];
    }
    
    return 0;
}

Bài 3: Đổ nước vào chai (6 điểm)

Cho dãy số nguyên dương

$A_1,A_2,A_3,...,A_n$

$(n\le {10}^5)$. Chọn một số phần tử sao cho không có hai phần tử nào liền kề nhau trong dãy, sao cho tổng các phần tử được chọn là lớn nhất.

Brute - force:

Quay lui thử tất cả các cách chọn.

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

$O\left(2^n\right)$.

AC:

Quy hoạch động cơ bản.

Định nghĩa

$d{p}_i$ là tổng lớn nhất có thể đạt nếu xét lấy trong

$i$ phần tử đầu tiên (có thể lấy hoặc không lấy).

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

• $d{p}_1$ =
  $A_1$: Trường hợp cơ sở.
• $d{p}_i=max(d{p}_{i-1},d{p}_{i-2}+A_i)$
  $(i\ge 2)$:
  • $d{p}_i=d{p}_{i-1}$: Không lấy
    $A_i$ vào tổng tối ưu.
  • $d{p}_i=d{p}_{i-2}+A_i$: Lấy
    $A_i$ vào tổng tối ưu.

Kết quả:

$d{p}_n$.

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

$O\left(n\right)$.

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, A[N+1];
long long dp[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
    }

	dp[1] = A[1];
	for (int i = 2; i <= n; i++)  {
		dp[i] = max(dp[i-1], dp[i-2] + A[i]);
    }

	cout << dp[n];

	return 0;
}