Cho dãy n số nguyên không âm a1, a2, an. Người ta tiến hành chọn ra 2 chỉ số i, j sao cho i < j Và xóa khỏi dãy 2 số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn. Yêu cầu: Cho dãy số a1, a2, an. Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau. Dữ liệu nhập: gồm 2 dòng - Dòng 1: Chứa số nguyên n (2 ≤ n ≤ 106) - Dòng 2: Chứa n số nguyên không âm a1, a2, an (0 ≤ ai ≤ 109) Dữ liệu xuất: - Là một số nguyên cho biết số cách chọn 2 chỉ số i, j thỏa mãn. Thuật toán: Ta sẽ đếm số lượng các số chẵn và lẻ trong dãy, đồng thời xác định tổng các phần tử trong dãy là lẻ hay chẵn. Nếu tổng của dãy là một số lẻ, tức là ta phải xóa một số lẻ và 1 số chẵn để tổng trở về chẵn. ⇒ Với c số chẵn và l số lẻ, là có số lượng các cặp có thể xóa là c*l. Nếu tổng của dãy là một số chẵn, ta phải xóa 2 số chẵn hoặc 2 số lẻ. Tức tổng số cách xóa sẽ bằng tổng số cách chọn ra 2 phần tử chẵn hoặc 2 phần tử lẻ từ 2 tập c và l. Xét riêng từng tập c và l, ví dụ tập c có 5 phần tử, khi thêm một phần tử nữa vào tập thì ta sẽ có thêm 5 cách ghép phần tử thứ 6 đó với 5 phần tử kia. Tức tổng quát, với n phần tử, ta sẽ có 1+2+.. +n-1 cách chọn 2 phần tử bất kỳ. Code: Mã: #include <bits/stdc++.h> using namespace std; long long int a, n, anschan, ansle, chan, le, fn; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("xoso.inp", "r", stdin); //freopen("xoso.out", "w", stdout); cin >> n; for (int i = 1; i <= n; i++){ cin >> a; if (!(a%2)) chan++; else le++; fn = (fn+a)%2; } if (fn) cout << chan*le; else{ for (int i = 1; i < chan; i++) anschan += i; for (int i = 1; i < le; i++) ansle += i; cout << anschan + ansle; } //cout << " " << fn; return 0; }
