2021蓝桥杯真题 小蓝卡片 数学+二分查找+前缀和优化

无聊时刷到了这题，看到网上都是暴力解法，于是想摸个比较优化的解法

题目描述

小蓝有很多数字卡片，每张卡片上都是数字0到9。小蓝准备用这些卡片来拼一些数，

他想从1开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从1拼到多少。 例如，当小蓝有 30张卡片，其中0到9各3张，

则小蓝可以拼出1到 10，但是拼11时卡片1已经只有一张了，不够拼出11。

现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少？

这是道填空题，其实不需要过多的优化，但还是想写写hhh🍵

思路

通过观察题干，emmmm，一大堆没用的信息在干扰我的眼睛！！好在给出了案例，小蓝抽到11就拼不出来了，这说明小蓝拼的数字一定是连续的，且受到卡牌数量限制。而且，卡牌是从1开始拼，那么率先消耗完的一定是卡片1！

这个信息还是比较重要的，这说明连续的中断点要么：

1️⃣ 卡在1上，例如2101时用完，没办法拼出下一张

2️⃣ 卡在$[n,n+9]$上，其中$n$是最后一张用到的$1$牌，如:2021,我们只能拼到2030了。

综合以上信息，我们可以想到：

• 找到最后出现1的位置
• 从1开始遍历连续的整数值，直到一种卡片缺失

这两种都是比较常见的解法，简单写一下：

def func1(n):
    cards=[n]*10
    res=0
    while True:
        res+=1
        t=res
        while t:
            cards[t%10]-=1
            if cards[t%10]<=0:
                return res
            t//=10

print(func1(2021))
# 3181
1
2
3
4
5
6
7
8
9
10
11
12
13
14

def func1(n):
    cnt=n
    i=1
    while True:
        t=i
        while t:
            t,b=divmod(t,10)
            if b==1:
                cnt-=1
        # 需要注意，可能会有拼不成的情况
        if cnt==0:
            return i
        if cnt<0:
            return i-1
        i+=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

那我们能不能直接递推1的值，而不是无脑的遍历呢？

状态1️⃣:当1为末尾元素，且末尾元素前没有1,例如：2321，那么下次的状态则会保留末尾的1，然后在十位上进位：2331。

状态2️⃣: 末尾元素随意，但前方元素存在1，例如，2310的下一个状态是2311。

进位情况

• 当进位时，前方元素存在1或者将要生成1，那么进位情况是正常的十进制进位。(9->0)
• 当前方元素不存在1，那么末尾元素将从9->1

以上，我们发现需要通过两个值来控制整个状态，分别是isOne前方是否存在1和carryBit是否进位来模拟以上的流程。

我们用isOne记录累计1的数量，当发生进位时，该元素数量减一，而当生成1时，该元素数量加一。

 def CarryBit(dig,isOne):
        idx=-2
        while 1:
            if idx * -1 > len(dig):
                dig = [1] + dig[:-1] + [0]
                isOne += 1
                break
            else:
                v = dig[idx] + 1
                if v != 10:
                    dig[idx]=v
                    if v == 1:
                        isOne += 1
                    if v == 2:
                        isOne -= 1
                    break
                dig[idx] = 0
                idx -= 1
        return dig,isOne
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这个方法用来进位，同时控制isOne的变化。

整个代码如下：

def createDig(n):

    dig,cnt=[1],n
    isOne=1
    def CarryBit(dig,isOne):
        idx=-2
        while 1:
            if idx * -1 > len(dig):
                dig = [1] + dig[:-1] + [0]
                isOne += 1
                break
            else:
                v = dig[idx] + 1
                if v != 10:
                    dig[idx]=v
                    if v == 1:
                        isOne += 1
                    if v == 2:
                        isOne -= 1
                    break
                dig[idx] = 0
                idx -= 1
        return dig,isOne
    i=1
    while i<cnt:
        if isOne==0:
            # 进位应当是十位加一
            # 而当十位是一的时候，应当从零开始
            dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=0
            else:
                dig[-1]=1
            i+=1
        else:
            tem=dig[-1]+1
            if tem==1:
                i+=1
            if tem==10:
                dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=tem%10
                i+=isOne
            else:
                dig[-1]=1
                i+=1

    return int("".join(map(lambda x:str(x),dig)))
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

该方法可以用来直接生成任意正整数区间内含有1的元素，在时间复杂度上比原先的$O(B\ast n)$会快些，原因在于不需要做除法一位一位提取元素。

进一步分析

不难发现，这两种方法的时间复杂度都是$O(n)$级别的，那么有没有办法可以对其进行优化呢？

根据上文给的条件，我们只需要递推卡牌1的数量即可。

• 在个位数上，能选择的卡牌有1，表达为$C_1^1=1$
• 在十位上，递推表达为：$C_{10}^1$（十位固定为一，个位数能选择的)+$C_9^1$(个位固定为一，十位不能选0)$+1=20$
• 在百位上，递推表达为:$(C_{10}^1{)}^2+(C_9^1{C}_{10}^1)\ast 2+20=300$
• 在千位上，递推表达为：$(C_{10}^1{)}^3+C_9^1(C_{10}^1{)}^2\ast 3+300=4800$

于是我们可以进一步优化初始条件：

构建前缀和数组，获得初始进入条件。

def initDig(n,dig=10):
    weight=[int(10**(i-1)+(9*10**(i-2))*(i-1)) for i in range(1,dig)]
    accumulate=[weight[0]]
    
    for i in range(1,len(weight)):
        accumulate.append(weight[i]+accumulate[-1])
    # 检查在哪个范围
    l,r=0,len(accumulate)
    while l<=r:
        mid=(r-l)//2+l
        if accumulate[mid]>=n:
            r=mid-1
        else:
            l=mid+1
            
    remain=n-accumulate[l-1]
    if l==0:
        return [1],0
    return [1]+[0]*l,remain
