A Small World of unnamedtat

unnamedtat的技术博客

0%

刷题记录

发表于 更新于 分类于
本文字数： 2.6k
个人做题记录

本篇内容包括：

DP

第十五课：线性dp，计数dp，区间dp

图形排版

解题思路：

由于删除一张图片i后，只会对从i+1的图片的行高产生影响，因此此题可拆分成三个part：

①依次删除下标为i的图片，将i+1之后的新的行高，依次加上之前的累计行高的for循环；②新行高的计算。我们可能会碰到多次以不同的图片、状态开始插入，但从某张同样的图片开始新起一行，这新的一行的行高一定是相同的，因此可以用dp状态记录；③而行高的计算依赖于每张图片的加入规则，不再赘述。

  • ①的for循环：在累计的h高度下，同时依次计算前面i-1张图片的行高，加上后面i+1张图片的行高，即得到去掉第i张图片的行高，进行比较保存。
  • ②：计算后续i+1张图片行高
    • 算出从每一张图片新起一行(width=0,height=0)，填到最后一张的行高【动态规划（倒序）的for循环，计算1次】：
      • 从最后一张N-1填起，填的规则遵守③，dp数组状态dp[i]dp[i]。
      • 一直填到下一行（满足图片序号< N，且当前width<页面宽度），找到之前可以复用的状态dp[j]dp[j]，并记录此行高度h
      • 状态转移方程为dp[i]=h+dp[j]dp[i]=h+dp[j]
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
44
45
46
47
48
import os
import sys

a = []
dp = [ 0 for i in range(int(1e5+1))]#k行及之后的行高
M = 0
N = 0

def add(cur_wh,k):#将第k张图片加入cur行
  #不压缩的情况
  if cur_wh[0]+a[k][0]<=M:
    cur_wh[0] += a[k][0]
    cur_wh[1] = max(cur_wh[1], a[k][1])
  #需要压缩
  else:
    w = M-cur_wh[0]
    cur_wh[0]=M
    cur_wh[1]=max(cur_wh[1],(w*a[k][1]+a[k][0]-1) // a[k][0])
  return

def getBlowHeight(cur_wh,k):
  # 计算出在目前状况下从k图到填满cur行的【k+j】处的行高
  while k<N and cur_wh[0]<M:
    add(cur_wh,k)
    k+=1
  # 最后下标等于【k+j+1】处，即新的一行
  # 将该行行高与【k+j+1】处后续行高相加并返回
  return cur_wh[1]+dp[k]

if __name__=='__main__':
  M, N = map(int,input().strip().split())
  for i in range(N):
    a.append(list(map(int,input().strip().split())))
    #初始化dp数组，即从i张图片新起一行填到最后一行的这部分行高
  for i in range(N-1, -1, -1):
    dp[i]=getBlowHeight([0, 0], i)
  h=0#累计高度
  min_h=1e7
  cur_wh=[0,0]
  for i in range(N):#计算去除i后 h+以i+1开始的行高
    min_h=min(min_h,h+getBlowHeight(cur_wh[:],i+1))#记录最小高度
   #更新累计高度
    add(cur_wh,i)
    if cur_wh[0] == M:  # 当前行已填满，另起一行
      h += cur_wh[1]
      cur_wh = [0, 0]
print(min_h)

松散子序列

由于每一项的值都大于0，所以我们要尽可能的多选，将问题转换成：给定一个序列，要求不能选取相邻的元素，问能获得的最大价值是多少？

实际上，当前的取舍状态只影响上一项和下一项的取舍状态，于是在遍历到每一项的时候都记录上该项和上一项的取/舍价值即可。则可以说每一个状态（上一步加本一步的取舍操作）都有最佳状态，是贪心的思想。

1、分别记录每项取或不取所形成的价值

2、取的话就等于上一项不取加上本项的价值

3、不取的话等于上一项取或者不取中的最大值

思路和题解来自：线性dp（打家劫舍系列）

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
def get(c):                                       #获得字符的价值
    return ord(c)-ord('a')+1
s=input()
n=len(s)
dp=[[0,0] for i in range(n)]
dp[0][1]=get(s[0])
 
for i in range(1,n):
    dp[i][0]=max(dp[i-1][0],dp[i-1][1])          # 不取，选上一项操作的最大值
    dp[i][1]=dp[i-1][0]+get(s[i])                # 取这一项的话上一项只能不取了
print(max(dp[-1][0],dp[-1][1]))

# 这里还可以进一步压缩

# 数组不取，取
# 初始化取第一个
last=[0,getValue(s[0])]
for i in range(1,len(s)):
    now=[0,0]
    # 计算并更新状态
    now[1]=last[0]+getValue(s[i]) # 取的话要要影响上一项，只有一种情况了
    now[0]=max(last) # 不取的话，不影响上一项，直接取前面情况的可能最大值
    ###由于没有逐个存储
    ### 所以在操纵last变量时一定不要粗心
    ### 后面的运算不能基于已经更改的last
    last=now
print(max(last))

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s)<2:
            return s
        maxlen=1
        indexBegin=0
        #初始化dp数组
        dp=[[False if i!=j else True 
        for i in range(len(s))] for j in range(len(s))]
        #只需要判断≥2的子串，并且对于字串内部子串只用判断该子串≥4(即(j-1)-(i+1)+1>=2)的情况
        for j in range(1,len(s)):
            for i in range(0,j):
                if s[i]==s[j]:
                    if j-i>=3 and dp[i+1][j-1]!=False:
                        dp[i][j]=True
                    elif j-i<3: 
                        dp[i][j]=True
                    else:continue
                    if maxlen<j-i+1:
                        indexBegin=i
                        maxlen=j-i+1
        return s[indexBegin:indexBegin+maxlen]

