題目鏈接

BZOJ4245

題解

套路①
位運(yùn)算當(dāng)然要分位討論，高位優(yōu)先
考慮在\(or\)下，如果該位為\(0\)，則每一位都為\(0\)

套路②
我們選m段異或和，轉(zhuǎn)化為\(m\)個(gè)前綴和的點(diǎn)，且其中有一個(gè)是\(n\)

容易發(fā)現(xiàn)，該位結(jié)果要為0，則選取的前綴和該位都為\(0\)
所以貪心查找所有該位為\(0\)的，首先第\(n\)個(gè)前綴和一定要為\(0\)，如果其它滿足有至少\(m - 1\)個(gè)，那么該位答案為\(0\)，剩余為\(1\)的打上標(biāo)記不能選
如果不夠，那這一位就沒(méi)辦法了，直接放棄

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,0,sizeof(s)) #define cp pair<int,int> #define LL long long int using namespace std; const int maxn = 500005,maxm = 100005,INF = 1000000000; inline LL read(){LL out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } int n,m,tag[maxn]; LL a[maxn],ans; int main(){n = read(); m = read();REP(i,n) a[i] = read() ^ a[i - 1];for (LL i = 1ll << 61; i; i >>= 1){if (a[n] & i){ans += i;continue;}int cnt = 1;for (int j = 1; j < n; j++)if (!tag[j] && !(a[j] & i)) cnt++;if (cnt >= m){for (int j = 1; j < n; j++)if (!tag[j] && (a[j] & i))tag[j] = true;}else ans += i;}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9094057.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ4245 [ONTAK2015]OR-XOR 【贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。