二分$T$和$S$第一个不同的位置，即需要对于$s$，判定是否存在$T[1,s]=S[1,s]$且满足条件的$T$
（注：这里的条件不包含$T$的字典序最小）
显然$T[1,s]$已经确定，记其中第$i$种字母出现次数为$a_{i}$
而对于$T(s,n]$，只有字典序（尽量大）和字符数量的限制，因此若交换两个字符能增大字典序显然不劣，重复交换这样的字符，不难得到最终字符从前往后是不上升的
设其中第$i$种字符有$b_{i}$个，即希望依次最大化$b_{26},b_{25},...,b_{1}$，不妨依次暴力枚举（共$sigma(k)$种取值），并对后面的部分背包+bitset判定是否可行，即可得到该序列并进而比较与$S$的字典序
这一部分的复杂度为$o(alphasigma(k)frac{n}{omega}log n)$（其中$alpha=26$，$omega=64$）
进一步的，由于下一个位置一定不同，那么再之后的部分也仅有字典序（尽量小）和字符数量的限制，可以类似地求出，而下一个位置直接暴力枚举即可
这一部分的复杂度为$o(alpha^{2}sigma(k)frac{n}{omega})$
综上，（单组数据）复杂度为$o(alphasigma(k)frac{n}{omega}log n+alpha^{2}sigma(k)frac{n}{omega})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define A 26 5 vector<int>v; 6 bitset<N>bt[A+1]; 7 int t,n,m,a[A],b[A]; 8 char s[N]; 9 bool get_max(int n){ 10 memset(b,0,sizeof(b)); 11 for(int i=A-1;i>=0;i--){ 12 bt[i].reset(); 13 for(int j=0;(j<v.size())&&(a[i]<=v[j]);j++){ 14 int x=v[j]-a[i]; 15 if (x<=n)bt[i]|=(bt[i+1]<<x); 16 } 17 } 18 if (!bt[0][n])return 0; 19 for(int i=0;i<A;i++) 20 for(int j=0;(j<v.size())&&(a[i]<=v[j]);j++){ 21 b[i]=v[j]-a[i]; 22 if ((b[i]<=n)&&(bt[i+1][n-b[i]])){ 23 n-=b[i]; 24 break; 25 } 26 } 27 return 1; 28 } 29 bool check(int k){ 30 memset(a,0,sizeof(a)); 31 for(int i=1;i<=k;i++)a['z'-s[i]]++; 32 if (!get_max(n-k))return 0; 33 for(int i=0;i<A;i++) 34 for(int j=0;j<b[i];j++) 35 if (s[++k]!='z'-i)return s[k]<'z'-i; 36 return 1; 37 } 38 int main(){ 39 bt[A][0]=1; 40 scanf("%d",&t); 41 while (t--){ 42 scanf("%d%d%s",&n,&m,s+1); 43 v.clear(); 44 for(int i=m;i;i--) 45 if (m%i==0)v.push_back(i); 46 v.push_back(0); 47 memset(a,0,sizeof(a)); 48 if (!check(0)){ 49 printf("-1 "); 50 continue; 51 } 52 int l=0,r=n; 53 while (l<r){ 54 int mid=(l+r+1>>1); 55 if (check(mid))l=mid; 56 else r=mid-1; 57 } 58 if (l==n){ 59 printf("%s ",s+1); 60 continue; 61 } 62 memset(a,0,sizeof(a)); 63 for(int i=1;i<=l;i++)a[s[i]-'a']++; 64 for(int i=s[l+1]-'a'+1;i<A;i++){ 65 a[i]++; 66 if (get_max(n-l-1)){ 67 for(int j=1;j<=l;j++)printf("%c",s[j]); 68 printf("%c",i+'a'); 69 for(int j=0;j<A;j++) 70 while (b[j]--)printf("%c",j+'a'); 71 printf(" "); 72 break; 73 } 74 a[i]--; 75 } 76 } 77 return 0; 78 }