Algorithm_practice1

practice 1

1
2
3
4
5
6
7
8

大洋国有两种面值的纸币，面值分别是 m 和 n,m n 互质,现在问你如果有无限多张 m 和 n，最大的不能组成的金额是多少
例如说 m n 分别是 4 和 7 时，最大不能组成的金额是 17
18=1*4+2*7
19=3*4+1*7
20=5*4+0*7
21=0*4+3*7
...

这个题目翻译过来就可以理解为

1
mx+ny=k，给出 m n，求方程不存在非负整数解时 k 的最大值

现在乍一看有点像exgcd,因为exgcd是 mx+ny=gcd(m,n)一定存在一组解x,y。但是显然和个题目有点不符合。看题目未果直接上一串测试代码进行测试看能否从结果中得到规律

下面是测试代码

1
2
3
4
5
6
7
8
9
10
11
12
def k_max(m,n):
    a_list = list()
    for x in range(10):
        for y in range(10):
            k = m*x+n*y
            a_list.append(k)
    ans = sorted(a_list)
    print(ans)
    ans = ans [:-40]
    for i in range(len(ans)-1,-1,-1):
        if ans[i]-1 not in ans:
            return ans[i]-1

能够得到一下的结果数据

m n value k m*i n*j
2 3 2 1 2*1 3*0
2 5 4 3 2*2 5*0
3 5 8 7 3*1 5*1
4 7 18 17 4*1 7*2
5 7 24 23 5*2 7*2
5 9 32 31 5*1 9*3

上面表格中的value值就是k+1,即最大不能组成金额后的最小值。这里因为题目可知，达到最大不能组成金额后，任意的金额都可以有mx+ny来表示。

看表格中的数据如果只看m×i 和 n×j 看不出来什么，但是如果看m,n,k这三个数值，如果你有绝世的数感,你会发现这三个数满足这个规律k = mn -m-n。唔这个真的好像RSA中的phi值的计算虽然但是不知道有无关系。然后经过查阅资料确实在数论中存在这个公式并通过证明(贝祖定理，就当积累一下这个公式)

问了一下deepseek下面是推到过程，根据方程 k=mn−m−nk=mn−m−n，我们可以通过以下步骤进行证明和分析：

关键变形与解的构造

  1. 方程变形
    原方程两边加1：

    k+1=mn−m−n+1=(m−1)(n−1)k+1=mn−m−n+1=(m−1)(n−1)

    这表明 k+1*k*+1 必须能分解为两个整数 (m−1)(*m*−1) 和 (n−1)(*n*−1) 的乘积913。

  2. 解的表示
    若 k+1=p⋅qk+1=p⋅q（其中 p,qp,q 为整数），则解为：

    m=p+1,n=q+1m=p+1,n=q+1

    例如：

    • 当 k=5k=5 时，k+1=6=2×3k+1=6=2×3，则 m=3,n=4m=3,n=4 或 m=4,n=3m=4,n=3。

解的讨论

  1. 整数解的存在性
    • 当 k+1k+1 为 合数 时，方程有多个整数解（对应不同的因数分解方式）。
    • 当 k+1k+1 为 质数 时，方程仅有有限解（如 m=2,n=k+2m=2,n=k+2 或 m=k+2,n=2m=k+2,n=2）。
    • 当 k+1k+1 为 负数 时，解可能涉及负整数。例如，若 k=−3k=−3，则 k+1=−2=(−1)×2k+1=−2=(−1)×2，解得 m=0,n=3m=0,n=3 或 m=3,n=0m=3,n=0。
  2. 解的对称性
    方程具有对称性：若 (m,n)(m,n) 是解，则 (n,m)(n,m) 也是解。例如，(3,4)(3,4) 和 (4,3)(4,3) 均为 k=5k=5 的解。

与数论定理的联系

  1. 贝祖定理（Bézout’s Identity）的类比
    原方程 mn−m−n=kmn−m−n=k 可改写为：

    m(n−1)−n=km(n−1)−n=k

    这表明 mm 和 nn 需满足特定线性组合关系。若 kk 是 gcd⁡(m,n)gcd(m,n) 的倍数，则方程有解13。

  2. 最大公约数的应用
    设 d=gcd⁡(m,n)d=gcd(m,n)，则方程可表示为：

    d(md⋅nd−md−nd)=kd(d**m⋅d**n−d**m−d**n)=k

    当 dd 能整除 kk 时，方程可能存在整数解。

所最后的exp代码：

1
2
def k_max(m,n):
    return m*n-m-n

这里还有jack_gdn师傅的一个思路

