题意：给出一个长度为n的数列 和一个c 数列的所有数都在c范围内
问： 求一个最长子串 满足下列条件：
1 所有奇数位置的数相等
2 所有偶数位置的数相等
3 偶数位置和奇数位置的数不相等
比赛的时候枚举c 然后二分查找n o( c^2 logn ) 780ms
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1e4+5; const int mod=1e9+7; vector<int>a[105]; vector<int>::iterator it; int n,m,c,x; int check(int i,int j) { if( !a[i].size()||!a[j].size() )return 0; int ans=1; int pos=a[i][0]; while(1) { it=lower_bound(a[j].begin(),a[j].end(),pos ); if(it==a[j].end())return ans; pos=*it;ans++; it=lower_bound(a[i].begin(),a[i].end(),pos ); if(it==a[i].end())return ans; pos=*it;ans++; } } int main() { while(~RII(n,c)) { rep(i,1,n) { RI(x);a[x].pb(i); } int ans=0; rep(i,1,c) rep(j,1,c) if(i!=j)ans=max(ans,check(i,j)); printf("%d ",ans); rep(i,1,100)a[i].clear(); } return 0; }
可以dp做 o(nc) 100ms
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=200; struct node{int ans,now; }dp[N][N]; int n,m,a[100005],c; int sol() { rep(i,1,c)rep(j,1,c)dp[i][j].ans=0,dp[i][j].now=i; rep(i,1,n)RI(a[i]); rep(i,1,n) { int x=a[i]; rep(j,1,c) { if(x==j)continue; if(dp[x][j].now==x){dp[x][j].ans++;dp[x][j].now=j; } if(dp[j][x].now==x){dp[j][x].ans++;dp[j][x].now=j; } } } int ans=0; rep(i,1,c) rep(j,1,c)ans=max(ans,dp[i][j].ans); return ans; } int main() { while(~RII(n,c))printf("%d ",sol()); return 0; }