题目来源：https://www.acwing.com/activity/content/2869/

最长公共上升子序列

题意

对于两个数列 A和 B。所有的公共上升子序列中最长的就是最长公共上升子序列。

注：子序列不一定连续

A B < 3000

思路

最长上升子序列

  • dp[i]：以i结尾的上升子序列的最大长度。
  • ”上一步“：以x结尾的，x<i。
  • 状态转移：对每个状态，枚举之前的状态即可

最长公共子序列

方法1

  • dp[i][j]只考虑A的前i个数，以B[j]结尾的最长公共子序列
  • dp[i][j]=
    • if A[i]==B[j] : max( dp[i-1][0...j-1]+1)。可预先计算mx，优化时间复杂度。（不重不漏）
    • else : dp[i-1][j] （不重不漏）

方法2（更直观）

  • dp[i][j]只考虑A的前i个数，B的前 j 个数的答案
  • dp[i][j]=
    • if A[i]==B[j] : dp[i-1][j-1]+1
    • max(dp[i][j-1], dp[i-1][j]) （有重不漏，因为是最大值，不影响）
1
2
3
4
5
6
7
8
9
10
11
12
13
# 方法一
for i in range(1,N+1):
    mx = 0
    for j in range(1,M+1):
        if A[i]==B[j]:
            dp[i][j] = mx+1
        else:
            dp[i][j] = dp[i-1][j]
        mx = max(dp[i-1][j],mx)
       
            
for j in range(0,M+1):
    ans = max(ans,dp[N][j])
1
2
3
4
5
6
7
8
# 方法二
dp = [[0 for i in range(1010)] for _ in range(1010)]
ans = 0
for i in range(1,N+1):
    for j in range(1,M+1):
        if A[i]==B[j]:dp[i][j] = dp[i-1][j-1]+1
        else: dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[N][M])

本题

  • dp[i][j]只考虑A的前i个数，以B[j]结尾的最长公共子序列
  • dp[i][j]=
    • if A[i]==B[j]
      • max( dp[i-1][k]+1) when 0<k=<j and B[k] < B[j]
      • 优化：因为A[i]==B[j]，所以有： when 0<k<j and B[k] < A[i]
      • 外层循环A[i]不变，所以可提到外面
    • else
      • dp[i-1][j]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input().strip())
A = list(map(int,input().strip().split()))
B = list(map(int,input().strip().split()))
A = [0]+A;B = [0]+B
dp = [[0 for i in range(3010)] for _ in range(3010)]
ans = 0
for i in range(1,N+1):
    mx = 0
    for j in range(1,N+1):
        dp[i][j]=dp[i-1][j]
        if A[i]==B[j]: dp[i][j] = max(dp[i][j],mx+1)
        if A[i]>B[j]: mx = max(mx,dp[i-1][j])
        
ans = 0
for i in range(1,N+1):
    ans = max(ans,dp[N][i])
print(ans)

背包九讲

波动数列

题意

他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？

思路

因为起始数字任意，对sum的影响是k*n。经过推导后，发现可以只考虑起始为0的情况。

对于一种组合，sum=A ，只要A%n = s%n，这种组合就合法

可以看成分组背包问题，每组两个物品，对于从左往右数第g组 (1<=g<n) ，重量为(n-g)*a和(n-g)*b。

f[i][j]表示前i组中，sum%n为j的情况总数。

注意有个坑，一共只有n-1组物品，而不是n组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
MOD = 100000007
n,s,a,b = map(int,input().strip().split(" "))
k = s%n # 
f = [[0 for i in range(n+5)] for j in range(n+5)]

f[0][0]=1
for i in range(1,n):
    va = (n-i)*a
    vb = (n-i)*(-b)
    for j in range(n): # 因为要取模，所以可以为负
        f[i][j]=(f[i][j]+f[i-1][((j-va)%n+n)%n])%MOD
        f[i][j]=(f[i][j]+f[i-1][((j-vb)%n+n)%n])%MOD
print(f[n-1][(s%n+n)%n])

能量项链

题意

思路

区间DP+破环为链

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input())
A = list(map(int,input().strip().split()))
for i in range(N):
    A.append(A[i])
dp = [[0 for i in range(2*N+5)] for j in range(2*N+5)]

