6.午枫的密码本

个人感觉出简单了

思路：

不要看到 $k≤10^{100}$ 就吓*了。

想这样一个问题：当 k 大于或等于 [不同字符数] 时会发生什么。（想通了你就会做这道题了）
答案是 LIS 就等于 [不同字符数] 。为什么呢？因为对于每个重复出现的字符串可以选择任意一个字符，我们就可以

• 第一轮，选择ASCLL最小的字符；
• 第二轮，选择ASCLL第二小的字符；
  ......
• 第 [不同字符数] 轮，选择ASCLL最大的字符。

这样，k 大于或等于 [不同字符数] 时，答案是 [不同字符数] 。

那么如果k不大怎么办，直接用$O(nlogn)$的LIS方式求解！（应该都背下来了）
为什么不会超时？因为：最多不同字符只有不到 100 个，而字符串长度小于 100.

我的代码：（留了很多优化空间）

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string dif(string a){                            //算不同字符数量，用桶，注意返回值是string以便比较大小
    int tong[129];
    for(int i=0;i<129;i++)tong[i]=0;
    for(int i=0;i<a.size();i++)tong[a[i]]++;
    int ans=0;
    for(int i=0;i<129;i++)if(tong[i])ans++;
    string anss=to_string(ans);
    return anss;
}
int lis(string a){                     //正常LIS
    char t[20005];int l=0;
    for(int i=1;i<=a.size();++i){
        char*p=lower_bound(t,t+l,a[i]);
        if(p==t+l)t[l++]=a[i];
        else*p=a[i];
    }
    return l;
}
bool daxiao(string a,string b){     //比大小，但是不能直接比较因为直接比较比的是 字典序。这个害得我多错一次（bushi）
    if(a.size()!=b.size())return a.size()>b.size();
    return a>=b;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        string a,k;
        cin>>a>>k;
        string ab=' '+a;
        //处理k大的情况
        string butongzifugeshu=dif(a);
        if(daxiao(k,butongzifugeshu)){
            cout<<butongzifugeshu<<endl;
            continue;
        }
        //转成数字此时k小于100，原因见思路;
        int kt=0;
        for(int i=0;i<k.size();i++){
            kt+=int(k[i]-48);
            if(i!=k.size()-1)kt*=10;
        }
        //算S'
        for(int i=1;i<kt;i++)ab+=a;
        cout<<lis(ab)<<endl;
    }
}

---