首页 > 代码库 > 洛谷P1061 Jam的计数法 数学

洛谷P1061 Jam的计数法 数学

洛谷P1061 Jam的计数法
数学 
已知一个字符串 其 均有 s--t构成 且字符串要求 s[ i ]<s[ j ] i < j
已知一个字符串 求按字典序排列 的后5个字符串

1、 对于一个字符串已知,我们如何求他的下一个字符串呢? 我们可以从低位枚举到高位,找到第一个
可以增长的数,然后增长
2、同时把自己后面的串改为字典序最小,即这一位为上一位 + 1 这样字典序就最小了

 

 

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream>
 9 using namespace std ;
10 
11 int s,t,w ;
12 string jam ;
13 
14 int  main() 
15 {
16     cin>>s>>t>>w>>jam ;
17     for(int i=1;i<=5;i++) 
18        for(int j=w-1;j;j--) 
19          if(jam[j]-96 < j-(w-1)+t)    //   当前这位的字母  <=  该位上最大能填的数 -1  说明还能继续扩大  那就扩大 
20          {
21              jam[j]++ ;
22              for(int k=j+1;k<w;k++) 
23                  jam[ k ] = jam[ k-1 ]+1 ;     //  扩大了之后  使合法的字典序最小 
24              cout<<jam<<\n ;
25              break ; 
26          }
27     return 0 ;
28 }

 

洛谷P1061 Jam的计数法 数学