天梯赛练习L1-050 倒数第N个字符串

题目

1
2
3
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB

题目描述

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为{ aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz }。这个序列的倒数第27个字符串就是zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

输入

输入在一行中给出两个正整数 $L(2 ≤ L ≤ 6)$和$N (N≤10^5)$。

输出

在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

输入样例

1
3 7417

输出样例

1
pat

解析

Ｌ个字符就是Ｌ位的26进制数，告诉我们n是倒数的位置，那么我们求一下正着数的位置，然后将求得的10进制数字转化为26进制（每位26进制用小写的26个字符表示），这样求得的字符串就是外面需要的字符串。

如何求正数呢？

用总数减去倒数的就是正数了，因a到z有26步，所以Ｌ位共有$26^L$个

参考：

[https://www.cnblogs.com/yinbiao/p/8685712.html(https://www.cnblogs.com/yinbiao/p/8685712.html)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
提交时间	2019/2/16 00:55:43	
耗时		　4 ms
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    int num = pow(26, n) - m;
    string s = "";
    while(num)
    {
        s += num%26+'a';
        num /= 26;
    }
    while(s.size() < n) ////位数不够时，补充到L位为止
        s += 'a';
    for(int i = s.size() - 1; i >= 0; i--)
        cout << s[i];
    return 0;

“a”+N

题目

1
2
时间限制: 2 Sec  
内存限制: 128 MB

题目描述

在C语言中，“a”加上一个数的结果是一个整数。
例如：“a”+6=97+6=103
但是老陈觉得这样很无聊，所以他改变了这个加的定义：加N的结果是当前字符串按字典序的顺序之后第N个字符串。
例如：”az”+4的结果就是”az”之后第四个字符串。(“az”，”ba”，”bb”，”bc”，”bd”)，所以”az”+4=”bd”。
现在请你编写程序实现它。

输入

第一行包含一个正整数T，代表数据组数。(1≤T≤1000)
接下来T行，每行一个测试数据。每个测试数据包含一个字符串s和一个正整数X。(字符串长度不大于10^4且保证非空，1 ≤ X ≤ 10^13)

输出

对于每组测试数据，输出s+X的结果。

输入样例

1
2
3
4
3
a 10
abcd 5
zzz 3

输出样例

1
2
3
k
abci
aaac

解析

刚开始一看就知道是26进制题目,所以下意识得想先把字符串转成十进制,然后再相加,最后再转成26进制.emmm这个很明显是错误的,因为字符串长度比较长,一转十进制的话,早就爆范围了.那怎么解决呢?

能不能不转换直接相加呢,这样就可以避免了这个问题?直接相加的话我们考虑下每个字母需要变成什么,那么就需要知道每个位对应要相加的数,同时要处理下进位,所以最终我们可以像处理大数加法那样,去处理进位.

首先我们先把数加到第一位上面,然后判断有没有进位,如果有那么就加到下一位,同时第一位也要减去对应的数,如此循环直到不需要进位.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
Time:436 ms
Memory:1088 kb
2019-04-08 22:48:52 
*/
#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN = 1E4+10;
char s[MAXN];
int main()
{
    int t;
    ll n;
    scanf("%d", &t);
    while(t--)
    {
        ll arr[MAXN] = {0};
        scanf("%s %lld", s, &n);
        int len = strlen(s);
        for(int i = 0; i < len; i++) //将字母变成数字存储,同时翻转容易存储
            arr[i] = s[len-1-i] - 'a';
        ll next = 0; //进位
        arr[0] += n;
        for(int i = 0; i < len; i++)
        {
            next = arr[i] / 26; //需要进的位
            arr[i] %= 26; //减去已经进位的
            if(next)
            {
                if(i == len-1) //处理完成但是还有进位,就加在首部
                {
                    arr[i+1] = next-1;
                    len++;
                }
                else
                    arr[i+1] += next; //后一位加上进位
            }
        }
        for(int i = len-1; i >= 0; i--)
            printf("%c", 'a' + arr[i]);
        printf("\n");
    }
    return 0;
}