1
2
3
首先来说，28 是一个肯定能拼出来的数，而且有（至少）两种拼法，7*4+0*7 或者 0*4+4*7。那么如果我想在这个数字上加1或者减1怎么弄？观察发现2*4-1*7=1，3*7-5*4=1，也就是说如果我想让这个数字减去1，就可以放进去一个7拿走两个4，或者放进去五个4拿走三个7。这几个系数都可以在 O(m) 和 O(n) 的时间内遍历出来，所以对于一个数，如果这个数既不能拿走两个4，也不能拿走三个7，那么比它小的数中肯定有不能用 4 和 7 组成的数字。那么既不能拿走两个4，又不能拿走三个7，而且这个数尽可能大，那么应该是多少呢？那就是刚好有一个4和两个7，也就是18，那么比 18 小 1 的 17 就刚好是最大的不能用 4 和 7 组合的数。推广一下就是，刚好不能用 m 和 n 组成的最大数 k 可以表示为 (x-1)n+(y-1)m-1，其中 x, y 分别为方程
ay-xn-1, bx-my=1 的最小非负整数解

6135. 奶牛体检 | 原题链接

题目简要描述

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
输入有3行，第一行是一个整数 n，第二行和第三个各自有 n 个用空格分割的整数，第二行表示原序列，第三行表示目标序列。现在可以执行一次操作，就是在原序列中选出 l 和 r 两个位置，然后将这个区间内的元素倒过来，这时候得到一个新序列，新序列和目标序列中可能会有对应位置的元素相等。(l,r) 被称为使新序列与目标序列中有 n 个元素对应位置相等的方法，现在需要你输出 n+1 行，第 i 行表示使新序列与目标序列中有 i-1个元素对应位置相等的方法数量。l 和 r 可以相等，
输入样例1
3
1 3 2
3 2 1
输出样例1：
3
3
0
0
当 (l,r) 为 (1,1) (2,2) (3,3) 时，新序列中不会与目标序列对应位置元素相等，(1,2) (2,3) (1,3) 均可以有一个对应位置元素相等，没有方法能够使新序列与目标序列中有 2 个或 3 个对应位置元素相等。

输入样例2：
3
1 2 3
1 2 3
输出样例2：
0
3
0
3

输入样例3：
7
1 3 2 2 1 3 2
3 2 2 1 2 3 1
输出样例3：
0
6
14
6
2
0
0
0

1<=l<=r<=n
数据范围1≤N≤7500

再把描述优化一下就是说要写出第i行，i-1个元素，两个序列a[i]==b[i] 的方法的个数。

解题过程

很容易想到进行枚举，我最开始是这样的想，先把输入的数据转换成[0]+list的形式，按照正常的顺序从左向右以此遍历l,r然后进行顺序的转换，最后把得到的顺序转换到一个新的空列表里，最后再用lambda函数对应列元素相减看元素0的个数，但是因为你存到空列表这个过程中，实际上已经存了个 $$o(n^2)$$的时间复杂度的程序，然后lambda函数又是一个$$o(n)$$的时间复杂度的程序，最后下来是个$$o(n^3)$$的一个程序。因为这个数据范围的因素，$$o(n^3)$$程序应该很容易不通过，因此要想着如何进行优化这个算法。但是冥思苦想没有思路，不知道从哪里下手，中间Jack_GDN师傅给了个提示就是降低时间复杂度的关键是减少重复和不必要操作的次数 这是个比较重要的点。我们只需针对重复的步骤进行删减冗余就可以优化代码。在整个过程中会发现l=2,r=3时(2,3)的位置交换一次顺序，当l=1,r=4时(2,3)又重复操作交换了一次顺序，当l=1,r=5时也是同理(这里需要体会一下重复的含义)。

这样的话我们遍历的时候就可以不用从头到尾遍历，而是根据中间向两边扩展的一种思路去写就可以避免重复操作的问题。当然这里需要考虑奇数和偶数分开讨论。

对于如何计数，我们可以先考虑一个问题，就是题目是要找新序列和目标序列中a[i]=b[i]的不同个数的方法数，那么就不妨直接在原序列上进行一个修改。先统计出原序列的 a[i]=b[i] 的个数，然后再通过从中间向两边不断扩散得到的序列进行一个叠加(这里是学习了一下wp的思路)

其中：a[l]=b[l] ，a[r]=b[r]为减一，a[l]=b[r],a[r]=b[l]为加一。于是就有下面的代码

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
from collections import defaultdict
n = int(input())
origin = [0]+list(map(int,input().split())) 
target = [0]+list(map(int,input().split()))

ans = defaultdict(int) #这个是默认字典，里面带int类型是便于计数，默认ans[i]=0

count = 0
for i in range(1,n+1):
    if origin[i] == target[i]:
        count +=1

