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);
}
}