Lweb and String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 312    Accepted Submission(s): 21 Problem Description Lweb has a string S . Oneday, he decided to transform this string to a new sequence. You need help him determine this transformation to get a sequence which has the longest LIS(Strictly Increasing). You need transform every letter in this string to a new number. A is the set of letters of S , B is the set of natural numbers. Every injection f:A→B can be treat as an legal transformation. For example, a String “aabc”, A={a,b,c} , and you can transform it to “1 1 2 3”, and the LIS of the new sequence is 3. Now help Lweb, find the longest LIS which you can obtain from S . LIS: Longest Increasing Subsequence. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence) Input The first line of the input contains the only integer T,(1≤T≤20) . Then T lines follow, the i-th line contains a string S only containing the lowercase letters, the length of S will not exceed 105 . Output For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer. Sample Input 2 aabcc acdeaa Sample Output Case #1: 3 Case #2: 4 Author UESTC Source 2016中国大学生程序设计竞赛 - 网络选拔赛 题意：给你一个字符串，把字符变成数字，让你构造一下，问你使得LIS最长是多少。 题解：其实求的是字母的种数。 AC代码： #pragma comment(linker, "/STACK:102400000,102400000") //#include<bits/stdc++.h> #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<map> #include<cmath> #include<queue> #include<set> #include<stack> #include <utility> using namespace std; typedef long long ll; typedef unsigned long long ull; #define mst(a) memset(a, 0, sizeof(a)) #define M_P(x,y) make_pair(x,y) #define rep(i,j,k) for (int i = j; i <= k; i++) #define per(i,j,k) for (int i = j; i >= k; i--) #define lson x << 1, l, mid #define rson x << 1 | 1, mid + 1, r const int lowbit(int x) { return x&-x; } const double eps = 1e-8; const int INF = 1e9+7; const ll inf =(1LL<<62) ; const int MOD = 1e9 + 7; const ll mod = (1LL<<32); const int N = 100; const int M=100010; template <class T1, class T2>inline void getmax(T1 &a, T2 b) {if (b>a)a = b;} template <class T1, class T2>inline void getmin(T1 &a, T2 b) {if (b<a)a = b;} int read() { int v = 0, f = 1; char c =getchar(); while( c < 48 || 57 < c ){ if(c=='-') f = -1; c = getchar(); } while(48 <= c && c <= 57) v = v*10+c-48, c = getchar(); return v*f; } string s; int c[26]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int cas=1; int t; t=read(); while(t--){ cin>>s; int ans = 0; memset(c,0,sizeof(c)); for(int i=0;i<s.size();i++) { c[s[i]-'a']++; if(c[s[i]-'a']==1)ans++; } printf("Case #%d: %d\n",cas++,ans); } return 0; }