AcWing 1109. 等式
原题链接
简单
作者:
wzc1995
,
2019-10-23 11:24:25
,
所有人可见
,
阅读 943
算法
(贪心,位运算) $O(n \log A)$
- 对于这类问题,我们一般采用贪心的算法来解决,即从高位开始往低位贪心,如果高位能填 1,则添 1,因为低位无论多少个 1 都不能比过高位的 1。
- 因为此题要求要保证找到满足要求的
k
下尽可能大,所以我们不能随便填 1 导致低位无法满足小于等于 M
。
- 首先预处理出来每一位填 0 和 1 所带来那一位的代价是多少,记为
t0
和 t1
。
- 我们从低位到高位预处理一个数组
mint
,记录下到当前第 $i$ 位的时候,从第 0 到第 $i$ 位最小能产生的和是多少。
- 我们从高位开始枚举,如果当前位填 1,能满足之后的位至少有一个能满足的答案(用
mint
来判断),则填 1;否则填 0。
时间复杂度
- 对于每个数字,遍历他的二进制位若干次,故时间复杂度最坏为 $O(n \log A)$。
空间复杂度
- 需要 $O(\log A)$ 的数组记录每一位上的信息。
C++ 代码
#include <cstdio>
#include <cstring>
const int N = 1010;
const int S = 50;
#define LL long long
#define min(a, b) ((a) < (b) ? (a) : (b))
LL a[N];
int main() {
int T, n;
LL m;
scanf("%d", &T);
for (int kase = 1; kase <= T; kase++) {
scanf("%d%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
LL t0[S], t1[S];
LL mint[S];
for (int s = 0; s < S; s++) {
t0[s] = t1[s] = 0;
for (int i = 1; i <= n; i++) {
t0[s] += a[i] & (1ll << s);
t1[s] += (1ll << s) - (a[i] & (1ll << s));
}
}
mint[0] = min(t0[0], t1[0]);
for (int s = 1; s < S; s++)
mint[s] = mint[s - 1] + min(t0[s], t1[s]);
LL ans;
if (mint[S - 1] > m)
ans = -1;
else {
ans = 0;
LL tot = 0;
for (int s = S - 1; s >= 0; s--) {
if (s == 0) {
if (tot + t1[s] <= m) {
ans |= 1;
tot += t1[s];
} else {
tot += t0[s];
}
} else {
if (tot + t1[s] + mint[s - 1] <= m) {
ans |= 1ll << s;
tot += t1[s];
} else {
tot += t0[s];
}
}
}
}
printf("Case #%d: %lld\n", kase, ans);
}
return 0;
}
https://www.acwing.com/blog/content/33100/
大佬们,怎么理解 Y总讲的,不太会呀 不知道 s[i][0] += 1ll << i; 这是什么意思??