题意：给出一个长度为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\n",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\n",sol());return 0; }
