http://47.96.116.66/problem.php?cid=1177&pid=3
http://47.96.116.66/problem.php?cid=1180&pid=3
题解：我有一个想法的
如下：
不是AC的题解
理由是我记得这么一个性质 A^B^B=A;
/*
*@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=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
ll ans,cnt,flag,temp,sum;
ll a[N];
ll c[N][N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
while(~scanf("%d",&n)){
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
ans=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
//cout<<(temp^=a[i])<<endl;
}
c[1][1]=a[1];
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
c[i][j]=c[i-1][j]^a[i];
}
c[i][i]=a[i];
sort(c[i]+1,c[i]+i+1);
//for(int j=1;j<=i;j++){
//printf("%-6lld%c",c[i][j]," \n"[i==j]);
//}
}
for(int i=1;i<=n;i++){
ll now=c[i][1];
cnt=1;
for(int j=i+1;j<=n;j++){
for(int k=1;k<=j;k++){
if(c[j][k]>now){
now=c[j][k];
cnt++;
break;
}
}
}
ans=max(ans,cnt);
}
cout<<ans<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
想法二
/*
*@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=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
ll ans,cnt,flag,temp,sum;
ll a[N];
ll c[N][N];
ll dp[N][N];
ll DP[N];
void dfs(int i,ll now){
cout<<i<<" "<<now<<endl;
if(i>=n){
return;
}
dfs(i+1,a[i+1]);
dfs(i+1,now^a[i+1]);
}
int main()
{
#ifdef DEBUG
//freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&n);
//while(~scanf("%d",&n)){
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
ans=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
//cout<<(temp^=a[i])<<endl;
}
// sort(a+1,a+n+1);
// DP[1]=1;
// for(int i=2;i<=n;i++){
// DP[i]=1;
// for(int j=1;j<i;j++){
// if(a[i]>a[j]&&DP[j]+1>DP[i]){
// DP[i]=DP[j]+1;
// }
// }
// ans=max(ans,DP[i]);
// }
c[1][1]=a[1];
// for(int i=2;i<=n;i++){
// for(int j=1;j<i;j++){
// c[i][j]=c[i-1][j]^a[i];
// //cout<<(c[i][j]^a[i])<<" "<<c[i-1][j]<<endl;
// }
// c[i][i]=a[i];
// sort(c[i]+1,c[i]+i+1);
// //for(int j=1;j<=i;j++){
// //printf("%-6lld%c",c[i][j]," \n"[i==j]);
// //}
// }
//dfs(1,a[1]);
//cout<<ans<<endl;
dp[1][1]=1;
for(RI i=2;i<=n;i++){
for(int j=1;j<i;j++){
c[i][j]=c[i-1][j]^a[i];
//cout<<(c[i][j]^a[i])<<" "<<c[i-1][j]<<endl;
}
c[i][i]=a[i];
sort(c[i]+1,c[i]+i+1);
for(int j=1;j<=i;j++){
printf("%-6lld%c",c[i][j]," \n"[i==j]);
}
for(RI j=1;j<=i;j++){
dp[i][j]=1;
for(RI k=1;k<i;k++){
for(RI l=1;l<=k;l++){
if(c[i][j]>c[k][l]){
if(dp[i][j]<dp[k][l]+1)
dp[i][j]=dp[k][l]+1;
}else{
break;
}
}
}
ans=max(ans,dp[i][j]);
}
//for(int j=1;j<=i;j++){
//printf("%-6lld%c",dp[i][j]," \n"[i==j]);
//}
}
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
我从广东工业大学康师傅博客搬来的线性基DP题解：
https://blog.csdn.net/kzn2683331518/article/details/88768657
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 5010;
const int O = 1020;
int n,k;
ll b[110][70]; //b[i][j]位置i，第j位的基
ll lis[110][110]; //lis[i][j]位置i，lis为j的最小后缀
ll a[110];
void inser(int i, ll x){
for(ll j = 62;j>=0 && x;j--){
if((x>>j)&1){
if(b[i][j] == 0){
b[i][j] = x; return;
}
else x ^= b[i][j];
}
}
}
ll getmin(int i, ll x){
for(ll j = 62;j>=0 && x;j--)
x = min(x, x^b[i][j]);
return x;
}
ll greatthan(int i, ll g){
ll x = a[i];
for(ll j = 62;j>=0;j--)
x = max(x, x^b[i][j]);
if(x > g){
for(ll j = 62;j>=0;j--)
if(b[i][j]){
ll tmp = x^b[i][j];
if(tmp > x)continue;
if(tmp > g){
x = min(tmp, x);
continue;
}
else{
for(ll k = j-1;k>=0;k--)
tmp = max(tmp, tmp ^ b[i][k]);
if(tmp > g)
x = tmp;
}
}
assert(x > g);
return x;
}else return INF;
}
int main() {
while(~scanf("%d\n",&n)){
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(lis, INF, sizeof lis);
for(int i = 1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i = 1;i <= n;i++){
memcpy(b[i],b[i-1],sizeof(b[i]));
inser(i, a[i-1]);
}
lis[1][1] = getmin(1, a[1]);
for(int i = 2;i<=n;i++){
lis[i][1] = min(lis[i-1][1], getmin(i,a[i]));
for(int j = 2;j<=i;j++){
if(lis[i-1][j-1] == INF)break;
lis[i][j] = min(lis[i-1][j], greatthan(i, lis[i-1][j-1]));
}
}
int ans = n;
for(int i = n;i>=1;i--){
if(lis[n][i] != INF){
ans = i;
break;
}
}
assert(ans >= 1);
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号