第一题

• 回文字符，AC

• 遍历即可

def first():
    n = int(input())
    s = input()
    # s = 'acacb'
    change = 0
    for i in range((len(s) + 1) // 2):
        if s[i] != s[- i - 1]:
            change += 1
    print(change)

第二题

• 方块染色，AC

• 求 n，m 的最小因子

def second():
    import math
    t = int(input())
    while t > 0:
        t -= 1
        n, m = map(int, input().split(' '))
        res = min(n, m)
        if n == 1 or m == 1:
            res = max(n, m)

        for i in range(2, int(math.sqrt(n)) + 1):
            if i >= res:
                break
            if n % i == 0:
                res = min(res, i)
                break
        for i in range(2, int(math.sqrt(m)) + 1):
            if i >= res:
                break
            if m % i == 0:
                res = min(res, i)
                break
        print(res)

第三题

• 最大或值的最小长度，暴力AC

def third():
    n = int(input())
    nums = list(map(int, input().split(' ')))
    res = 0
    for i in nums:
        res = res | i
    length = len(nums)

    end = 0
    temp = 0
    for i in range(len(nums)):
        temp = temp | nums[i]
        if temp == res:
            end = i
            break

    for i in range(end, len(nums)):
        temp = 0
        for j in range(i, -1, -1):
            temp = temp | nums[j]
            if temp == res:
                length = min(length, i - j + 1)
                break

    print(length)

第四题

• 连通情况下的最大载货量

• 求最大生成树

• 类似于Kruskal算法，每次取权值最大的边，用并查集来看是否连通，写出来只通过 20%，没查出来哪有错

def four():
    def comb(x, y):
        if x == y:
            return 1

        res = 1
        for i in range(y):
            res = res * (x - i) // (i + 1)
        return res

    def merge(x, y):
        r1 = find(x)
        r2 = find(y)
        if r1 <= r2:
            point[r2] = r1
        else:
            point[r1] = r2

    def find(x):
        root = x
        if point[x] != x:
            root = find(point[x])
            point[x] = root
        return root

    n, m = map(int, input().split(' '))
    path = []
    point = {}
    for _ in range(m):
        u, v, a, b = map(int, input().split(' '))
        path.append((u, v, comb(a, b)))
        point[u] = u
        point[v] = v
    path.sort(key=lambda x: -x[2])

    r = 0
    for uu, vv, c in path:
        if point[uu] == point[vv]:
            continue
        merge(uu, vv)
        r = (r + c) % int(1e9 + 7)

    if len(point) < n:
        print(-1)
    else:
        print(r)