小a与星际探索
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 DEBUGfreopen("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);} }?
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
