[acwing周赛复盘] 第 63 场周赛20220806

[acwing周赛复盘] 第 63 场周赛20220806

    • 一、本周周赛总结
    • 二、 4503. 数对数量
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、4504. 字符串消除
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、4505. 最大子集
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • T3调试用的break没删wa了一次,搞笑了。[acwing周赛复盘] 第 63 场周赛20220806_第1张图片

[acwing周赛复盘] 第 63 场周赛20220806_第2张图片

二、 4503. 数对数量

链接: 4503. 数对数量

1. 题目描述

[acwing周赛复盘] 第 63 场周赛20220806_第3张图片

2. 思路分析

签到题,枚举x,y=n-x,检查y是否在范围内即可。

3. 代码实现

import collections
import io
import os
import sys
from collections import deque

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve(a,b,n):
    ans = 0
    for x in range(0,a+1):
        y = n-x
        if 0<=y<=b:
            ans += 1


    print(ans)


if __name__ == '__main__':
    if False:
        n = int(input())
        m, n = map(int, input().split())
        s = list(map(int, input().split()))
    a = int(input())
    b = int(input())
    n = int(input())
    solve(a,b,n)

三、4504. 字符串消除

链接: 4504. 字符串消除

1. 题目描述

[acwing周赛复盘] 第 63 场周赛20220806_第4张图片

2. 思路分析

  • 没想出来什么制胜策略。
  • 因为每次都得消除1对且只能消除一对,那么直接检查能消除多少对即可。
  • 由于消除中间的,两边可能匹配上,用栈来消除。
  • 最后检查消除了多少次,奇数次则获胜。

3. 代码实现

import collections
import io
import os
import sys
from collections import deque

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve(s):
    stack = []
    cnt = 0
    for c in s:
        if stack  and stack[-1] == c:
            cnt += 1
            stack.pop()
        else:
            stack.append(c)

    if cnt & 1:
        print('Yes')
    else:
        print('No')




if __name__ == '__main__':
    if False:
        n = int(input())
        m, n = map(int, input().split())
        s = list(map(int, input().split()))
    s = input()
    solve(s)

四、4505. 最大子集

链接: 4505. 最大子集

1. 题目描述

[acwing周赛复盘] 第 63 场周赛20220806_第5张图片

2. 思路分析

忘记删除调试用的break,wa了一次,蛋疼。

  • 模拟了半天,没想出什么好办法,只能暴力。
  • 但是暴力的时候可以倍增枚举:
  • 对每个数j,检查比它大1的数是否在数组里;检查比它大2的数;比它大4的数;比它大8的数。。。
  • 这个数b如果在数组里,还得检查b是否和当前答案集里的每个数差都是2的幂。
  • 这里先得写一个judge,位运算用O(1)时间检查这个数是不是2的幂。
  • 那么对每个数,他最多有log(2e9)的数在集合里,只需要枚举这么多大概是30。
  • 检查也是log(2e9),因此总复杂度是O(n* lgT lgT)=O(n30*30)

3. 代码实现

import io
import os
import sys
from collections import deque

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.readline
MOD = 10 ** 9 + 7


def sovle(n, x):
    if n == 1:
        print(1)
        print(x[0])
        return
    x.sort()
    s = set(x)
    mx = max(x)
    mn = min(x)
    ans = list()

    def jugde(b):
        if b == 0:
            return False
        return b & (b - 1) == 0

    for i in x:
        j = i
        t = [j]
        k = 0
        while j + 2 ** k <= mx:
            b = j + 2 ** k
            if b in s and all(jugde(abs(b-a)) for a in t):
                t.append(b)
            k += 1
        if len(t) > len(ans):
            ans = t[:]

    print(len(ans))
    print(' '.join(map(str, ans)))


if __name__ == '__main__':

    if False:
        n = int(input())
        m, n = map(int, input().split())
        s = list(map(int, input().split()))

    n = int(input())
    x = list(map(int, input().split()))
    sovle(n, x)

六、参考链接

你可能感兴趣的