对局匹配

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
import os
import sys

M=10**5+5
N,K=map(int,input().split())
A=list(map(int,input().split()))
ctn=[0]*M#记录各分数的用户个数

for i in range(N):
  ctn[A[i]]+=1
# 若k=0，可直接计数有多少种不同的分数
if not K:
  print(sum(1 for item in ctn if item>0))
# 否则分成k个等差数列分别计算
else:
  ans = 0#最终结果
  dp=[]#动态规划的数组
  series=[]#存放差值为k的等差数列的对应分数个数
  for i in range(K):
    for j in range(i,max(A)+1,K):# 剩下的数字不可能差值为k
      series.append(ctn[j])
    for j in range(len(series)):
      if j==0:
        dp.append(series[0])#初始默认选择series[0]
      elif j == 1:
        dp.append(max(dp[j-1],series[j]))
      else:
        dp.append(max(dp[j-1],series[j]+dp[j-2]))
    ans+=dp[-1]
    series=[]
    dp=[]
  print(ans)

二分查找

管道

参考：第十四届蓝桥杯省赛 Python B 组 D 题——管道（AC）

解题思路：要求水流覆盖完整个管道的最小时间tmint_{min}。则在整个时间轴上，[tmin,maxtime][t_{min},max_{time}]都满足条件（检测到），而[1,tmin)[1,t_{min})检测不到，则求时间的操作可以转为一个求最小的二分问题。

  1. 初始化lt为tmint_{min}，rt为10910^9
  2. 求中点mid=math.floor((lt+rt)/2)是否满足条件，满足则移动rt=mid，否则移动lt=mid+1
  3. 持续此操作直至满足rt==lt

注意lt的更新。我们认为lt代表未判定是否满足的的最小时间（因此每次需要再＋1来找到未判定的时间，否则产生死指针），而rt本身及右边是满足的时间。

lt的初值是1，因为我们从Si≥1Si \geq 1 开始判定。而rt的初值是: 2×1092\times 10^9！（只在Si=10910^9开一个两端的）

而对于每个时间，我们需要检测其是否满足条件———是否每个管道都覆盖了水。对于每个需要我们验证的固定的时间TiT_i，每个在其规定的SiS_is时间段打开的阀门LiL_i的覆盖区间是一定的：[Li−(Ti−Si)L_i-(T_i-S_i),Li+(Ti−Si)L_i+(T_i-S_i)]，这样的无数个线段。于是这样我们就把检验的问题转为一个经典的区间覆盖问题。

区间覆盖问题分为四步：

  1. 将所有的区间按左端点大小排列
  2. 判断左端点是否能覆盖到1
  3. 以左端点最小的其中一个区间的右端点为r，依次比较下一个更小的左端点是否≤\leq目前的r，满足小于认为覆盖这一片，比较更新r为两者之中最大的右端点，不满足直接结束这一情景的判定
  4. 最后比较r是否大于整个区间的右端点。
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
import math
n,length=map(int,input().split())
ls=[]
for i in range(n):
    ls.append(list(map(int, input().split())))
