題目鏈接：點擊查看

題目大意：給出 n 個數組成的數組 a ，再給出 q 次詢問，每次詢問給出一個 m ，要求找到一個 k ，使得 ( k ^ a[ i ]?) 之和小于等于 m 且 k 最大，若不存在輸出 - 1

題目分析：首先我們可以按位儲存數組 a?，這個第 k 位對于異或的貢獻就是 2^k 了，接下來我們可以通過構造一個 k ，使得? ( k ^ a[ i ] ) 之和最小，這樣在每次詢問時，如果給出的 m 比最小的?( k ^ a[ i ] ) 之和還要小，那么答案顯然就是 - 1 了，否則的話按位從最高位開始貪心就好了，貪心的策略就是當前的位如果放置 1 且加上其余位置異或的貢獻依然小于等于 m ，則肯定放 1 ，否則置 0 即可，由于運算過程中可能會爆 long long ，所以可以暫時地將其轉換為 __int128 進行運算

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=60;__int128 sum[N+1],cnt[N+1][2];LL solve(__int128 m) {if(sum[N]>m)return -1;LL ans=0;for(int i=N;i>=0;i--){if((cnt[i][0]<<i)+(i?sum[i-1]:0)<=m){ans|=(1LL<<i);m-=(cnt[i][0]<<i);}elsem-=(cnt[i][1]<<i);}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){LL num;scanf("%lld",&num);for(int j=0;j<=N;j++)cnt[j][(num>>j)&1]++;}for(int i=0;i<=N;i++){sum[i]=min(cnt[i][0],cnt[i][1])<<i;if(i)sum[i]+=sum[i-1];}int w;cin>>w;while(w--){LL m;scanf("%lld",&m);printf("%lld\n",solve(m));}return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - Final Exam(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。