小a与星际探索_c++星际探险家在其最新的宇宙探险中遭遇了一系列新的挑战。此次探险中,探险家的飞

https://ac.nowcoder.com/acm/contest/317/C

C++版本一

题解：DP简单题

hacked

只能过95%左右

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,q;
ll ans,cnt,flag,temp;
ll a[N];
ll dp[N];
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //scanf("%d",&n);
    //scanf("%d",&t);
    //while(t--){}
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    dp[1]=a[1];
    flag=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]<a[j]&&dp[j])
                dp[i]=max(dp[i],dp[j]^a[i]);
        }
    }
    if(dp[n]!=0){
        cout << dp[n] << endl;
    }else{
        cout << -1 << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：线性基

#include <bits/stdc++.h>
#define lld I64d
using namespace std ;
inline long long Readin() {
	long long K = 0 , F = 1 ; char C = ' ' ;
	while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
	while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
	return F * K ;
}
const int Bit = 12 ;
int N , A[3005] , Base[Bit+5] ;
inline void Insert( int Num ) {
	for(register 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(register int i = Bit ; --i >= 0 ; )
		Num = max( Num , Num ^ Base[i] ) ;
	return Num ;
}
int main() {
	N = Readin() ;
	for(register int i = 0 ; ++i <= N ; A[i] = Readin() ) ;
	if( A[1] <= A[N] ) return not printf( "-1\n" ) ;
	for(register int i = 1 ; ++i < N ; )
		if( A[1] > A[i] and A[i] > A[N] )
			Insert( A[i] ) ;
	return not printf( "%d\n" , Query( A[1] ^ A[N] ) ) ;
}

C++版本三

std

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 10003, INF = 1e9 + 10;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void chmax(int &a, int b) {a = (a > b ? a : b);}
int sqr(int x) {return x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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 N, mx;
bool f[MAXN][MAXN];
struct Node {
    int id, val;
    bool operator < (const Node &rhs) const {
        return val > rhs.val;
    }
}a[MAXN];
signed main() {
    //freopen("a2.in", "r", stdin);
    //cout << (457 ^ 23);
    N = read();
    for(int i = 1; i <= N; i++) a[i].id = i, a[i].val = read(); mx = 6001;
    sort(a + 1, a + N + 1);
    for(int i = 1, flag = 1; i <= N; i++) {
        if(a[i].id == 1) {flag = 0, f[i][a[i].val] = 1; continue;}
        if(flag) continue;
        if(a[i].id == N) {
        	int k = i - 1;
        	while(k && a[i].val == a[k].val) k--;
        	if(!k) break;
            for(int j = mx; j >= 0; j--) {
                f[i][j] |= f[k][j ^ a[i].val];
                if(f[i][j]) {printf("%d", j); return 0;}
            } 
            break;
        }
    	else if(a[i].val == a[i - 1].val) {
            memcpy(f[i], f[i - 1], sizeof(f[i]));
        }
        else {
        	for(int j = 0; j <= mx; j++) 
                f[i][j] |= (f[i - 1][j ^ a[i].val] | f[i - 1][j]); 	
        }
    }
    puts("-1");
    return 0;
}

C++版本四

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<queue>
#define ll long long
#define pb push_back
#define test printf("here!!!")
using namespace std;
const int mx=5000+10;
const ll mod=1e9+7;
int dp[mx];
struct Node
{
    int p;
    int id;
    friend bool operator <(Node a,Node b)
    {
        return a.p>b.p;
    }
}a[mx];
int maxn=-1;
int n,t;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].p);
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    int cp,np;
    for (int i=1;i<=n;++i)
    {
        if (a[i].id==1)
        {
            cp=i;
        }
        if (a[i].id==n)
        {
            np=i;
        }
    }
    if (cp>np) printf("-1\n");
    else
    {
        dp[a[cp].p]=1;
        for (int i=cp+1;i<=np;++i)
        {
            for (int j=0;j<=mx;++j)
            {
               if (dp[j]) dp[j^a[i].p]=a[i].id;
            }
        }
        int res=-1;
        for (int j=mx;j>=0;--j)
        {
            if (dp[j]==n)
            {
                res=j;
                break;
            }
        }
        if (res==0) printf("-1\n");
        else printf("%d\n",res);
    }
}