阿里 3.25 笔试真题 - 算法岗

import sys
input = sys.stdin.readline

def main():
    T = int(input())
    out = []
    for _ in range(T):
        n = int(input())
        if n <= 3:
            out.append("-1")
        elif n % 2 == 0:
            out.append("1 2")
        else:
            out.append(f"{(n - 1) // 2} {n - 1}")
    print("\n".join(out))

main()

import sys
input = sys.stdin.readline

def main():
    T = int(input())
    out = []
    for _ in range(T):
        n, m = map(int, input().split())
        grid = []
        for i in range(n):
            grid.append(input().strip())

        INF = float('inf')
        f = [[0] * m for _ in range(n)]

        # 从右下角倒推
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                val = 1 if grid[i][j] == '1' else -1
                if i == n - 1 and j == m - 1:
                    f[i][j] = val
                    continue

                # 下一步的编号是 (i + j + 1)，1-indexed
                # 奇数步由玩家一操作（最大化），偶数步由玩家二操作（最小化）
                next_step = i + j + 1  # 1-indexed
                candidates = []
                if i + 1 < n:
                    candidates.append(f[i + 1][j])
                if j + 1 < m:
                    candidates.append(f[i][j + 1])

                if next_step % 2 == 1:
                    # 玩家一（天才）选择，最大化
                    f[i][j] = val + max(candidates)
                else:
                    # 玩家二（笨蛋）选择，最小化
                    f[i][j] = val + min(candidates)

        out.append(str(f[0][0]))
    print("\n".join(out))

main()

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right, insort

def main():
    n, m = map(int, input().split())
    # intervals: 存储 (left, right) 的有序列表，按 left 排序，互不重叠
    intervals = []  # list of [left, right]
    # 为了方便 bisect，单独维护一个 lefts 数组
    lefts = []

    out = []
    for _ in range(m):
        l, r, x = map(int, input().split())

        # 合并区间 [l, r]
        new_l, new_r = l, r

        # 找到第一个左端点 <= r 的区间中，可能与 [l, r] 重叠的
        # 区间 [a, b] 与 [l, r] 重叠或相邻的条件：a <= r + 1 且 b >= l - 1
        # 即：a <= new_r + 1 且 b >= new_l - 1

        # 找到 lefts 中第一个 > new_r + 1 的位置
        right_bound = bisect_right(lefts, new_r + 1)
        # 从 right_bound - 1 往前找，找到所有 b >= new_l - 1 的区间
        # 但更简单的做法：找到所有可能重叠的区间

        # 找起始位置：第一个右端点 >= new_l - 1 的区间
        # 由于我们按 left 排序，需要从 bisect_right(lefts, new_l - 1) - 1 开始往左检查
        # 但往左检查效率不高，换一种方式

        # 找所有 left <= new_r + 1 的区间（索引 0..right_bound-1）
        # 在其中找 right >= new_l - 1 的
        # 从最左边的可能重叠区间开始

        # 先找第一个可能重叠的：left <= new_r + 1 的区间中，
        # 我们从 bisect_left(lefts, new_l) 往前一个开始检查
        start = bisect_right(lefts, new_l) - 1
        if start < 0:
            start = 0

        # 收集所有要合并的区间索引
        to_remove = []
        for idx in range(start, len(intervals)):
            a, b = intervals[idx]
            if a > new_r + 1:
                break
            if b >= new_l - 1:
                # 重叠或相邻
                new_l = min(new_l, a)
                new_r = max(new_r, b)
                to_remove.append(idx)

        # 从后往前删除
        for idx in reversed(to_remove):
            intervals.pop(idx)
            lefts.pop(idx)

        # 插入新区间
        pos = bisect_left(lefts, new_l)
        intervals.insert(pos, (new_l, new_r))
        lefts.insert(pos, new_l)

        # 查询 x 所在的区间
        qi = bisect_right(lefts, x) - 1
        if qi >= 0 and intervals[qi][0] <= x <= intervals[qi][1]:
            out.append(str(intervals[qi][1]))
        else:
            out.append(str(x))

    print("\n".join(out))

main()