Problem Description:
给定一个完全由小写英文字母组成的字符串等差递增序列,该序列中的每个字符串的长度固定为 L,从 L 个 a 开始,以 1 为步长递增。例如当 L 为 3 时,序列为 { aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz }。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L,本题要求你给出对应序列倒数第 N 个字符串。
Input:
输入在一行中给出两个正整数 L(2 <= L <= 6)和 N(<= 105)。
Output:
在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。
Sample Input:
3 7417
Sample Output:
pat
思路:这题是有技巧的。技巧1:倒序着不好算,所以我们需要先把它换成正序的来算。技巧2:然后我们就会发现用正序的数除以26得到的余数,假设为x,则在字母表中第(x+1)个字母就是这一位的字符。例如L=3,N=7417,那么这个序列的倒数第7417个字符串就是正数第26*26*26-7417=10159个字符串,设为M=10157。因为L=3,则每个字符串都由3个字符组成,因此要除商取余3次才能得到3个字符,每次得到的余数就是这个字符在字母表中的位数。
My DaiMa:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include<stdio.h> #include<iostream> #include<string> using namespace std; int main() { long long int l,n,m=1,x,y; char a[6]; scanf("%lld%lld",&l,&n); for(int i=1;i<=l;i++) m*=26; n=m-n; y=l; while(l--) { x=n%26; a[l]='a'+x;//第一次算出来的字符是字符串中的第L个的字符,第二次算出来的字符是字符串中的第L-1个字符 n=n/26; } for(int i=0;i<y;i++) printf("%c",a[i]);//所以最后输出的时候是要倒着输出的 return 0; } |