题目描述

按规律输出。在一格内叠词

样例

3
15012233444 3-4-4
15012233444 3-3-5
12223 2-3
Case #1:  one five zero one double two three three triple four
Case #2:  one five zero one double two double three triple four
Case #3:  one two double two three

算法1

(暴力枚举) $O(n^2)$

很像lc的罗马数字那个

时间复杂度

参考文献

C++ 代码

#include <iostream> //从io标准输入输出里读
#include <cstring>
#include <sstream> //从字符串读
#include <vector>
using namespace std;
// getline() strstr 分隔符，- 读到它时终止。
string nums[] = {
    "zero", "one", "two", "three", "four",
    "five", "six", "seven", "eight", "nine",
};
string cnts[] = { //缩写的表示
    "", "", "double", "triple", "quadruple",
    "quintuple", "sextuple", "septuple", "octuple",
    "nonuple", "decuple",
};
//有点像PAT. 思路简单，但代码实现复杂，细节多，特判，输入输出不一样。
void print(string s)
{
    for (int i = 0; i < s.size(); i ++ ) 
    {   //遍历s 每一段。
        int j = i + 1; //当前相同的数字是哪一段, 区间:【i, j】
        while (j < s.size() && s[j] == s[i]) j++; //区间【i,j】相同
        int len = j - i; // 这一段的长度
        if (len >= 2 && len <= 10) cout << cnts[len] << ' ' << nums[s[i] - '0'] << ' ';
        //缩写 + num[s[i]]
        else if (len > 10)
        {
            for (int k = 0; k < len; k++) //大于10个，分别输出len个数字
                cout << nums[s[i] - '0'] << ' ';
            //注意 s[i]是个字符，所以减去偏移量'0'
        }
        else cout << nums[s[i] - '0'] << ' ';//一个字符
        i = j - 1;
    }
}

int main()
{
    int n;
    cin >> n;
    for (int C = 1; C <= n; C++)
    {
        string s, seq; //电话号码，分隔
        cin >> s >> seq;

        vector<int> len; //读到长度(Defn)数组里
        string str;
        stringstream ssin(seq); //初始化到sstream
        while (getline(ssin, str, '-')) len.push_back(stoi(str)); //压入vector(len)中，并且stoi string to integer 字符串转化为数字
        //读到~~num~~ str里，用 ‘-’终止

        printf("Case #%d:  ", C);

        int start = 0; //每一段的开始。第一段从0开始
        for (int l : len) //每次找到当前段的长度
        {
            print(s.substr(start, l)); //s当中的某一段，从start开始，到l。
            start += l; //输出完事后 start偏移l
        }
        puts("");
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

Python 代码

缩写 = ['', '', 'double', 'triple', 'quadruple', 'quintuple', 
    'sextuple', 'septuple', 'octuple',
    'nonuple', 'decuple']
数字 = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven',
        'eight', 'nine']
def read(l, r):
    while l < r:
        k = l + 1
        while k < r and a[k] == a[l]:
            k += 1
        #这样区间[l, k]就是数字相同的一段
        长度 = k - l
        if 2 <= 长度 <= 10:
            res.extend([缩写[长度], 数字[a[l]]])
        elif 长度 > 10:
            res.extend([数字[a[l]]] * 长度) #每个字分别输出出来
        else:
            res.append(数字[a[l]]) #省一个就输出出来
        l = k
# def joinres(res):
#    return ' '.join(res)

if __name__ == "__main__":
    T = int(input())
    t = 0
    while t < T:
        t += 1
        a, b = input().split()
        a = list(map(int, a))
        b = list(map(int, b.split('-'))) #用-来分隔
        l, res = 0, []
        for x in b:
            read(l, l + x)
            l += x #起始端加上偏移量
        print('Case #%d:  %s' % (t, ' '.join(res)))
        # ans = joinres(res)
        # print(f'Case #{t}:  {ans}')

作者：查猪字幕组
链接：https://www.acwing.com/activity/content/code/content/919399/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。