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

• • 一、本周周赛总结
  • 二、4719. 商品种类
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、4720. 字符串
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、4721. 排队
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、参考链接

一、本周周赛总结

• 这周蛮简单的。
• 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 + 7def 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, 前后的回车空格无所谓，会前后striptest_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()

三、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和outputtest_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()

四、4721. 排队

链接: 4721. 排队

1. 题目描述

2. 思路分析

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

• 然后发现离线+堆就可以搞定。
• 把询问排序后，从小到大访问身高，并把访问的下标放到大顶堆中。
• 显然对于当前访问的身高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] * nfor 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-1t.append(idx)print(' '.join(map(str,ans)))def main():n, = RI()a = RILST()solve(n, a)if __name__ == '__main__':# testcase 2个字段分别是input和outputtest_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()

六、参考链接

• 无