• [acwing周赛复盘] 第 78 场周赛20221119


    一、本周周赛总结

    • 这周蛮简单的。
    • T2 栈的应用。
    • T3 离线+大顶堆。
      在这里插入图片描述
      在这里插入图片描述

    二、4719. 商品种类

    链接: 4719. 商品种类

    1. 题目描述

    在这里插入图片描述

    2. 思路分析

    就是set去重

    3. 代码实现

    import sys
    from collections import *
    from contextlib import redirect_stdout
    from itertools import *
    from math import sqrt
    from array import *
    from functools import lru_cache
    import heapq
    import bisect
    import random
    import io, os
    from bisect import *
    
    RI = lambda: map(int, sys.stdin.buffer.readline().split())
    RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
    RILST = lambda: list(RI())
    
    MOD = 10 ** 9 + 7
    
    
    def main():
        n, = RI()
        s = set()
        for _ in range(n):
            p = tuple((RS()))
            s.add(p)
    
        print(len(s))
    
    
    if __name__ == '__main__':
        # testcase 2个字段分别是input和output, 前后的回车空格无所谓,会前后strip
        test_cases = (
            (
                """
    5
    b y
    m r
    b y
    m y
    m g
    """,
                """
    4
    """
            ),
        )
        if os.path.exists('test.test'):
            total_result = 'ok!'
            for i, (in_data, result) in enumerate(test_cases):
                result = result.strip()
                with io.StringIO(in_data.strip()) as buf_in:
                    RI = lambda: map(int, buf_in.readline().split())
                    RS = lambda: buf_in.readline().strip().split()
                    with io.StringIO() as buf_out, redirect_stdout(buf_out):
                        main()
                        output = buf_out.getvalue().strip()
                    if output == result:
                        print(f'case{i}, result={result}, output={output}, ---ok!')
                    else:
                        print(f'case{i}, result={result}, output={output}, ---WA!---WA!---WA!')
                        total_result = '---WA!---WA!---WA!'
            print('\n', total_result)
        else:
            main()
    
    
    • 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
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    三、4720. 字符串

    链接: 4720. 字符串

    1. 题目描述

    在这里插入图片描述

    2. 思路分析

    • 题目很贴心的不需要证明,那就按照一种方法直接删除就好了。
    • 很显然,题目中需要删除相邻位置;且删完了继续删合并后的相邻位置。
    • 明显是栈。

    3. 代码实现

    import sys
    from collections import *
    from contextlib import redirect_stdout
    from itertools import *
    from math import sqrt
    from array import *
    from functools import lru_cache
    import heapq
    import bisect
    import random
    import io, os
    from bisect import *
    
    RI = lambda: map(int, sys.stdin.buffer.readline().split())
    RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
    RILST = lambda: list(RI())
    DEBUG = lambda x:sys.stderr.write(x)
    MOD = 10 ** 9 + 7
    
    
    #    	 ms
    def solve(s):
        st = []
        for c in s:
            if st and st[-1] == c:
                st.pop()
            else:
                st.append(c)
    
        print(''.join(st))
    
    
    def main():
        s, = RS()
        DEBUG(s)
        solve(s)
    
    
    if __name__ == '__main__':
        # testcase 2个字段分别是input和output
        test_cases = (
            (
                """
    aabbcddddefggbbaa
    """,
                """
    cef
    """
            ),
            (
                """
    abcddcef
    """,
                """
    abef
    """
            ),
            (
                """
    abacabaabacabaa
    """,
                """
    a
    """
            ),
        )
        if os.path.exists('test.test'):
            total_result = 'ok!'
            for i, (in_data, result) in enumerate(test_cases):
                result = result.strip()
                with io.StringIO(in_data.strip()) as buf_in:
                    RI = lambda: map(int, buf_in.readline().split())
                    RS = lambda: buf_in.readline().strip().split()
                    with io.StringIO() as buf_out, redirect_stdout(buf_out):
                        main()
                        output = buf_out.getvalue().strip()
                    if output == result:
                        print(f'case{i}, result={result}, output={output}, ---ok!')
                    else:
                        print(f'case{i}, result={result}, output={output}, ---WA!---WA!---WA!')
                        total_result = '---WA!---WA!---WA!'
            print('\n', total_result)
        else:
            main()
    
    
    • 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
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    四、4721. 排队

    链接: 4721. 排队

    1. 题目描述

    在这里插入图片描述

    2. 思路分析

    • 更新,其实不用堆,由于每次都访问的是堆顶,只存个max®就行

    读了半天题,还以为要树状数组。

    • 然后发现离线+堆就可以搞定。
    • 把询问排序后,从小到大访问身高,并把访问的下标放到大顶堆中。
    • 显然对于当前访问的身高v,如果堆中存在元素,都是比它小的(这里暂时不考虑相等)。
    • 那么所有比它小的数,只要下标比它大就是一个不满意,而大顶堆保证了堆顶就是最右的下标,这个下标就是要求的下标。
    • 由于py中默认是小顶堆,这里我们取个符号。
    • 为了处理相等的情况,我多建立了一个队列,用来暂存身高,只有小于当前值了,才从队列弹出到堆。

    3. 代码实现

    import sys
    from collections import *
    from contextlib import redirect_stdout
    from itertools import *
    from math import sqrt
    from array import *
    from functools import lru_cache
    import heapq
    import bisect
    import random
    import io, os
    from bisect import *
    
    RI = lambda: map(int, sys.stdin.buffer.readline().split())
    RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
    RILST = lambda: list(RI())
    
    MOD = 10 ** 9 + 7
    
    
    #    	 ms
    def solve(n, a):
        h = []
        a = sorted(zip(a, range(n)))
        t = deque()
        ans = [-1] * n
        for v,idx in a:
            while t and a[t[0]]!= v:
                heapq.heappush(h,-t.popleft())
            if h and -h[0]>idx:
                ans[idx] = -h[0]-idx-1
            t.append(idx)
    
    
        print(' '.join(map(str,ans)))
    
    
    def main():
        n, = RI()
        a = RILST()
        solve(n, a)
    
    
    if __name__ == '__main__':
        # testcase 2个字段分别是input和output
        test_cases = (
            (
                """
    6
    10 8 5 3 50 45
    """,
                """
    2 1 0 -1 0 -1
    """
            ),
            (
                """
    7
    10 4 6 3 2 8 15
    """,
                """
    4 2 1 0 -1 -1 -1 
    """
            ),
            (
                """
    5
    10 3 1 10 11
    """,
                """
    1 0 -1 -1 -1 
    """
            ),
        )
        if os.path.exists('test.test'):
            total_result = 'ok!'
            for i, (in_data, result) in enumerate(test_cases):
                result = result.strip()
                with io.StringIO(in_data.strip()) as buf_in:
                    RI = lambda: map(int, buf_in.readline().split())
                    RS = lambda: map(bytes.decode, buf_in.readline().strip().split())
                    with io.StringIO() as buf_out, redirect_stdout(buf_out):
                        main()
                        output = buf_out.getvalue().strip()
                    if output == result:
                        print(f'case{i}, result={result}, output={output}, ---ok!')
                    else:
                        print(f'case{i}, result={result}, output={output}, ---WA!---WA!---WA!')
                        total_result = '---WA!---WA!---WA!'
            print('\n', total_result)
        else:
            main()
    
    • 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
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92

    六、参考链接

  • 相关阅读:
    知识点16:big.LITTLE 和 dynamIQ架构的cache
    5. 最长回文子串
    go语言中的锁底层分析(一)
    Dubbo中的Triple协议和应用级服务发现
    Django基础之django模型层(一)单表操作
    android系统耗时关键字
    求一个软件,能在微信小程序里面传照片的,微信小程序要使用真实的拍实物,我想要照片代替传,这个软件可以做出来吗?
    泛微项目二次开发
    Python黑科技揭秘:多窗口操作不再是难题,这些技巧让你轻松搞定
    提高Producer的发送速度
  • 原文地址:https://blog.csdn.net/liuliangcan/article/details/127940769