2018.10.9 好未来笔试

发表于 |

总结：共3道算法题，全部AC，3道题目都很麻烦，但仿佛测试数据强度很低，我所担心的溢出什么的全都没发生。

1. 细胞分裂（AC）

小明是一个生物学家，最近他在做一份关于细胞研究的工作。他进行了若干次实验
第一次实验开始，试管里有1个细胞。每一秒1个细胞会分裂成k个细胞，并且会由于某些未知原因，还会额外产生b个细胞。即，如果在某一秒的开始试管内有x个细胞，那么在这一秒的结束时刻，试管中就会有kx + b个细胞。
实验结果表示，在n秒结束的那一刻，试管中一共有z个细胞。
第二次实验时，小明给试管中放入t个细胞，他想知道至少经过多少秒后，试管中可以至少有z个细胞(按照第一次试验细胞分裂的规律)。

输入描述：
一行4个整数 k, b, n, t，用空格隔开，含义如题所述
满足 1 <= k, n, b, t <= 10^6.

输出描述：
一个整数，代表最少需要的时间

样例输入：
1 1 1 1

样例输出：
1

样例输入：
2 2 3 3

样例输出：
3

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

k,b,n,t = read()
z = 1 # 计算z的数量
for i in range(n):
    z = k*z + b

time = 0 # 模拟过程
while t < z:
    t = k*t + b
    time += 1
print(time)

2. 首尾相同的数字（AC）

小明非常喜欢和区间有关的问题。
这次他有一对数字 l,r。小明想找出有多少个数字x (l <= x <= r)， 满足x的十进制表示的第一位数字和最后一位数字相等。x不含前导0，除了数字0本身。
比如 989， 2， 1001，就是满足条件的数字，但是 49, 10, 972都不满足条件。
请你帮小明计算出结果

输入描述：
一行两个数字l , r，用空格隔开
满足 1 <= l <= r <= 10 ^ 18

输出描述：
一个整数，满足条件的数字个数

样例输入：
1 10

样例输出：
9

样例输入：
88 100

样例输出：
2

思路分析：
我是用helper(num)函数来计算1,num中有多少个满足条件的数
然后 helper(r) - helper(l) + int(l is 满足条件)得出结果
我们首先发现这样一个规律：
1位数： 9个
2位数： 9个
3位数： 90个 （固定住左右两边，中间有0-9，共10种取法）
4位数： 900个 （中间有00-99，共100种取法）
依次类推…
那么假设对于一个8位数 num = 32344325
我们可以先计算小于8位数时的满足条件的数的总数，即res += 9+9+90+900+...
然后根据num的首位val，这里val = 3，从1开始向上分析直至val-1，这一段是没有任何数字丢失的，我们完全可以计算。中间有6位数字在变动。所以有10^6种取法。res += (val-1) * 10^6
最后判断首位为3的情况，将首位固定为3，能有30000003 - 32344313是确保能取到的
所以 res += int(中间6位)， 最后一个32344323能否取到取决于本身最后一位是否大于3，这里大于所以最后 res += 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
26
27
28
29
30
31
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

# 用来存储发现的规律
rec = [1,1,10]
for i in range(18): rec.append(rec[-1]*10)

l,r = read()

def helper(num):
    # 3位数以下很简单，直接处理即可
    if num < 10: return num
    if num < 100: return 9 + num // 11
    l = len(str(num))
    res = 0
    for i in range(l-1):
        res += 9 * rec[i]
    val = int(str(num)[0])
    for i in range(val - 1):
        res += rec[l-1]
    val1 = int(str(num)[1:-1])
    res += val1
    if int(str(num)[-1]) >= val: res += 1
    return res

val1 = helper(l)
val2 = helper(r)
val = val2 - val1
s = str(l)
if s[0] == s[-1]: val += 1
print(val)

3. 序列递增（AC）

小明又找到了一个序列，包含n个整数。
小明希望你在这个序列中找出一个最长的子串(连续的)，可以改变其中最多一个整数，使这个子串是严格递增的。你需要输出这个最长字段的长度。

输入描述：
第一行一个整数n,表示序列中数字的个数
第二行n个整数x[i]，用空格分开

输出描述：
一个整数，满足条件的数字个数

样例输入：
2
3 6

样例输出：
2

样例输入：
3
7 1 9

样例输出：
3

思路分析：
首先我将所有上升的序列段全部分别保存了下来，两个两个的分析，看两个是否能通过改变第一个序列的结尾或者改变第二个序列的开头来进行合并

特殊case是第二个序列长度为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
26
27
28
29
30
31
32
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

n = int(input())
a = read()
if n <= 2: print(n)
else:
    p = []
    rec = [a[0]]
    for i in range(1, n):
        if a[i] > a[i-1]:
            rec.append(a[i])
        else:
            p.append(rec)
            rec = [a[i]]
    if rec: p.append(rec)

    res = 0
    for i in range(len(p)-1):
        if len(p[i+1]) == 1 and i+2 < len(p):
            if p[i][-1] < p[i+2][0] - 1:
                res = max(res, len(p[i]) + 1 + len(p[i+2]))

        if len(p[i]) == 1:
            res = max(res, 1 + len(p[i+1]))
        else:
            if p[i][-2] < p[i+1][0] - 1 or (len(p[i+1]) > 1 and p[i][-1] < p[i+1][1]-1):
                res = max(res, len(p[i]) + len(p[i+1]))

    res = max(res, len(p[-1]) + 1)
    if res > n: print(n)
    else: print(res)