1. 使括号有效的最小添加

如果是单类别的括号，就是：
LeetCode921题
给定一个由 ‘（’ 和 ‘）’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘（’ 或是
‘）’，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者

它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者

它可以被写作 (A)，其中 A是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
class Solution(object):
    def minAddToMakeValid(self, S):
        stack=['?'] # 加一个'?'打底，防止栈为空并且需要pop时报错
        for i in S:
            if stack[-1]=='(' and i==')':# 栈顶为左括号，且当前元素为右括号，可以互相抵消。此时栈顶出栈
                stack.pop()
            else: # 抵消不了的元素通通入栈
                stack.append(i)
        return len(stack)-1 ```

本题解题思路：

经典区间dp问题，构建一个len(s)*len(s)的二维数组。dp[i][j]代表着从字符串i位置到j位置需要的最小括号匹配数。
对角线部分（dp[i][i]）为1，从下到上遍历上三角部分， dp[0][len(s)-1] 为所求结果
当i<j 时:
- 如果第i个位置和第j个位置的两个括号是匹配的（if((s[i]=='[' && s[j]==']') or (s[i]=='(' && s[j]==')'))），那么dp[i][j] = dp[i+1][j-1]，相当于两边分别都往外扩了一步；
- 如果第i个位置和第j个位置的两个括号无法抵消，则 dp[i][j] = dp[i][k]+dp[k+1][j] k的范围为[i,j):
  - i和j处的括号无法抵消时，i和j的加入会影响i+1到j-1范围内的括号添加数。~~因此不能用dp[i][j-1]和dp[i+1][j]来考虑dp[i][j]的状态转移。~~
  - 所以用k遍历i到j之间的dp[i][k]+dp[k+1][j]相连结果。取相连结果的最小值（如dp[2][4]为 dp[2][2]+dp[3][4],dp[2][3]+dp[4][4]中的最小值）
  - i和j之间由两个子字段组成。两个子字段的dp值相加（即：dp[i][k]+dp[k+1][j]）为潜在的dp[i][j]。最小的相加值“获胜”

def helper(s):
    n=len(s)
    dp=[[0 for _ in range(n)] for _ in range(n)]
    # 对角线初始化为1
    for i in range(n):
        dp[i][i] =1
    for i in range(n-2,-1,-1):
        for j in range(i+1,n):
            # 当i < j时
            # 如果能抵消，则 dp[i][j]=dp[i+1][j-1]
            if ((s[i]=='[' and s[j]==']') or  (s[i]=='(' and s[j]==')')):
                dp[i][j]=dp[i+1][j-1]
            else:
                # 如果不能抵消，则 dp[i][j] = dp[i][k]+dp[k+1][j] k的范围为[i,j)
                temp=n
                for k in range(i,j):
                    temp=min(temp,dp[i][k]+dp[k+1][j])
                dp[i][j]=temp
        print(dp[i])
    print(dp[0][-1])
# s=str(input().strip())
s='()[)[)(][(]([)]]]((]]'
helper(s)

2. 求抛物线围成的面积

题目要求取6位小数，注意输出的格式：print("{:.6f}".format(ans))
Python format 格式化函数
计算n组面积

import math
def solution(A,B,C,D):
    # 简单的微积分后，求得的面积
    ans = (1/3)*A*(D**3-C**3) + 0.5*(D**2-C**2)+B*(D-C)
    return ans

n = int(input())
for _ in range(n):
    a,b,c,d = list(map(int,input().split()))
    ans = abs(solution(a,b,c,d))
    # print("%.6f"%ans)
    print("{:.6f}".format(ans))

3. 选队长的方案

主要考察的知识点：

排列组合找规律：方案数为 ans=n * 2^(n-1)
用快速幂来计算方案数：Krahets的快速幂知识点讲解

class Solution:
    def myPow(self, x, n) :
        if x == 0: return 0 # 若为0，直接返回结果
        res = 1
        if n < 0: x, n = 1 / x, -n # 把n为负数的情况转化成正数
        while n:
            if n%2==1:res*=x # res随着x的增大越来越大
            x*=x 
            n=n//2 # 幂每次向下除2，直至为0
        return res

所以本题把方案数带进去即可：

def myPow(x,n) :# 求x的n次方
    if x == 0: return 0
    res = 1
    if n < 0: x, n = 1 / x, -n
    while n:
        if n % 2 == 1: res *= x
        x *= x
        n = n // 2
    return res

n=int(input().strip())
output=n*myPow(2,n-1)%(10**9+7)
print(output)

4. 计算图的价值

统计小伙伴相同的点对数量。用 defaultdict 实现。
（AC 90%）

from collections import defaultdict

# 数据输入
'''
4 3
1 2
2 3
2 4
'''
n,m=map(int,input().strip().split())
res=[]
for i in range(m):
    res.append(list(map(int,input().strip().split())))

# 统计每个点的对应的小伙伴。主人（1个）：小伙伴（1个或多个）
host=defaultdict(list)
for x,y in res:
    host[x].append(y) # 键为x对应的小伙伴
    host[y].append(x)
# print(host) # defaultdict(<class 'list'>, {1: [2], 2: [1, 3, 4], 3: [2], 4: [2]})

# 统计小伙伴相同的（主人）键。此时，小伙伴(处理过了，是独特的1个名称)：主人（1个或多个）
partner=defaultdict(list)
for u,v in host.items():
    v=''.join(map(str,sorted(v))) # 小伙伴从  [1,3,4]-> 134
    partner[v].append(u)
# print(partner) # defaultdict(<class 'list'>, {'2': [1, 3, 4], '134': [2]})

# partner中，主人数>1的才会对图产生价值 （1:2，然后 2:1 的这种无价值）
ans=0
for v,u in partner.items():
    hostLen=len(u)
    if hostLen>1:
        # 从n种样品中 取 2种，无先后区分。则一共有 n*（n-1）/2 种组合
        ans+=hostLen*(hostLen-1)/2
print(int(ans))