# 找时间的区间
ls.sort()
lt=ls[0][0]
rt=pow(10,9)*2
while lt<rt:
    mid=math.floor((lt+rt)/2)
    # 这里注意一定要判断阀门是否开启
    cover=[[every_ls[0]-(mid-every_ls[1]),every_ls[0]+(mid-every_ls[1])] \
    for every_ls in ls if mid>=every_ls[1]]
    cover.sort()
    if len(cover) == 0 or cover[0][0]>1:
        lt=mid+1
        continue
    r=cover[0][1]
    # 判断是否覆盖完，每个左小于当前的r
    for j in range(1,len(cover)):
        if cover[j][0]>r+1:#这里注意是相接的管道！
            break
        else:
            r=max(cover[j][1],r)
    if r<length: lt=mid+1    # 判断r的大小即可
    # 判断是否满足右
    else: rt=mid
print(rt)

切片操作

1
2
3
4
5
6
a="-123"
# end都会少取一位
>>> a[:0:-1] # 步长为-时，start从右边开始数，需要注意下标会取到end+1
'321'
>>> a[:2:] # 步长为正，下标取到end-1
'-1'

字符串转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import re
class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """
        pattern = r"^[\+\-]?\d+"
        result = int(*re.findall(pattern, s.lstrip()))
        min = -2**31 
        max = 2**31 -1
        if result>max:
            return max
        elif result<min:
            return min
        else:
            return result
  • 正则表达式
  • 星号运算符：
    • 完全序列解包
    • 不完全序列解包 取某些连续的值作为元组
    • 字典序列解包**

参考：Python 星号的妙用 —— 灵活的序列解包

中心扩散

我真的是很无语，十几天没刷题之后一切都抛之于脑后了，还写的特别慢，还是要天天温习啊。。。

判断回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x=str(x)
        flag=0
        # 从中间扩散，并且为奇数时不用判断中心的字符
        for i in range(len(x)//2):
            if x[i]!=x[len(x)-i-1]:
                flag=1
                break
        if flag==1:return False
        return True

        '''
        x = str(x)
        return x == ''.join(list(reversed(x)))
        '''
        # return str(x) == str(x)[::-1]

双指针

盛最多的水

本来这道题想直接暴力曲线救国的，结果内存不够……

1
2
3
4
5
6
7
8
import itertools
class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 两个要最远，且最高
        height_with_id=list(enumerate(height))
        matrix=list(itertools.combinations(height_with_id,2))
        volum=[abs(line[0][0]-line[1][0])*min(line[0][1],line[1][1]) for line in matrix]
        return sorted(volum)[-1]

看了大佬解答，原来是要稍微分析下，从两头开始，每次只移动短板。

  • 若向内 移动短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])可能变大，因此下个水槽的面积 可能增大 。
  • 若向内 移动长板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])不变或变小，因此下个水槽的面积 一定变小。
  • 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

如此我们就去掉了两两比较时：移动长版一定比 最好状态>当前状态 差的情况。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l,r,res=0,len(height)-1,0
        while(l!=r):
            if height[l]<height[r]:
                res=max(res,height[l]*(r-l))
                l+=1
            else:
                res=max(res,height[r]*(r-l))
                r-=1
        return res

省赛题目

以下参考：蓝桥杯【第14届省赛】Python B组 76.10分！

A：匹配任何含有2 0 2 3三个字

1
2
3
4
5
6
import re

nums=range(12345678,98765432+1)
patern=r'\d*'.join('2023')
print(sum(not re.search(patern,num_str) for num_str in map(str,nums)))
#85959030

B：硬币兑换

硬币面值、数量相等且呈等差数列coinncoin_n，硬币面值可两两组合，兑换一次一张纸币

求最后能得到的单一面值（纸币加硬币）的某一最大数量

参考：蓝桥：硬币兑换（python）

1.暴力解：【我觉得稍微好理解一点】

我们要找出最后每种面值能存在的最大数量【一个面值coinmaxcoin_{max}】的最大数量max。

因此每种硬币coinncoin_n最多只能和别的组合一次（或者说在全兑换某个面值以达成目的时和别的组合一次，组合完后剩下的只能丢了），因为组合完多的硬币【面值coinncoin_n】和任何面值加起来都不再等于coinmaxcoin_{max}

于是我们就遍历所有可能的硬币组合C(2, 2023)+i，看每种面值的纸币的最大数目，就是这些组合兑换的纸币面值coinnewcoin_{new}的累积值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math
# 创建一个结果集表示:可能存在的所有面值，共2023*2种
res = [i for i in range(0,2023+1)]+[0]*2023

# 遍历范围从1到2023
for i in range(1, 2024):
    # 再次遍历范围从i+1到2023
    for j in range(i, 2024):
        # 将'res'列表中索引为(i+j)的元素增加i, 因为兑换的次数取决于最小的硬币数，所以加i
        if i==j: res[i + j] +=math.floor(i/2)
        else: res[i + j] += i
# 找出'res'列表中的最大值并打印
print(max(res))
# 682425
print(res.index(max(res)))
# 2697

2.归纳推理【大佬好厉害，我老是怕漏最优解】

我们需要使得兑换纸币的数量+硬币本来的数量【这个值我们有】最大。因此想：遍历兑换的纸币面值，寻找最大值。

自然地想到根据面值 2023 的硬币数最多，于是我们先想直接尽可能地兑换面值 2023 的纸币。

这样就会产生两两对半的数列组合：1<>2022、2<>2021……1011<>1021。总数为：r=2023+(1+1011)×10112=513589r=2023+\frac{(1+1011)\times 1011}{2}=513589。

通过这个例子我们发现，在兑换纸币面值一定的情况下，为了兑换同一种纸币并且使兑换的数量最大，我们用来两两组合的硬币加起来都会等于这个值，所以它是由两 个个首尾相接、数量相等的等差数列组成的。这两个数列组合起来的窗口可以在整个[1,2023][1,2023]上移动，注意我们的数列最大值只能取2023、最小值只能取1。

但是我们没有必要往小的方向移动。在探讨出{1,……1011}, {1011+1, 1011+2,……2022}的情况后，窗口再向左移动i位，兑换−coini-coin_i，硬币本来-i。这样就去掉了这些情况！

而往右移动i位，则兑换的数目的等差数列为{2i,……1010+i,1011+i}, {1012+i,……2023}，本来为0，兑换纸币为(1011+3i)×(1012−i)2\frac{(1011+3i) \times (1012-i)}{2}，为一个开口向下的二元函数，也许会在某个位置超过 513589。

1
2
3
4
5
6
ans=0
for i in range(0,1011):
    coins=(1011+3*i)*(1012-i)/2
    ans=max(ans,coins)
print(ans)
# 682425.0

E:保险箱

首先由于右位会影响左位，所以我们只能从右位调起。

以12349->54321作为例子，每一位都有三种情况：

flowchart TD
A[第n位] --> B[进位1235_1]
A[第n位] --> C[退位1233_1]
A[第n位] --> D[不进不退1234_1]
B[进位1235_1] --> E[进位124_21]
B[进位1235_1] --> F[退位122_21]
B[进位1235_1] --> G[不进不退123_49]
C[退位1233_1] --> H[进位124_21]
C[退位1233_1] --> I[退位122_21]
C[退位1233_1] --> J[不进不退123_49]
D[不进不退1234_1] --> i[...]

可以看出，由于每一位i的操作都会诱发前面n-i个的数字变化操作，所以会产生大量重复的节点，但其实每个节点诱发的n-i个数字的变化状态都只有三个（分别由进/不进/不产生）。

因此我们就找到了每一位i在 actions=[−1,1,0]actions=[-1,1,0] 的三种不同状态下，dp的两个状态量：foreheadNumi,totalMoveMiniforeheadNum_i, totalMoveMin_i。注意：对于每个状态只有最小移动步数才是一定的，我们记录每种状态的最小步数下的 foreheadNumiforeheadNum_i 。

初始的三个状态的状态量：

nowNum=num1nowNum=num_1

totalMoveMin1={abs(nowNum−tonum1)if action1==0abs(nowNum−(tonum1+10))if action1==1abs((nowNum+10)−tonum1)if action1==−1totalMoveMin_1=\begin{cases} abs(nowNum-tonum_1) & \text{if } action_1==0\\\\ abs(nowNum-(tonum_1+10)) & \text{if } action_1==1\\\\ abs((nowNum+10)-tonum_1) & \text{if } action_1==-1 \end{cases}

简化为

for action1action_1 in actionsactions:

totalMoveMin1=abs(nowNum−tonum1−10∗action1)totalMoveMin_1=abs(nowNum-tonum_1-10*action_1)

foreheadNum1=floor(num/10)−action1foreheadNum_1= floor(num/ 10) - action_1

而状态转移:

首先找到i+1位的数字，三种情况：

分别再计算actioniaction_i的三种情况，并对于这三种情况取最小值记录。

nowNum=[[foreheadNumi%10 for actioni+1 in actions] for actioni in actions]nowNum=[[foreheadNum_i\%10 \text{ for } action_{i+1} \text{ in } actions]\\\\ \text{ for } action_{i} \text{ in } actions]

遍历

totalMoveMini+1=min(abs(nowNum−tonumi+1−10∗actioni+1)+totalMoveMini)totalMoveMin_{i+1}=min(abs(nowNum-tonum_{i+1}-10*action_{i+1})+totalMoveMin_i)

if theActionitheAction_i with state theTotalMoveMinitheTotalMoveMin_i, theForeheadNumitheForeheadNum_i made totalMove minimal

foreheadNumi+1=floor(theForeheadNumi/10)+actioni+1foreheadNum_{i+1}= floor(theForeheadNum_i/ 10) + action_{i+1}

有问题的代码：

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
import math
n=int(input())
# 一定要保留前置0
x=int("1"+input())
y=int("1"+input())
# 退位/正常/进位
actions=[-1,0,1]
fhNum=[x//10 + action1 for action1 in actions]
minMove=[abs(x%10-y%10 - action1*10) for action1 in actions]
y=y//10
for i in range(1,n):
    thisTonum=y%10
    y=y//10
    thisMinMove=[math.inf for action in actions]
    thisFhNum=[math.inf for action in actions]
    for actionj in actions:
        nowNum=fhNum[actionj+1]%10
        for actioni in actions:
            thisMove=abs(nowNum-thisTonum-actioni*10)+minMove[actionj+1]
            if thisMinMove[actioni+1]>thisMove:
                thisMinMove[actioni+1]=thisMove
                thisFhNum[actioni+1]=fhNum[actionj+1]//10 + actioni
    minMove=thisMinMove
    fhNum=thisFhNum
print(int(min(minMove)))

然后就只有65%通过，剩下的都报：段错误，不知道错在哪。。。我自己生成了100-1000的没报错。。。以后写dp老老实实用数组写了。

下面是大佬的代码(保险箱-lanqiao9003555425的代码 )。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import os
import sys

n=eval(input())
x=list(map(int,input()))
y=list(map(int,input()))
dp=[[0]*3 for _ in range(n)]
dp[n-1][0]=abs(y[-1]-x[-1])
dp[n-1][1]=10-x[-1]+y[-1]  # 进位
dp[n-1][2]=10-y[-1]+x[-1]  # 退位
for i in range(n-2,-1,-1):
    dp[i][0]=min(dp[i+1][0]+abs(y[i]-x[i]),dp[i+1][1]+abs(y[i]-x[i]-1),dp[i+1][2]+abs(y[i]-x[i]+1))
    dp[i][1]=min(dp[i+1][0]+10-x[i]+y[i],dp[i+1][1]+9-x[i]+y[i],dp[i+1][2]+11-x[i]+y[i])
    dp[i][2]=min(dp[i+1][0]+10-y[i]+x[i],dp[i+1][1]+11-y[i]+x[i],dp[i+1][2]+9-y[i]+x[i])
print(min(dp[0][0],dp[0][1],dp[0][2]))

比我简短多了，我晕倒了。

寻找整数

一元同余线性方程组的性质：

如果 x^ 为 x 的最小整数解，则通解为 x^+k⋅lcm(m1​,m2​,…mn​) （即相差k倍模数的公倍数）。

则满足前n个条件的解空间为(note: 满足前i+1个条件的解(包括最小解)，一定包含于满足i个的解空间中)：

  • x_fit1=[1,3,5,7,9,11,…]
  • x_fit2=[5,11,17,…]
  • x_fit3=[5,17,29,…]
1
2
3
4
5
6
7
8
9
10
11
12
from math import gcd  
def lcm(a,b):
  return a*b//gcd(a,b) #最小公倍数
 
a=[0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46]
step=1 # 初始步长为1
x=0
for i in range(2,50):
  while x%i!=a[i]:
    x+=stap # 找到满足mod得到a中第i个余数的最小整数解
  stap=lcm(stap,i) # 用前一个的最小公倍数作为步长，在前一个的解空间中寻找最小解
print(x)