未命名

交互题：猜数字

import sys
l, r, ans = 1, 7, 0
for i in range(3):
    mid = (l + r) // 2
    print(f"? {mid}")
    sys.stdout.flush()
    a = input()
    if a == '<':
        l = mid + 1
    elif a == '>':
        r = mid - 1
    else:
        ans = mid
        break
print(f"! {ans}")
sys.stdout.flush()

03_k进制转换

有 n 台破解器，字符集 S 长度为 k，密码长度为 m。总共有 k^m 个密码，按 S 定义的字典序排列。每台破解器处理连续的一段密码，要求：

• 所有密码都被处理
• 工作量均衡，最大与最小工作量差不超过 1

def idx_to_password(idx):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

n, m = map(int, input().split())
s = input().strip()

k = len(s)
total = k ** m
lenth_for_machine = total // n
remainder = total % n
a = 0
for i in range(n):
    len_i = lenth_for_machine
    if i < remainder:
        len_i += 1
    b = a + len_i
    print(idx_to_password(a), idx_to_password(b - 1))
    a = b

04_跳跃过桥

方法一：二分搜索

def first_true(lo, hi, check):
    """查找第一个满足 check(x) 为 True 的 x"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_reach(target):
    """检查是否能通过跳跃长度 k 到达终点"""
    farthest = k
    for i in range(1, n + 1):
        if a[i] <= target and i <= farthest:
            farthest = max(farthest, i + k)
    return farthest >= n + 1

for _ in range(t):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split())) + [0]  # 添加起点和终点
    result = first_true(min(a), max(a), can_reach)
    print(result)

方法二：单调队列

from collections import deque

t = int(input())

def solve_one(n, k, a):
    q = deque()
    q.append((0, 0))
    cost = 0

    for i in range(1, n + 2):
        while q and q[0][0] < i - k:
            q.popleft()
        if q:
            cost = max(q[0][1], a[i])
            while q and q[-1][1] >= cost:
                q.pop()
            q.append((i, cost))
    return cost

    
for _ in range(t):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split())) + [0]
    print(solve_one(n, k, a))

06_前缀和

n, q = map(int, input().split())
s = input().strip()

pref = [[0] * (n + 1) for _ in range(26)]

for i in range(n):
    for c in range(26):
        pref[c][i + 1] = pref[c][i]
    pref[ord(s[i]) - 97][i + 1] += 1

for _ in range(q):
    l, r = map(int, input().split())
    flag = False
    for c in range(26):
        if pref[c][r] - pref[c][l - 1] == 1:
            flag = True
            break
    print("YES" if flag else "NO")

07_路径构造

import sys
input = sys.stdin.readline

q = int(input())
S_list = [int(input()) for _ in range(q)]
n = max(S_list).bit_length()  # 最大S的二进制位数

print(n + 1, 3)
for i in range(n):
    print(0, 1 << i, 0)
print("0 0 0")

for S in S_list:
    path = []
    flag = 1  # 奇偶标志，决定RR还是LL
    for i in range(n):
        if (S >> i) & 1:
            path.extend(['RR' if flag else 'LL', 'D'])
            flag ^= 1
        else:
            path.append('D')
    if flag:
        path.append('RR')
    print(''.join(path))

08_二分图染色

BFS 版本

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
c = [int(x) for x in input().split()]
adj = [[] for _ in range(n)]

for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

visited = [-1] * n  # -1: 未访问, 0/1: 染色结果
ans = 0

for i in range(n):
    if visited[i] != -1:
        continue

    q = deque([i])
    visited[i] = 0
    res = [0, 0]  # res[0]: 以0为基准的修改次数, res[1]: 以1为基准的修改次数

    while q:
        u = q.popleft()
        # 计算两种基准下的修改次数
        res[0] += visited[u] ^ c[u]       # 若最终为0，需要修改多少次
        res[1] += (visited[u] ^ 1) ^ c[u] # 若最终为1，需要修改多少次

        for v in adj[u]:
            if visited[v] == -1:
                q.append(v)
                visited[v] = visited[u] ^ 1
            elif visited[v] == visited[u]:
                print("Impossible")
                exit()

    ans += min(res)

print(ans)

DFS 版本（递归）

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
node = list(map(int, input().split()))

adj = [[] for _ in range(n)]
for _ in range(n):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

vis = [-1] * n

def dfs(u, c):
    vis[u] = c
    cnt = (vis[u] != node[u])  # 当前颜色与node[u]不匹配的个数
    total = 1
    for v in adj[u]:
        if vis[v] == c:
            return False, 0, 0
        if vis[v] == -1:
            ok, cc, tot = dfs(v, 1 ^ c)
            if not ok:
                return False, 0, 0
            cnt += cc
            total += tot
    return True, cnt, total

ans = 0
for u in range(n):
    if vis[u] == -1:
        ok, c, tot = dfs(u, 0)
        if not ok:
            print("Impossible")
            exit()
        ans += min(c, tot - c)

print(ans)

13_dp

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# dp[i][j]: 考虑A前i个和B前j个的最长友好数组长度
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] + dp[i - 1][j - 1] == B[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[n][m])