A. Kevin and Arithmetic
题意：给你\(n\)个数，你一开始有一个\(x = 0\)，每次你让\(x\)加上一个没用过的数，然后\(x\)会一直除二直到变成奇数。如果你加上一个数后能除2，分数加1，问分数最大多少。
奇数后面加奇数才能是偶数，但一开始\(x\)是零，那么需要一个偶数，否则只能浪费一个奇数。
所以如果有偶数就是奇数个数加1，否则是奇数个数减1.
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
int cnt[2]{};
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
++ cnt[a[i] & 1];
}
if (cnt[0]) {
std::cout << 1 + cnt[1] << "\n";
} else {
std::cout << std::max(0, cnt[1] - 1) << "\n";
}
}
B. Kevin and Geometry
题意：\(n\)个数，你要选四个数组成等腰梯形。
对梯形作高发现两边是两个三角形，那么(上底-下底)/2是底边长，为了让梯形的两个腰边能够上上底，这个距离一定小于腰边。所以我们找两个相同的数作为腰边，然后找差值最小的两个数当上底和下底。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
int p = -1;
for (int i = 0; i + 1 < n; ++ i) {
if (a[i] == a[i + 1]) {
p = i;
break;
}
}
if (p == -1) {
std::cout << -1 << "\n";
return;
}
for (int i = 0, j = 0; i + 1 < n; ++ i) {
while (i == p || i == p + 1) {
++ i;
}
j = std::max(j, i);
while (j == i || j == p || j == p + 1) {
++ j;
}
if (i < n && j < n && std::abs(a[i] - a[j]) < a[p] + a[p]) {
std::cout << a[j] << " " << a[i] << " " << a[p] << " " << a[p] << "\n";
return;
}
}
std::cout << -1 << "\n";
}
C. Kevin and Puzzle
题意：\(n\)个人，每个人可能是老实人也可能是说谎者，老实人一定说真话。两个说谎者不能站一起。第\(i\)个说左边有\(a_i\)个骗子。问这些人可能的组合有多少。
\(f_{i_{0/1}}\)表示第\(i\)个是老实人/说谎者。那么如果\(i\)是老实人，看前面一个人怎么转移过来。如果前面那个人也是老实人，那么\(a_i = a_{i+1}\)，因为\(i\)说真话，\(i-1\)也是老实人，那么\(i-1\)左边的老实人应该等于\(a_i\)说的，不然两个人不可能同时是老实人。如果\(i-1\)是说谎者，那么因为两个说谎者不能站一起，第\(i-2\)个人一定是老实人，因为\(i-1\)是说谎者，那么到\(i-2\)这里还有\(a_i - 1\)个说谎者，看能不能对上就行。
如果\(i\)说谎，那么\(i-1\)一定使老实人，\(f_{i_0} = f_{i-1_1}\)。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
}
if (n == 1) {
std::cout << (1 + (a[1] == 0)) << "\n";
return;
}
std::vector f(n + 1, std::array<Z, 2>{});
f[1][0] = a[1] == 0;
f[1][1] = 1;
for (int i = 2; i <= n; ++ i) {
if (a[i] == a[i - 1]) {
f[i][0] += f[i - 1][0];
}
if (i >= 2 && a[i] - 1 == a[i - 2]) {
f[i][0] += f[i - 1][1];
}
f[i][1] = f[i - 1][0];
}
std::cout << f[n][0] + f[n][1] << "\n";
}
D. Kevin and Numbers
题意：两个数字\(A\)和\(B\)，每次可以从\(A\)里选两个数，满足他们的差绝对值小于等于1，然后把这两个数删掉，然后把他们的和加入\(A\)，问\(A\)能不能变成\(B\)。
考虑反着来，从\(B\)到\(A\)，那么发现如果\(B\)的最大值大于\(A\)的最大值，那么这个最大值必须拆开，发现拆开的方式是唯一的。于是模拟就行。
注意最多操作\(n-m\)次，一直操作可能超时。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::priority_queue<int> a, b;
for (int i = 0; i < n; ++ i) {
int x;
std::cin >> x;
a.push(x);
}
for (int i = 0; i < m; ++ i) {
int x;
std::cin >> x;
b.push(x);
}
i64 sum = n - m;
while (sum >= 0 && a.size() && b.size()) {
if (a.top() == b.top()) {
a.pop();
b.pop();
} else if (sum > 0) {
int u = b.top(); b.pop();
b.push(u / 2);
b.push(u - u / 2);
-- sum;
} else {
break;
}
}
if (a.empty() && b.empty()) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
E. Kevin and And
题意：\(n\)个数，你有\(m\)个数让他们操作，每次可以选一个\(i\)和\(j\)，然后\(a_i \&= b_j\)，求最多\(k\)次操作让数组和最小。
发现\(m\)很小，枚举所有操作可以与的数。 然后计算\(f_{ij}\)表示第\(a_i\)操作\(j\)次最多减小多少，然后差分一下，记\(d_{i,j}\)为\(a_i\)操作\(j\)次比操作\(j-1\)次可以多减少的值。就可以用优先级队列记录一次操作可以减少的最大值。
点击查看代码
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<i64> b(m);
for (int i = 0; i < m; ++ i) {
std::cin >> b[i];
}
std::vector<std::vector<i64> > op(m + 1);
for (int i = 0; i < 1 << m; ++ i) {
i64 x = (1ll << 30) - 1;
int cnt = 0;
for (int j = 0; j < m; ++ j) {
if (i >> j & 1) {
x &= b[j];
++ cnt;
}
}
op[cnt].push_back(x);
}
std::vector d(n, std::vector<i64>(m + 1));
for (int i = 0; i < n; ++ i) {
for (int j = 1; j <= m; ++ j) {
for (auto & x : op[j]) {
d[i][j] = std::max(d[i][j], a[i] - (a[i] & x));
}
d[i][j] = std::max(d[i][j], d[i][j - 1]);
}
for (int j = m; j >= 1; -- j) {
d[i][j] = d[i][j] - d[i][j - 1];
}
}
std::priority_queue<std::array<i64, 3> > heap;
for (int i = 0; i < n; ++ i) {
heap.push({d[i][1], 1, i});
}
i64 ans = std::accumulate(a.begin(), a.end(), 0ll);
while (k -- ) {
auto [x, cnt, id] = heap.top(); heap.pop();
ans -= x;
if (cnt + 1 <= m) {
heap.push({d[id][cnt + 1], cnt + 1, id});
}
}
std::cout << ans << "\n";
}