题解 | #牛客周赛 Round 37#

雾之湖的冰精

https://ac.nowcoder.com/acm/contest/77231/A

A

标准签到

from sys import stdin
a, b = map(int, stdin.readline().split())
if a + b > 9 or a > 9 or b > 9:
    print("No")
else:
    print("Yes")

B

要仔细看题， wa了好几次，注意是总金币而不是分别，减去小于 $x$ 最大的 $a_i$ 即可现在想想二分查找bisect也许更高效

from sys import stdin
n, x = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
a.sort()
cnt = 0
for i in range(n):
    if x >= a[i]:
        cnt += 1
    else:
        if i >= 1:
            x -= a[i-1]
        break
    if i == n-1:
        x -= a[i]
print(cnt, x)

C

很有意思的题， python大数计算真的方便。其实注意到这个数的倍数是有规律的。后三位每200一个循环，前面大概是 $0, 0, 1, 1, 2, 2, 3, 3, 4, 4 ....$ 然后枚举后三位按规律凑就行

from sys import stdin
las = [495, 990]
for i in range(2, 200):
    las.append(las[i-2]-10)
    if las[-1] < 0:
        las[-1] += 1000
n = int(stdin.readline().strip())
if n % 495 == 0:
    print(-1)
else:
    if (n * 10 + 5) % 495 == 0:
        print(5)
    else:
        t = n % 10
        tmp = n // 10
        flag = 0
        for x in las:
            add = t * 100 + x % 100
            if (tmp * 1000 + add) % 495 == 0:
                print(x%100)
                flag = 1
                break
        if not flag:
            for x in las:
                if (n * 1000 + x) % 495 == 0:
                    print(x)
                    break

D

思维题，仔细想，最后肯定只会留下 $1$ 个，因为如果有更大的字母，小紫会拿走，有更小的小红会取走，然后分析一下最后只可能剩下首尾的一个，判断一下即可

from sys import stdin
n = int(stdin.readline().strip())
s = stdin.readline().strip()
if ord(s[-1]) > ord(s[0]):
    print(s[-1])
else:
    print(s[0])

E

BFS，没啥特别的，除了要加上一个维度判断方向，我们这里采用 $las$ ，可以观察 $dx$ $dy$ 数组发现前两个和后两个互为反向，用 $las i 1$ 特判即可。注意踩到 . 时要沿着 $las$ 走而不是直接给 $ny$ 加一

from sys import stdin
t = int(stdin.readline().strip())
def bfs(stx, sty, edx, edy):
    global ls, n, m
    # print(edx, edy)
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    vis = [[[0] * (m + 1) for _ in range(n)] for _ in range(5)]
    q = [(stx, sty, 0, 0)]
    flg = 1
    while q:
        nx, ny, st, las = q[0]
        # print(q[0])
        q.pop(0)
        if nx == edx and ny == edy and ls[nx][ny] == 'T':
            flg = 0
            print(st)
            break
        if ls[nx][ny] == 'S':
            for i in range(4):
                tx = nx + dx[i]
                ty = ny + dy[i]
                if tx < 0 or ty < 0 or tx >= n or ty >= m or vis[i+1][tx][ty] or ls[tx][ty] == '#':
                    continue
                vis[i+1][tx][ty] = 1
                q.append((tx, ty, st+1, i+1))
        elif ls[nx][ny] == '*':
            for i in range(4):
                tx = nx + dx[i]
                ty = ny + dy[i]
                if tx < 0 or ty < 0 or tx >= n or ty >= m or vis[i+1][tx][ty] or ls[tx][ty] == '#':
                    continue
                if las + i + 1 == 7 or las + i + 1 == 3:
                    continue
                vis[i+1][tx][ty] = 1
                q.append((tx, ty, st+1, i+1))
                # print("add", q[-1])
        elif ls[nx][ny] == '.':
            tx = nx + dx[las-1]
            ty = ny + dy[las-1]
            if tx < 0 or ty < 0 or tx >= n or ty >= m or vis[las][tx][ty] or ls[tx][ty] == '#':
                continue
            vis[las][tx][ty] = 1
            q.append((tx, ty, st+1, las))
    if flg:
        print(-1)
while t:
    t -= 1
    n, m = map(int, stdin.readline().split())
    ls = [list(stdin.readline().strip()) for _ in range(n)]
    # print(ls)
    stx, sty, edx, edy = 0, 0, 0, 0
    for i in range(n):
        for j in range(m):
            if ls[i][j] == 'S':
                stx = i
                sty = j
            if ls[i][j] == 'T':
                edx = i
                edy = j
    bfs(stx, sty, edx, edy)

F

很有意思的一道题。首先重复的数字肯定是可以丢掉的。接着分析数据范围得出 $a_i$ 不会超过 $8$ 个 bit，所以最后的剩下的灵魂肯定不超过8。（极端情况每个灵魂只有1位是0） 8... 这么小的数，当然逃不出对位进行搜索判断了。坑点在于回溯的时候并不是每一个是 0 的位都要改成 1，而是这一轮修改过的 0 位修改回去

from sys import stdin
an = float("inf")
def dfs(stx, cnt):
    global a, an, ls, n
    if cnt > 8:
        return
    if stx == n:
        if max(ls) == 0:
            an = min(an, cnt)
        return
    if max(ls) == 0:
        an = min(an, cnt)
        return
    for i in range(stx, n):
        tmp = a[i]
        p = 0
        cn1 = 0
        pos = []
        while p < 8:
            if tmp & 1 == 0 and ls[p]:
                pos.append(p)
                cn1 += 1
                ls[p] = 0
            tmp >>= 1
            p += 1
        if cn1 == 0:
            continue
        dfs(i + 1, cnt + 1)
        for p in pos:
            ls[p] = 1
    
t = int(stdin.readline().strip())
while t:
    t -= 1
    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().split()))
    a = list(set(a))
    ans = 0
    ans += n - len(a)
    n = len(a)
    an = float("inf")
    for i in range(n):
        ls = [0] * 8
        tmp = a[i]
        p = 0
        while p < 8:
            if tmp & 1 == 1:
                ls[p] = 1
            tmp >>= 1
            p += 1
        dfs(i+1, 1)
    if an != float("inf"):
        ans += n - an
        print(ans)
    else:
        print(-1)