比赛的时候还特别撒比地写了二分的那个写法，然后wa了一发，因为这个集合的翻译成自然数集。还是转换了一下，还是去写了一个二分。 后面就是出现几种就是多长。。。
比赛的真的非常非常挫的code….
#include<iostream> #include<cstdio> #include<map> #include<set> #include<string> #include<queue> #include<math.h> #include<string.h> #include<algorithm> using namespace std; #define eps 1e-8 typedef __int64 LL; const int N=1e5+10; int d[N]; int a[N]; char s[N]; int vis[1000]; int n; int kill(int len,int x) { int b=1,e=len; while(b<=e) { int mid=(b+e)/2; if(x>d[mid]) b=mid+1; else e=mid-1; } return b; } void Init() { memset(vis,0,sizeof(vis)); int cnt=1; for(int i=1;i<=n;i++) { int x=s[i]; if(!vis[x]) vis[x]=cnt++; } } int main() { int t; int cas=1; scanf("%d",&t); while(t--) { scanf("%s",s+1); n=strlen(s+1); Init(); for(int i=1;i<=n;i++) { int x=s[i]; a[i]=vis[x]; } d[1]=a[1]; int len=1; int j; for(int i=2;i<=n;i++) { if(d[1]>=a[i]) //如果比最小的还小 j=1; else if(a[i]>d[len]) //如果比最大的还大 { j=++len; } else { j=kill(len,a[i]); } d[j]=a[i]; } printf("Case #%d: %d\n",cas++,len); } return 0; }