題目鏈接：https://www.luogu.org/problem/P4570

題目大意：

　　給一個(gè)序列，在這個(gè)序列中選一些數(shù)，這些數(shù)的魔法值之和要最大，要求這些數(shù)中任意幾個(gè)數(shù)的異或和不為0。

解題報(bào)告：

　　貪心法，按魔法值最大的取，如果能插入線(xiàn)性基，就選中這個(gè)數(shù)。為什么這樣選是對(duì)的呢，考慮三組數(shù)a[1]=1,v[1]=2，a[2]=2,v[2].y=3，a[3]=3,v[3]=4。其中a[ ]代表該元素的序號(hào)，v[ ]代表該元素的價(jià)值。

　　那么有a[3]^a[1]^a[2]=0，這時(shí)我們會(huì)發(fā)現(xiàn)，要是價(jià)值（即總魔法和）最大，應(yīng)當(dāng)取a[2]和a[3]兩個(gè)點(diǎn)，由此便證明了該貪心是正確的。

AC代碼：

1 #include<vector> 2 #include<cstdio> 3 #include<iostream> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #include<cmath> 8 #include<algorithm> 9 #define numm ch-48 10 #define pd putchar(' ') 11 #define pn putchar('\n') 12 #define pb push_back 13 #define fi first 14 #define se second 15 #define fre1 freopen("1.txt","r",stdin) 16 #define fre2 freopen("2.txt","w",stdout) 17 using namespace std; 18 template <typename T> 19 void read(T &res) { 20 bool flag=false;char ch; 21 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 22 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 23 flag&&(res=-res); 24 } 25 template <typename T> 26 void write(T x) { 27 if(x<0) putchar('-'),x=-x; 28 if(x>9) write(x/10); 29 putchar(x%10+'0'); 30 } 31 const int maxn=1010; 32 const int N=60; 33 const int inf=0x3f3f3f3f; 34 const int INF=0x7fffffff; 35 typedef long long ll; 36 ll d[70]; 37 struct node { 38 ll x; 39 int y; 40 bool operator<(const node &b) const{ 41 return y>b.y; 42 } 43 }a[maxn]; 44 bool add(ll x) { 45 for(int i=60;~i;i--) 46 if(x&(1LL<<i)) 47 if(d[i]) x^=d[i]; 48 else { 49 d[i]=x; 50 return true; 51 } 52 return false; 53 } 54 int main() 55 { 56 int ans=0,n; 57 read(n); 58 for(int i=1;i<=n;i++) 59 read(a[i].x),read(a[i].y); 60 sort(a+1,a+1+n); 61 for(int i=1;i<=n;i++) 62 if(add(a[i].x)) ans+=a[i].y; 63 write(ans);pn; 64 return 0; 65 } 代碼在這里！

?

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

總結(jié)

以上是生活随笔為你收集整理的P4570 [BJWC2011]元素（线性基+贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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