# 代码

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

int n = 0, m = 0;
int s[1005] = {};
double total = 0;

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
total = 0;
scanf("%d%d", &n, &m);

int tmp = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
scanf("%d%d", s + i, &tmp);
if (tmp == 1) cnt++;
}

m = min(m, cnt);
sort(s, s+n);

for (int i = 1; i <= m; ++i) {
total += (double) s[n - i] / 2;
}
for (int i = 0; i < n - m; ++i) {
total += s[i];
}

printf("%.1lf\n", total);

}
return 0;
}

# 题解

• 1的个数之和为偶数
• 1的个数最多的那个数的1的个数小于其他数1的个数的和（贪心）

# 代码

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

ll n = 0, ans = 0;
ll oddCnt = 0, evenCnt = 0;
ll s[300005] = {};
bool sumEven[300005] = {};

ll bitCnt(ll ori) {
ll cnt = 0;
while (ori) {
cnt += ori & 1;
ori >>= 1;
}
return cnt;
}

int main() {
cin >> n;
for (ll i = 0; i < n; ++i) {
cin >> s[i];
s[i] = bitCnt(s[i]);
}

ll sum = 0;
oddCnt = 0, evenCnt = 1, sumEven[n] = true;
for (ll i = n - 1; i >= 0; --i) {
sum += s[i];
if (sum & 1) {
ans += oddCnt;
oddCnt++;
} else {
ans += evenCnt;
sumEven[i] = true;
evenCnt++;
}
}

for (ll i = 0; i < n; ++i) {
ll sumx = 0, maxi = 0;
for (ll j = i; j < min(n, i + 64LL); ++j) {
if (s[j] > maxi) {
sumx += maxi;
maxi = s[j];
} else {
sumx += s[j];
}
if (sumx < maxi && sumEven[i] == sumEven[j + 1]) {
ans--;
}
}
}

cout << ans;
return 0;
}

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mt[100] = {};
ll mintree(int h, int d) {
if (h <= 0) return 0;
if (mt[h] >= 0) return mt[h];
else if (h == 1) return 1;
else return mt[h] = mintree(h - 1, d) + mintree(h - 1 - d, d) + 1;
}

int main() {
memset(mt, -1, sizeof(mt));
int n = 0, d = 0;
ll ans = 0;
scanf("%d%d", &n, &d);
if (n == 0) {
ans = 0;
} else {
ans = (1LL << (n - 1)) - 1 - mintree(n - 1 - d, d);
}
printf("%lld", ans);
}