题干：
小a正在玩一款星际探索游戏，小a需要驾驶着飞船从11号星球出发前往nn号星球。其中每个星球有一个能量指数pp。星球ii能到达星球jj当且仅当pi>pjpi>pj。
同时小a的飞船还有一个耐久度tt，初始时为11号点的能量指数，若小a前往星球jj，那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj，关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的pp有关，与下标无关
输入描述:
第一行一个整数nn，表示星球数
接下来一行有nn个整数，第ii个整数表示pipi 输出描述:
一个整数表示到达nn号星球时最大的耐久度
若不能到达nn号星球或到达时的最大耐久度为00则输出−1−1 示例1
输入
3
457 456 23 输出
478 说明
小a有两种方法到达33号星球
第一种：1→2→31→2→3，最终耐久度为457⊕456⊕23=22457⊕456⊕23=22
第二种：1→31→3，最终耐久度为457⊕23=478457⊕23=478 示例2
输入
4
2 4 4 2 输出
-1 示例3
输入
5
234 233 123 2333 23 输出
253 备注:
1⩽n,∀pi⩽3000
解题报告：
这题做法比较多样，比较好想的就是当成布尔背包去解，因为告诉你了最大值是3000，那就一个bool类型的dp数组判断能否得到就行了。因为异或不具有单调性（即正数异或一个正数得到的数不一定更大），，所以直接背包取max的做法显然是错误的。。还有就是这题可以直接类似spfa去求解，但是这题告诉你了顺序是从大到小走，所以可以直接排序然后直接判断就行了。具体解法就是排序然后把值位于a[1] a[n]之间的都加到b数组中，然后对b数组直接背包就行了，因为这样背包背出来的dp值如果是1，代表一定能凑出来，如果是0，代表一定凑不出来。（其实这样解的话就不需要排序了，，但是标程的解法是排序的。）
第二种方法是线性基，刚刚学会，，感觉超级好用。。代码附上、、
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其实并不是很标准，，这题貌似是数据问题刚好放过去了。、、）
#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 ;
} 总结：
其实最后求解的时候不能直接取max我感觉
京公网安备 11010502036488号