TLX-TROC29D - VIIbit Explorer
哪个印度尼西亚 wmc 出的题。。。
手玩+看到这个 $k$ 的数据范围大概才得到这东西操作到特定情况后不管怎么操作，答案都不会增加。
所以不妨考虑构造一个最优秀的方案。
我们显然希望构造出形如 $2^n - 1 = (1111\dots\dots 1)_2$ 的形式，而这个权值显然是两倍两倍增加的，所以考虑配对。
也就是形如 $i \text{ xor } j = 2^n - 1$ 的 $i, j$ 应该被配对。
此时出现一个问题是，$(11100)_2$ 还有 $(1100)_2$ 这两个的最优搭档显然应该是 $(11)_2$。
- 那怎么选呢？贪心选最大的。
- 能保证最优吗？当然可以
不难注意到，如果我们从 bit 数最多的开始贪心选择，出现配对重复的两个数 $i, j$ 中，bit 小的那一方必然会在 bit 大的那一方同 bit 的某一个数配对时被配对到。
比如上面的例子：$(1100)_2$ 向上会被 $(10011)_2$ 配对到。
所以我们不需要担心会被选漏，上面没有下面一定有。
唯一要考虑的特殊情况就是形如 $j = 0$ 的 $i$，特判一下即可。
复杂度 $O(n)$，似乎可以 log。
// Enonya
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int si = 1e6 + 10;
int n, k, vis[si], mx[100], g[si];
signed main() {
int ans = 0;
cin >> n >> k;
for(int i = 0; i < 24; ++i) {
mx[i + 1] = (1ll << (i + 1)) - 1;
}
g[1] = 0;
for(int i = 2; i <= n; ++i) {
g[i] = g[i >> 1] + 1;
}
int tot = 0;
for(int i = n; i >= 1; --i) {
if(tot == k) break;
if(vis[i] != 0) continue;
int ma = mx[g[i] + 1];
if((i ^ ma) <= 0) continue;
ans += ma * 2, vis[i] = 1, vis[i ^ ma] = 1, tot++;
}
cout << ans << endl;
return 0;
}TLX-TROC21D - Piranha Plan
直接对序列做不是很好搞。
值域上做可能对头一点，但是也不是很好弄。
最麻烦的地方就是在于这个 $P + Q$ 很迷惑，先尝试写出来会比较好。
不妨钦定一个已经被我们操作完的序列
$Q$ 就应该是此时所有满足 $a_i = a_j - 1$ 的 $a_i$ 元素的数量之和。
$P$ 呢？应该是我们把所有满足 $a_i = a_j - 1$ 的 $i, j$ 调整所花费的代价。
那这俩玩意儿加起来有没有什么性质？
有的，有的。
你注意到调整显然就是调整满足 $a_i = a_j - 1$ 的这样一对关系，因为 朋友 显然会从小的开始执行操作，所以不妨把 $a_j$ 全部调整为 $a_i$。那 $P$ 就是所有这样的 $a_j$ 的数量。
$Q$ 则是 $n -$ 剩下部分即调整后的 $a_i, a_j$ 的数量。
那么其实就是，钦定一些食人鱼不被吃掉，求这些数量的最大值即可。
做一个值域上的简单 dp 即可（以不超过 $x$ 为指标）
// Enonya
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int si = 2e5 + 10;
int n, a[si], c[si], dp[si];
signed main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i], c[a[i]] += 1;
}
for(int i = 2; i <= 100002; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + c[i]);
}
cout << n - dp[100001] << endl;
return 0;
}