AcWing 91场杯赛

Q1 4861. 构造数列 [Easy] 题解

Q2 4862. 浇花 [Medium] 题解

Q3 4863. 构造新矩阵 [Hard] 题解

Q1

4861. 构造数列 - AcWing题库

输出每个数按10进制分解出的结果。如‘23007’ => 20000，3000，7

思路

暴力

代码

def solve():
    n = input()
    print(len([n[i] for i in range(len(n)) if n[i] != '0']))
    for i in range(len(n)):
        if n[i] != '0': print(int(n[i])*pow(10, len(n)-i-1), end=' ')
    print()

复杂度分析

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

Q2

4862. 浇花 - AcWing题库

给定m个修改，每次将区间[l, r]加一。问最后哪一天的值不等于1。

思路

区间修改，单点查询。

明显的差分，最后在求前缀和的时候判断即可。

代码

def solve():
    n, m = list(map(int, input().split()))
    a = [0]*(n+2)
    for i in range(m):
        l, r = list(map(int, input().split()))
        a[l] += 1
        a[r+1] -= 1
    for i in range(1, n+1):
        a[i] += a[i-1]
        if a[i] != 1:
            print(i, a[i])
            return
    print('OK')

复杂度分析

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

Q3

4863. 构造新矩阵 - AcWing题库

思路

二分和鸽巢原理.

首先如果能找到L+1符合题意，那么L也肯定符合题意，所以可以二分答案。 之后要生成一个满足题意(m-1)*m的矩阵。由鸽巢原理，必须有一行要贡献两列大于L的值。

代码

def solve():
    input()
    n, m = list(map(int, input().split()))
    g = [list(map(int, input().split())) for i in range(n)]
    l, r = 1, int(1e9)
    while l <= r:
        mid = l+r >> 1
        if ck(g, mid, n, m): l = mid+1
        else: r = mid-1
    print(r)

def ck(g, t, n, m):
    cnt = [0]*n
    for i in range(m):
        hs = set()
        for j in range(n): 
            if g[j][i] >= t:
                hs.add(j)
                cnt[j] += 1
        if len(hs) == 0: return False
    if n < m-1: return True
    for i in cnt:
        if i > 1: return True
    return False

复杂度分析

• 时间复杂度：O(nmlog (1e9))
• 空间复杂度：O(nm)

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)