題目 3293: 藍橋杯2024年第十五屆決賽真題-數位翻轉
時間限制: 2s 內存限制: 192MB 提交: 1046 解決: 318
題目描述
小明創造了一個函數 f(x) 用來翻轉 x 的二進制的數位（無前導 0）。比如f(11) = 13，因為 11 = (1011)2，將其左右翻轉后，變為 13 = (1101)2；再比如f(3) = 3，f(0) = 0，f(2) = f(4) = f(8) = 1 等等。

小明隨機出了一個長度為 n 的整數數組 {a1, a2, ..., an}，他想知道，在這個數組中選擇最多 m 個不相交的區間，將這些區間內的數進行二進制數位翻轉（將ai 變為 f(ai)）后，整個數組的和最大是多少？

輸入格式
輸入共 2 行。

第一行為兩個正整數 n, m。

第二行為 n 個由空格分開的整數 a1, a2, ..., an。

輸出格式
輸出共 1 行，一個整數表示答案。

樣例輸入復制
5 3
11 12 13 14 15
樣例輸出復制
67
提示
【樣例說明 1】只翻轉 a1，和為 13 + 12 + 13 + 14 + 15 = 67。

再比如：

【樣例輸入 2】6 223 8 11 19 16 35

【樣例輸出 2】134

【樣例說明 2】翻轉區間 [a3, a4] 和 [a6]，和為 23 + 8 + 13 + 25 + 16 + 49 = 134。

【評測用例規模與約定】

對于 20% 的評測用例，保證 n, m ≤ 20。

對于 100% 的評測用例，保證 n, m ≤ 1000，0 ≤ ai ≤ 109。

1.分析

? ? ? ? 偶數反轉一定變小，判斷奇數即可，先算出所有變大的差值，再找到差值最大的m個區間。

2.代碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 1e5+10;
typedef long long LL;
LL n, m;
LL a[MAX],b[MAX],sum;
LL reserse(LL x) {      //反轉函數vector<LL> v;while (x) {LL t = x & -x;v.push_back(t);x -= t;}LL t = v[v.size() - 1];LL re = 0;for (int i = 0; i < v.size(); i++) {re += t / v[i];}return re;
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {   //輸入cin >> a[i];sum += a[i];}for (int i = 0; i < n; i++) {if (a[i] % 2 != 0) {       //判斷計算差值LL t = reserse(a[i]);if (t > a[i]) {b[i] = t - a[i];}}}LL t = 0;vector<LL> v;for (int i = 0; i < n; i++) {   //計算區間if (b[i]) {t += b[i];}else if (t != 0) {v.push_back(t);t = 0;}}if (t != 0) v.push_back(t);sort(v.begin(), v.end());for (int i = v.size()-1; i >=0; i--) {       //找到前m個區間if (v.size()-1-i<m) {sum += v[i];}}cout << sum << endl;return 0;
}