print(initDig(2021))
# ([1, 0, 0, 0], 1721)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

可以发现，2021的初始进入解可以被归到1000。

值得注意的是，100-200是一个模式，200-999是另一个模式，同理可以推到任一位上。

• 100-200：$C_{10}^1\ast 2+C_9^1\ast 2+(C_{10}^1{)}^2$
• 200-999: $(C_8^1{C}_{10}^1)\ast 2$
• 1000-2000: $(C_{10}^1{)}^2+(C_9^1{C}_{10}^1)\ast 2+(C_{10}^1{)}^3$
• 2000-9999:$(C_8^1{C}_{10}^1{C}_{10}^1)\ast 3$

可以通过计算获得更加精确的逼近值：
$$2021-1-19-280-(300+1000)=421$$
此时进入到2000-2999的区间，余量$4800>421>300$，应该是在千位进行变化。
$$421mod(300)=1,121$$
也就是进入到3000-3999的区间，还剩下121，$300>121>20$，可以按照阶段进一步划分：
$$121-20=101$$
此时进入区间3100-31999,该区间为特殊区间，区间大小为:$100+20=120>91$，所以最终值应该落入此区间。该特殊区间又可进一步递归：

110-119是一个模式，大小为10+10+1=21，其他模式大小为:10+1=11，于是：
$$\begin{gathered} (101-11-21)=69 \\ 59mod(11)=6,3 \end{gathered}$$

所以最终的结果为：$3119+60=3179$,$3179+3-1=3181$

整个过程模拟较为复杂，但确实可以通过数学方法将时间复杂度降低到$O(1)$，下面我通过取巧 偷懒 的方式进行优化:

def initDig(n):
    weight=[1,19] # 个位十位
    weight+=[120]+[20 for i in range(1,9)] # 百位
    weight+=[1300]+[300 for i in range(1,9)] # 千位
    hashmap=[1,10,200]+[100*i+200 for i in range(1,9)]+[2000]+[1000*i+2000 for i in range(1,9)]
    accumulate=[weight[0]]
    print(weight)
    print(hashmap)
1
2
3
4
5
6
7
8

按照小模式构建分箱，结果如下：

[1, 19, 120, 20, 20, 20, 20, 20, 20, 20, 20, 1300, 300, 300, 300, 300, 300, 300, 300, 300]
[1, 10, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000]
1
2

接着，通过二分法寻找分箱结果：

 for i in range(1,len(weight)):
        accumulate.append(weight[i]+accumulate[-1])
    # 检查在哪个范围
    l,r=0,len(accumulate)
    while l<=r:
        mid=(r-l)//2+l
        if accumulate[mid]>=n:
            r=mid-1
        else:
            l=mid+1
    remain=n-accumulate[l-1]
    if l==0:
        return [1],0
    return [int(i) for i in str(hashmap[l-1])],remain
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以看到可能的结果为：

print(initDig(2021))

# ([3, 0, 0, 0], 121)
1
2
3

我们将步骤从最开始的3181*A步缩减到2021*B+O(log5)步，再缩减到了121*B+4+O(log20)步，其中B表示进位情况，A表示每一位遍历，满足关系B<。当然可以更进一步分箱的缩减他的复杂度，或是通过更细致的数学模拟方法精确计算，最终达到$O(1)$

def initDig(n):
    weight=[1,19] # 个位十位
    weight+=[120]+[20 for i in range(1,9)] # 百位
    weight+=[1300]+[300 for i in range(1,9)] # 千位
    hashmap=[1,10,200]+[100*i+200 for i in range(1,9)]+[2000]+[1000*i+2000 for i in range(1,9)]
    # weight=[int(10**(i-1)+(9*10**(i-2))*(i-1)) for i in range(1,dig)]
    accumulate=[weight[0]]
    for i in range(1,len(weight)):
        accumulate.append(weight[i]+accumulate[-1])
    # 检查在哪个范围
    l,r=0,len(accumulate)
    while l<=r:
        mid=(r-l)//2+l
        if accumulate[mid]>=n:
            r=mid-1
        else:
            l=mid+1
    remain=n-accumulate[l-1]
    if l==0:
        return [1],0
    return [int(i) for i in str(hashmap[l-1])],remain
print(initDig(2021))




def createDig(n):

    dig,cnt=initDig(n)
    isOne=0
    for i in dig:
        if i==1:
            isOne+=1
    def CarryBit(dig,isOne):
        idx=-2
        while 1:
            if idx * -1 > len(dig):
                dig = [1] + dig[:-1] + [0]
                isOne += 1
                break
            else:
                v = dig[idx] + 1
                if v != 10:
                    dig[idx]=v
                    if v == 1:
                        isOne += 1
                    if v == 2:
                        isOne -= 1
                    break
                dig[idx] = 0
                idx -= 1
        return dig,isOne
    i=1
    while i<cnt:
        if isOne==0:
            # 进位应当是十位加一
            # 而当十位是一的时候，应当从零开始
            dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=0
            else:
                dig[-1]=1
            i+=1
        else:
            tem=dig[-1]+1
            if tem==1:
                i+=1
            if tem==10:
                dig,isOne=CarryBit(dig,isOne)
            if isOne:
                dig[-1]=tem%10
                i+=isOne
            else:
                dig[-1]=1
                i+=1

    return int("".join(map(lambda x:str(x),dig)))



print(createDig(2021))
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81