文远知行算法笔试0921

题1：数组中找一段异或和等于 k 的子数组

题干
给定整数数组 a[1..n] 与整数 k，求是否存在连续子数组使其异或和为 k。若存在输出该子数组的左右下标（1-based），否则输出 -1。

说明
定义前缀异或 px[i] = a1 ⊕ ⋯ ⊕ ai，则区间 [l, r] 的异或和为 px[r] ⊕ px[l−1]。

import sys

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    n, k = data[0], data[1]
    a = data[2:2+n]

    first_pos = {0: 0}  # px[0]=0 at position 0
    px = 0
    for r in range(1, n+1):
        px ^= a[r-1]
        need = px ^ k                   # need px[l-1] == px[r]^k
        if need in first_pos:
            l = first_pos[need] + 1     # 1-based
            print(l, r)
            return
        if px not in first_pos:         # keep earliest
            first_pos[px] = r
    print(-1)

if __name__ == "__main__":
    main()

题2：最长“美观”括号子串（支持 () [] {}）

题干
给定仅由括号 ()[]{} 组成的字符串 s，定义：

• 空串是美观；
• 若 A 美观，则 (A)、[A]、{A} 也美观；
• 若 A、B 都美观，则 AB 也美观。

求 s 中最长美观的连续子串长度。

import sys

pairs = {')':'(', ']':'[', '}':'{'}

def longest_beautiful(s: str) -> int:
    idx_stack = [-1]   # 下标栈，-1 为哨兵
    ch_stack  = ['#']  # 类型栈
    ans = 0
    for i, ch in enumerate(s):
        if ch in "([{":
            idx_stack.append(i)
            ch_stack.append(ch)
        else:
            if len(idx_stack) > 1 and ch_stack[-1] == pairs.get(ch, '?'):
                idx_stack.pop()
                ch_stack.pop()
                ans = max(ans, i - idx_stack[-1])
            else:
                idx_stack.append(i)
                ch_stack.append('#')    # 新的无效基底
    return ans

def main():
    s = sys.stdin.read().strip()
    print(longest_beautiful(s))

if __name__ == "__main__":
    main()

题3：n×m 乘法表的第 k 小元素

题干
乘法表第 i 行第 j 列为 i×j（下标从 1 开始）。给定 n, m, k，将整个乘法表按非降序排列后，求第 k 个元素。

思路
二分答案 x，并统计表中不大于 x 的个数：

找到最小的 x 使得 count(x) ≥ k。

import sys

def count_le(n, m, x, k):
    s = 0
    up = min(n, x)
    for i in range(1, up + 1):
        s += min(m, x // i)
        if s >= k:
            return s
    return s

def main():
    n, m, k = map(int, sys.stdin.read().strip().split())
    if n > m:
        n, m = m, n
    lo, hi = 1, n * m
    while lo < hi:
        mid = (lo + hi) // 2
        if count_le(n, m, mid, k) >= k:
            hi = mid
        else:
            lo = mid + 1
    print(lo)

if __name__ == "__main__":
    main()