换 `__int128` 试试?
by iMya_nlgau @ 2020-08-11 17:32:24
`now * LG_1[i]` 溢出了。
by ezoixx130 @ 2020-08-11 17:32:29
溢出了QAQ
(赛时我也被溢出卡了会/kk)
by LeavingZ @ 2020-08-11 17:33:10
51 太大了
by Scintilla @ 2020-08-11 17:35:43
@[Sapphire6575737973](/user/176569)
多过了一个点而已……难道我还有其它地方写错了?
by Acfboy @ 2020-08-11 17:39:52
@[Acfboy](/user/40318) 那可能是你贪心策略错了
正解是先贪心求出一个使 $\sum a \, \text{xor} \, k$ 最小的 $k$。再从高到低看 $k$ 的每一位,如果是 $1$ 不用管,如果是 $0$,再看能不能取 $1$。
by iMya_nlgau @ 2020-08-11 17:49:26
@[Sapphire6575737973](/user/176569) 为什么我从高到低能取1就取1会不对?
by Acfboy @ 2020-08-11 17:54:08
@[Acfboy](/user/40318) 这样可能会误判为无解吧
by iMya_nlgau @ 2020-08-11 17:58:10
@[Sapphire6575737973](/user/176569) 谢谢!
by Acfboy @ 2020-08-11 18:05:05
@[Sapphire6575737973](/user/176569)
还是挂了qwq,再帮我看看吧
50pts
```cpp
#include <cstdio>
#include <iostream>
#define N 100005
using namespace std;
__int128 a[N], maxx, m, ans, n, q, LG_0[55], LG_1[55];
__int128 Doit(int d){
__int128 an = 0, ans = 0;
bool flag = 0;
for(int i = d; i >= 0; i--){
__int128 now = (__int128) 1 << i;
if(an + now * LG_0[i] <= m && an + now * LG_0[i] <= an + now * LG_1[i])
an += now * LG_0[i];
else if(an + now * LG_1[i] <= m){
an += now * LG_1[i];
ans += now;
}
else return -1;
}
for(int i = d; i >= 0; i--){
__int128 now = (__int128) 1 << i;
if((ans & now) == 0 && (an + now * LG_1[i] - LG_0[i] * now <= m)){
an += now * LG_1[i];
ans += now;
}
}
return ans;
}
int main(){
scanf("%lld", &n);
int maxx = 0;
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for(int i = 0; i <= 51; i++)
for(int j = 1; j <= n; j++){
LG_0[i] += (a[j] >> i) & 1;
LG_1[i] += 1 - ((a[j] >> i) & 1);
}
scanf("%lld", &q);
for(int i = 1; i <= q; i++){
scanf("%lld", &m);
ans = Doit(51);
printf("%lld\n", ans);
}
return 0;
}
```
by Acfboy @ 2020-08-11 20:24:23