B-MST

题意

给定一张有 $n (2\le n\le 10^5)$ 个点，$m$ 条边的图，$q (1\le m,q\le 10^5)$ 次询问 $k$ 个点的子图，求其最小生成树权值。

C-Red Walking on Grid

题意

有一个 $2\times n (1\le n\le 10^6)$ 的管道，分为白区和红区，初始选择一个红区，每个红区走过后变成白区，问最多能走几步。

思路

考虑从左往右递推，当前方格能走的最大步数为左边与上下方格步数的最大值加一。

代码

n = int(input())
a = ['W' + input(), 'W' + input()]
b = [[0] * (n + 1), [0] * (n + 1)]

ans = 0
for i in range(1, n + 1):
    if a[0][i] == 'R':
        b[0][i] = b[0][i - 1] + 1
    if a[1][i] == 'R':
        b[1][i] = b[1][i - 1] + 1
    if a[0][i] == a[1][i] == 'R':
        b[0][i], b[1][i] = max(b[0][i], b[1][i] + 1), max(b[1][i], b[0][i] + 1)
    ans = max(ans, b[0][i], b[1][i])
ans = max(0, ans - 1)
print(ans)

E-GCD VS XOR

题意

给定正整数 $x (1\le x\le 10^{18})$，求满足 $gcd(x,y)=x\oplus y$ 的小于 $x$ 的正整数 $y$。若无则打印-1。

思路

将 $x$ 转换为二进制，如 0b110100。$y$ 即为最右侧的 1 开始的二进制数，也就是 100。

代码

t = int(input())
for _ in range(t):
    x = int(input())
    a = bin(x)
    b = ''
    for i in a[::-1]:
        b = i + b
        if i == '1':
            break
    ans = int(b, 2) ^ x
    print(ans if 0 < ans < x else -1)

H-Instructions Substring

题意

给定一个长度为 $n (1\le n\le 2\times 10^5)$ 的字符串表示操作指令（WASD分别表示上左下右），和一个坐标 $(x, y) (-10^5\le x,y\le 10^5)$，起始位置是 $(0, 0)$，问有多少个连续字串操作指令，会经过 $(x, y)$。

思路

从后往前枚举左端点，用字典查找记录的右端点。x = y = 0 的情况需要特判。

时间复杂度：$O(n)$

代码

n, x, y = map(int, input().split())
a = input()
d = {(0, 0): n - 1}
xk = yk = 0
ans = 0
if x == y == 0:
    print((n + 1) * n // 2)
else:
    for i in range(n - 1, -1, -1):
        if a[i] == 'W':
            yk += 1
        elif a[i] == 'A':
            xk -= 1
        elif a[i] == 'S':
            yk -= 1
        elif a[i] == 'D':
            xk += 1
        d[(xk, yk)] = i - 1
        k = d.get((xk - x, yk - y), n)
        ans += n - k
    print(ans)