for le in range(2,N+1):
    for l in range(2*N):
        if l + le -1 >= 2*N-1:break
        r = l + le -1
        for k in range(l,r):
            dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r]+A[l]*A[k+1]*A[r+1])

ans = 0
for i in range(N):
    ans = max(ans,dp[i][i+N-1])
print(ans)

质数距离(筛，[L,R]区间的素数)

题意

给定两个整数 L和 U，你需要在闭区间[L,U] 内找到距离最接近的两个相邻质数 C1和 C2（即 C2−C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数 D1和 D2（即 D1−D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

其中 L 和 U 的差值不会超过 1e6。

L U< 2e9

思路

直接从0开始筛会TLE。

对于任意一个合数x，他一定存在最小质因子d，d <= sqrt(x)

  • 先筛出[2,1e5]内的质数
  • 枚举d属于[2,1e5]，把[L , R]内所有以d为最小质因子的合数筛掉
  • 最后剩下的都是质数了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
st = [False for i in range(50010)]
primes = [0 for i in range(50010)]
cnt = 0

def fun(n):
    global cnt
    for i in range(2,n+1):
        if st[i]==False:
            primes[cnt]=i
            cnt+=1
        j = 0
        while primes[j]*i<=n:
            st[primes[j]*i] = True
            if i % primes[j]==0:break
            j+=1
            
fun(50000)
while True:
    try:
        l,r = map(int,input().split())
        su = [False]*(r-l+1)
        for i in range(cnt):
            p = primes[i]
            for j in range(max(2*p,((l+p-1)//p)*p),r+1,p):
                su[j-l]=True
        li = []
        for i in range(r-l+1):
            if su[i]==False and i+l>1: li.append(i+l)
        mx,mi = -1,2000000000
        mxa,mia = [],[]
        if len(li)==1:
            print("There are no adjacent primes.")
        else:
            for i in range(len(li)-1):
                if mx < li[i+1]-li[i]:
                    mx = li[i+1]-li[i]
                    mxa = [li[i],li[i+1]]
                if mi > li[i+1]-li[i]:
                    mi = li[i+1]-li[i]
                    mia = [li[i],li[i+1]]
            print("%d,%d are closest, %d,%d are most distant."%(mia[0],mia[1],mxa[0],mxa[1]))
    except :
        break

快速幂求逆元

题意

思路

当b和m互质时，b在%m下的逆元是b^m-2。

x/b = x*b^m-2 mod m

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def qmi(a,k,p):
    res = 1
    while k:
        if k&1:res= (res*a)%p
        k = k>>1
        a = (a*a)%p
    return res%p

n = int(input())
for i in range(n):
    a,p = map(int,stdin.readline().strip().split())
    if a%p==0:print("impossible")
    else: print(qmi(a,p-2,p))

Hankson的趣味题(约数)

题意

已知正整数 a0,a1,b0,b1设某未知正整数 x满足：

  1. x和 a0 的最大公约数是 a1
  2. x和 b0 的最小公倍数是 b1

求解满足条件的 x 的个数。

2000组数据

a0 a1 b0 b1<2e9

思路

暴力

注意到x是b1的约数。直接枚举b1的所有约数从1-sqrt(b1)，时间复杂度2000 5000 logN

优化1

可以先处理出质数，通过枚举质数得到若干（质数，次方），再dfs得到约数

优化2

代码

略

数三角形

题意

给定一个 n×m的网格，请计算三点都在格点上的三角形共有多少个。

注意：三角形的三点不能共线。

思路

直接求有难度。考虑容斥原理，先求出所有的$C_{m+n}^3$，再减去不合法的。

不合法的按照斜率分类：

  • 斜率为0：$mC_{n}^3$
  • 斜率正无穷：$nC_{m}^3$
  • 斜率为正和斜率为负的情况相等，只用考虑为正的情况
  • 左下角第一个和右上角第二个点的差为（i，j）时，有（n-i+1）*（m-j+1）种，中间的点gcd(i,j)-1个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def C(x,y):
    return x*(x-1)*(x-2) // 3 //2

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n,m = map(int,input().strip().split())
n,m = n+1,m+1
ans = C(m*n,3)-m*C(n,3)-n*C(m,3)
n,m = n-1,m-1
for i in range(1,n+1):
    for j in range(1,m+1):
        ans -= 2*(n-i+1)*(m-j+1)*(gcd(i,j)-1)
print(int(ans))