阿里 5.16 笔试真题 - AI研发岗

import sys

input = sys.stdin.readline

MOD = 10**9 + 7


def solve(s):
    # suf_oc 初始为整个串中 'o' 或 'c' 的总数
    suf_oc = 0
    for ch in s:
        if ch == 'o' or ch == 'c':
            suf_oc += 1
    cnt_o = 0  # 当前下标左侧已出现的 'o' 数
    ans = 0
    for ch in s:
        # 先把当前位从后缀剩余中扣掉，使 suf_oc 严格表示「右侧」合法 k 的数量
        if ch == 'o' or ch == 'c':
            suf_oc -= 1
        # 当前是 'p' 才贡献方案：左侧 'o' 数 * 右侧合法 k 数
        if ch == 'p':
            ans = (ans + cnt_o * suf_oc) % MOD
        if ch == 'o':
            cnt_o += 1
    return ans


T = int(input())
out = []
for _ in range(T):
    input()
    s = input().strip()
    out.append(str(solve(s)))
print('\n'.join(out), end='')

import sys

input = sys.stdin.readline


def solve(arr):
    # 单元素能贡献给 x 的最大值即 a[i] 自身
    # 多元素累积时，答案就是所有元素按位或
    res = 0
    for v in arr:
        res |= v
    return res


data = sys.stdin.buffer.read().split()
idx = 0
T = int(data[idx]); idx += 1
out = []
for _ in range(T):
    n = int(data[idx]); idx += 1
    a = [int(data[idx + j]) for j in range(n)]
    idx += n
    out.append(str(solve(a)))
print('\n'.join(out), end='')

import sys
from bisect import bisect_right


def solve(n, a):
    if n == 1:
        return 0
    if n == 2:
        return abs(a[1] - a[0])

    base = 0
    plo = [0] * (n - 1)
    phi = [0] * (n - 1)
    for k in range(n - 1):
        base += abs(a[k + 1] - a[k])
        plo[k] = a[k] if a[k] < a[k + 1] else a[k + 1]
        phi[k] = a[k] if a[k] > a[k + 1] else a[k + 1]

    # 扫描线统计：每个值被多少个相邻对的区间 [plo, phi] 覆盖
    events = {}
    for k in range(n - 1):
        events[plo[k]] = events.get(plo[k], 0) + 1
        events[phi[k] + 1] = events.get(phi[k] + 1, 0) - 1
    keys = sorted(events.keys())
    cum = 0
    cum_at = []
    for k in keys:
        cum += events[k]
        cum_at.append(cum)

    def count_cover(v):
        idx = bisect_right(keys, v) - 1
        if idx < 0:
            return 0
        return cum_at[idx]

    def covers(lo, hi, v):
        return 1 if lo <= v <= hi else 0

    ans = base
    for i in range(n):
        v = a[i]
        has_bridge = False
        blo = bhi = 0
        if i == 0:
            save = abs(a[1] - a[0])
            cnt = count_cover(v) - covers(plo[0], phi[0], v)
            head_b, tail_b = a[1], a[n - 1]
        elif i == n - 1:
            save = abs(a[n - 1] - a[n - 2])
            cnt = count_cover(v) - covers(plo[n - 2], phi[n - 2], v)
            head_b, tail_b = a[0], a[n - 2]
        else:
            blo = a[i - 1] if a[i - 1] < a[i + 1] else a[i + 1]
            bhi = a[i - 1] if a[i - 1] > a[i + 1] else a[i + 1]
            has_bridge = True
            save = abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1])
            cnt = (count_cover(v)
                   - covers(plo[i - 1], phi[i - 1], v)
                   - covers(plo[i], phi[i], v)
                   + covers(blo, bhi, v))
            head_b, tail_b = a[0], a[n - 1]

        if cnt >= 1:
            ins = 0
        else:
            # v 是数组的严格极值，暴力枚举有效相邻对求最小插入开销
            best = min(abs(v - head_b), abs(v - tail_b))
            for k in range(n - 1):
                if i > 0 and k == i - 1:
                    continue
                if i < n - 1 and k == i:
                    continue
                lo, hi = plo[k], phi[k]
                cost = 0 if lo <= v <= hi else abs(v - lo) + abs(v - hi) - (hi - lo)
                if cost < best:
                    best = cost
            if has_bridge:
                cost = 0 if blo <= v <= bhi else abs(v - blo) + abs(v - bhi) - (bhi - blo)
                if cost < best:
                    best = cost
            ins = best

        cand = base - save + ins
        if cand < ans:
            ans = cand
    return ans


data = sys.stdin.buffer.read().split()
idx = 0
T = int(data[idx]); idx += 1
out = []
for _ in range(T):
    n = int(data[idx]); idx += 1
    a = [int(data[idx + j]) for j in range(n)]
    idx += n
    out.append(str(solve(n, a)))
print('\n'.join(out), end='')