題干：

小a正在玩一款星際探索游戲，小a需要駕駛著飛船從11號星球出發(fā)前往nn號星球。其中每個星球有一個能量指數(shù)pp。星球ii能到達(dá)星球jj當(dāng)且僅當(dāng)pi>pjpi>pj。
同時小a的飛船還有一個耐久度tt，初始時為11號點(diǎn)的能量指數(shù)，若小a前往星球jj，那么飛船的耐久度會變?yōu)閠⊕pjt⊕pj(即tt異或pjpj，關(guān)于其定義請自行百度)
小a想知道到達(dá)nn號星球時耐久度最大為多少

注意：對于每個位置來說，從它出發(fā)可以到達(dá)的位置僅與兩者的pp有關(guān)，與下標(biāo)無關(guān)

輸入描述:

第一行一個整數(shù)nn，表示星球數(shù) 接下來一行有nn個整數(shù)，第ii個整數(shù)表示pipi

輸出描述:

一個整數(shù)表示到達(dá)nn號星球時最大的耐久度 若不能到達(dá)nn號星球或到達(dá)時的最大耐久度為00則輸出?1?1

示例1

輸入

復(fù)制

3 457 456 23

輸出

復(fù)制

478

說明

小a有兩種方法到達(dá)33號星球 第一種：1→2→31→2→3，最終耐久度為457⊕456⊕23=22457⊕456⊕23=22 第二種：1→31→3，最終耐久度為457⊕23=478457⊕23=478

示例2

輸入

復(fù)制

4 2 4 4 2

輸出

復(fù)制

-1

示例3

輸入

復(fù)制

5 234 233 123 2333 23

輸出

復(fù)制

253

備注:

1?n,?pi?3000

解題報告：

? ?這題做法比較多樣，比較好想的就是當(dāng)成布爾背包去解，因為告訴你了最大值是3000，那就一個bool類型的dp數(shù)組判斷能否得到就行了。因為異或不具有單調(diào)性（即正數(shù)異或一個正數(shù)得到的數(shù)不一定更大），，所以直接背包取max的做法顯然是錯誤的。。還有就是這題可以直接類似spfa去求解，但是這題告訴你了順序是從大到小走，所以可以直接排序然后直接判斷就行了。具體解法就是排序然后把值位于a[1]? a[n]之間的都加到b數(shù)組中，然后對b數(shù)組直接背包就行了，因為這樣背包背出來的dp值如果是1，代表一定能湊出來，如果是0，代表一定湊不出來。（其實這樣解的話就不需要排序了，，但是標(biāo)程的解法是排序的。）

? ?第二種方法是線性基，剛剛學(xué)會，，感覺超級好用。。代碼附上、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int N = 3000 + 5; ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f; } int a[N],f[1<<12],b[N]; int main() {int n = read();for(int i = 1;i <= n;++i) a[i] = read();int js = 0;int mx = a[1],mn = a[n];if(mx <= mn) {puts("-1");return 0;}f[mn ^ mx] = 1;f[0] = 1;for(int i = 1;i <= n;++i) {if(a[i] > mn && a[i] < mx) {b[++js] = a[i];}}int END = 1 << 12;for(int i = 1;i <= js;++i) {for(int j = END;j >= 0;--j) {f[j] = f[j ^ b[i]] | f[j];}}int ans = 0;for(int i = END;i >= 0;--i) {if(f[i] == 1) {ans = i;break;}}if(ans == 0) puts("-1");else printf("%d",ans);return 0; }

?線性基解法1：（這個query其實并不是很標(biāo)準(zhǔn)，，這題貌似是數(shù)據(jù)問題剛好放過去了。、、）

#include <bits/stdc++.h> #define lld I64d using namespace std ; const int Bit = 12 ; int N , A[3005] , Base[Bit+5] ; inline void Insert( int Num ) {for( int i = Bit ; --i >= 0 ; )if( 1 << i & Num )if( not Base[i] ) {Base[i] = Num ;break ;}else Num ^= Base[i] ; } inline int Query( int Num ) {for( int i = Bit ; --i >= 0 ; )Num = max( Num , Num ^ Base[i] ) ;return Num ; } int main() {cin>>N;for(int i = 1 ; i <= N ; i++) cin >> A[i] ;if( A[1] <= A[N] ) {printf( "-1\n" ) ;return 0;}for(int i = 2 ; ++i < N ; )if( A[1] > A[i] and A[i] > A[N] )Insert( A[i] ) ;printf( "%d\n" , Query( A[1] ^ A[N] ) ) ;return 0; }

線性基解法2：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n,a[MAX]; vector<int> vv; bool ok(int i) {if(a[i] > a[n] && a[i] < a[1]) return 1;else return 0; } int main() {cin>>n;for(int i = 1; i<=n; i++) cin>>a[i];if(a[1] <= a[n]) {puts("-1");return 0 ;}for(int i = 2; i<=n-1; i++) {if(ok(i)) vv.pb(a[i]);}int up = vv.size(),ans=0;ans = a[1]^a[n];if(up) {for(int i = 14,k=0; i>=0; i--) {for(int j = k; j<up; j++) {if((1<<i) & vv[j]) {swap(vv[j],vv[k]);break;}}if((1<<i) & vv[k]) {for(int j = k+1; j<up; j++) {if((1<<i) & vv[j]) vv[j] ^=vv[k];}k++;}}for(int i = 14,k=0; i>=0; i--) {if((1<<i) & vv[k]) ans = max(ans,ans^ vv[k]),k++;//或者 if (!(ans >> i & 1)) ans ^= vv[k];}}if(ans == 0) ans=-1;printf("%d\n",ans);return 0 ; }

總結(jié)：

? ?其實最后求解的時候不能直接取max我感覺

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 317C】小a与星际探索（背包dp 或 线性基）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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