算法分析
这题普遍的做法是用 map
来模拟,这里介绍一种用 popcount
的做法
注意到,奇数不能通过任何数合并而来,所以我们可以把所有数还原到奇数
假设一个奇数 $S$ 的个数为 $C$,那么 $S$ 最终能合并出 $\operatorname{popcount}(C)$ 个不同的数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
map<int, ll> mp;
rep(i, n) {
int s, c;
cin >> s >> c;
// ll x = 1;
// while (s%2 == 0) {
// s /= 2;
// x *= 2;
// }
// mp[s] += x*c;
int k = __builtin_ctz(s);
mp[s>>k] += c*1ll<<k;
}
int ans = 0;
for (auto p : mp) {
ans += __builtin_popcountll(p.second);
}
cout << ans << '\n';
return 0;
}