for i in range(1,n+1):
    #奇数的情况
    l,r = i,i  #从中间的同一个点向两侧
    sum_odd = count
    while l >=1 and r <= n:
        sum_odd +=  (origin[l]==target[r])+(origin[r]==target[l])-(origin[l]==target[l])-(origin[r]==target[r])
        ans[sum_odd] += 1 #记录同一种的情况的方法数
        r += 1
        l -= 1
    
    #偶数的情况
    l,r = i-1,i 
    sum_even = count
    while l >=1 and r <= n:
        sum_even +=  (origin[l]==target[r])+(origin[r]==target[l])-(origin[l]==target[l])-(origin[r]==target[r])
        ans[sum_even] += 1 #记录同一种的情况的方法数
        r+=1
        l -=1

for i in range(n+1):
    print(ans[i])

最大正方形原题链接

题目描述:

1
2
3
4
5
6
7
8
在一个 n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。
输入
4 4  #n和m
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出： 2

这个题目最开始是想着练习二维前缀和的，但是出乎意料的不太行。因为最开始根据这个二维矩阵能把每个对应位置的值给算出来，然后根据这个值本来想着是通过判断是否为平方数进行一个计数，显然这里会忽略掉不是正方形但是前缀和也是平方数的情况，这样的话就会误算。因此单纯从前缀和去判断最大正方形的边长是走不通的。(这里还傻傻的思考了好久如何解决，试了好几种方法，比如说拿i,j的最大值当成可能存在的最大边然后进行倒着遍历求边长，当然最后还是出现了上面的问题。)

最后实在没辙，看了一眼wp,竟然是用了动态规划,Orz! 不太会，只好先硬着头皮把这道题所涉及的动态规划的思路理一下。

解题思路

通过确定一个极大的正方形，向上，向左，左上进行一个逐步寻找其解的合理性的结果。具体的一个推到过程就直接粘了wp中的过程了

image

这里需要注意下，就是这里的状态方程直接套用数字逻辑中触发器比较好理解，就是找次态和现态之间的关系。
$$
次态 = x的最小值+所处极大值点的值
$$

1
2
3
4
5
6
7
8
9
10
11
import sys 
n, m = map(int, sys.stdin.readline().strip().split())  
rectangle = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
target = [rectangle[0]] + [[i[0]] + [0] * (m - 1) for i in rectangle[1:]]
ans = 0
for i in range(1,n):
    for j in range(1,m):
        if rectangle[i][j]:
            target[i][j] = rectangle[i][j] + min(target[i-1][j],target[i][j-1],target[i-1][j-1])
            ans = max(ans,target[i][j])
print(ans)

哞叫时间II

emm这个题纯属是千呼万唤始出来的感觉。

题目描述

1
2
3
4
5
6
7
8
9
输入n,和一个n列的整数序列，要找到这个整数序列中存在abb形式的个数
数据范围
1≤N≤10^6,
1≤ai≤N
输入样例：
6
1 2 3 4 4 4
输出样例：
3

这个题目最简单的思路是直接三层循环遍历去找，但是根据数据范围来说$$o(n^3)$$的时间复杂度有点高，需要降到$$o(nlogn)$$或者是$$o(n)$$的形式才可以。因此需要进行优化，这就需要看操作重复的部分了。(这个感觉比较难理解)，就是从以下的样例来看

1
2
7
1 2 2 4 3 4 4

这里要是正着数的的话我们可能会遇到遍历过第一个2之后再遍历一遍2的情况，这步属于冗余部分，因此为了避免这个我们要考虑从后遍历找到两个一样的即可。但是这里还会出现一个情况就是我们需要考虑前面有与自身重复和其他遍历的数例如上面样例中的2这种重复两种因素。我们肯定是要减掉重复的数据。

这里可以分两步步走: 1. 就是先找不与自身重复的数的种类，这里我们可以用列表或者字典去存储截止到当前数目不同的数字的个数。这里的个数可以直接用集合的长度去表示

2.对于与自身重复的种类的情况来说，因为采用了集合去计算不同数字的个数，那么直接等价为当倒数第二个数前还有与自己重复的数，与自己重复数的最多只有一个，直接减去即可。

对于整个框架来说，我们还需要统计出每个数字的个数用来判断遍历到倒数第二个a之前,前面是否还有重复的a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import Counter,defaultdict
n = int(input())
m = tuple(map(int,input().strip().split()))
dif = set()
var = dict()
for i in range(n):  #计算截止到当前为止，不同的数的个数
    var[i] = len(dif)
    dif.add(m[i])
cnt1 = Counter(m)   #统计出每个数的个数
cnt = defaultdict(int)  #用来倒着统计
ans = 0
for j in range(n-1,-1,-1): 
    cnt[m[j]] += 1
    if cnt[m[j]] ==2:
        lenghth = var[j]
        if cnt1[m[j]] > 2:
            lenghth -= 1   #减去重复的数
        ans += lenghth
print(ans)