8.29 美团笔试 算法(1, 1, 0.91, 1)

因此在某些明文的传输中会使用一种加密策略，小团如果需要传输一个字符串 S，
则他会为这个字符串添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个 “MT” 子序列，且以 T 结尾。
尾部字符串需要满足至少包含一个 “MT” 子序列，且以 M 开头。例如 AAAMT 和 MAAAT 都是一个合法的头部字符串，
而 MTAAA 就不是合法的头部字符串。很显然这样的头尾字符串并不一定是唯一的，因此我们还有一个约束，就是 S 是满足头尾字符串合法的情况下的最长的字符串。 

def solve(n, s):
    l, r = 0, n - 1
    while s[l] != 'M':
        l += 1
    l += 1
    while s[l] != 'T':
        l += 1
    l += 1
    while s[r] != 'T':
        r -= 1
    r -= 1
    while s[r] != 'M':
        r -= 1
    r -= 1
    print(s[l: r + 1])


if __name__ == '__main__':
    n = int(input())
    s = input()
    solve(n, s)

def solve(n, nums):
    visited = [False] * (n + 1)
    ret = [0] * n
    for idx, cnums in enumerate(nums):
        for k in cnums:
            if not visited[k]:
                ret[idx] = k
                visited[k] = True
                break
    for _ in ret:
        print(_, end=' ')


if __name__ == '__main__':
    n = int(input())
    nums = [0] * n
    for i in range(n):
        nums[i] = list(map(int, input().split()))
    solve(n, nums)

def solve(n, x, y, graph):
    dx = [None] * (n + 1)
    dy = [None] * (n + 1)
    if x == y:
        print(0)
        return
    que = deque()
    que.append([x, 0])
    while que:
        node, cur = que.popleft()
        dx[node] = cur
        for _node in graph[node]:
            if dx[_node] is None:
                que.append([_node, cur + 1])
    que = deque()
    que.append([y, 0])
    while que:
        node, cur = que.popleft()
        dy[node] = cur
        for _node in graph[node]:
            if dy[_node] is None:
                que.append([_node, cur + 1])
    ret = 0
    for xx, yy in zip(dx[1:], dy[1:]):
        if xx >= yy:
            ret = max(ret, xx)
    print(ret)


if __name__ == '__main__':
    n, x, y = map(int, input().split())
    graph = defaultdict(list)
    for i in range(n - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    solve(n, x, y, graph)

小团从某不知名论坛上突然得到了一个测试默契度的游戏，想和小美玩一次来检验两人的默契程度。
游戏规则十分简单，首先有给出一个长度为 n 的序列，最大值不超过 m。  小团和小美各自选择一个 [1,m] 之间的整数，
设小美选择的是 l，小团选择的是 r，我们认为两个人是默契的需要满足以下条件:  1. l 小于等于 r。  2. 对于序列中的元素 x，如果 0<x<l, 或 r<x<m+1,  则 x 按其顺序保留下来，要求保留下来的子序列单调不下降。  小团为了表现出与小美最大的默契，因此事先做了功课，他想知道能够使得两人默契的二元组 <l,r> 一共有多少种。  我们称一个序列 A 为单调不下降的，当且仅当对于任意的 i>j, 满足 A_i>=A_j。  输入第一行包含两个正整数 m 和 n，表示序列元素的最大值和序列的长度。(1<=n,m<=100000)  输入第二行包含 n 个正整数，表示该序列  5 5 4 1 4 1 2  10。

def isvalid(nums):
    for idx, val in enumerate(nums):
        if idx == 0:
            continue
        if val < nums[idx - 1]:
            return False
    return True

def solve(m, n, nums):
    ret = 0
    r = m
    while r > 0:
        tmp1 = []
        for k in nums:
            if k > r:
               tmp1.append(k)
        if not isvalid(tmp1):
            break
        ll, rr = 1, r
        c = 0
        while ll <= rr:
            mid = (ll + rr) // 2
            tmp2 = []
            for k in nums:
                if k < mid&nbs***bsp;k > r:
                    tmp2.append(k)
            if isvalid(tmp2):
                c = mid
                ll = mid + 1
            else:
                rr = mid - 1
        r -= 1
        ret += c
    print(ret)



if __name__=='__main__':
    m, n = map(int, input().split())
    nums = list(map(int, input().split()))
    solve(m, n, nums)