AcWing 90场杯赛

Q1

4806. 首字母大写 - AcWing题库

给你一个字符串，如果首字符是小写，就把它改为大写。最后返回

思路

额😅😅

代码

def solve(): 
    s = input()
    if ord(s[0]) >= 97:
        s = chr(ord(s[0])-97+65)+s[1:]
    print(s)

复杂度分析

时间复杂度：O(1)
空间复杂度：O(1)

Q2

4807. 找数字 - AcWing题库

给定一个正整数 m 和一个非负整数 s。

请你找到长度为 m 且各位数字之和为 s 的最小和最大非负整数。

要求所求非负整数不得包含前导零。

思路

因为位数是固定的，所以直接从高位到低位贪心。

最小数：从高位到低位遍历，每次从最小值选择（最高位最小值为1，因为不能有前导0）。判断剩余的的数字能不能被剩余的位数填满，就是后面全填9看总和有没有大于m；如果小于，说明后面无论怎么填都不行。
最大数：从高位到低位遍历，每次都填9，如果剩余数字不满9，就填剩余的数字。

然后开头加两个特判：总和为0，位数只能小于等于1；如果所有位都填9还小于m，说明不可能实现。

代码

def solve(): 
    n, m = list(map(int, input().split()))
    if m == 0:
        if n <= 1: print(0, 0)
        else: print(-1, -1)
        return
    if n*9 < m:
        print(-1, -1)
        return
    a, b = [0]*n, [0]*n
    ca, cb = 0, 0
    for i in range(n):
        bound = 0 if i != 0 else 1
        for k in range(bound, 10):
            if ca+k+9*(n-i-1) >= m:
                a[i] = k
                ca += k
                break
    for i in range(n):
        if m-cb >= 9:
            b[i] = 9
            cb += 9
        else:
            b[i] = m-cb
            break
    for i in a: print(i, end='')
    print(' ', end='')
    for i in b: print(i, end='')

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

Q3

4808. 构造字符串 - AcWing题库

给定一个长度为 n 的由小写字母构成的字符串 t 以及一个整数 k。

请你构造一个字符串 s，要求：

字符串 s 恰好有 k 个子串等于字符串 t。

字符串 s 的长度尽可能短。

思路

简单来说，就是s后面再加上(k-1)个s。为了总长最小，所以每次添加的字符要最少。

即求出最长的，s的前缀和后缀相等的长度。

例如，s = “abab” 最长的是”ab”，2个字符长。三个就不行了，因为”aba” != “bab”。

对于这题数据量 n <= 50,直接暴力遍历公共前后缀长度。

代码

def solve(): 
    n, m = list(map(int, input().split()))
    s = input()
    match = 0
    for i in range(n-1, 0, -1):
        if s[:i] == s[n-i:]:
            match = i
            break
    ans = s
    for j in range(m-1):
        ans += s[match:]
    print(ans)

复杂度分析

时间复杂度：O(n²)
空间复杂度：O(n)

Tips

当数据量大的时候，建议使用KMP，匹配公共前后缀。复杂度 O(n)

def solve(): 
    n, m = list(map(int, input().split()))
    s = " "+input()
    i, j = 2, 0
    ne = [0]*(n+1)
    while i <= n:
        while j and s[i] != s[j + 1]: j = ne[j]
        if s[i] == s[j + 1]: j += 1
        ne[i] = j;
        i += 1
    ans = s[1:]
    for j in range(m-1):
        ans += s[ne[n]+1:]
    print(ans)