笔试时间：2023年5月26日 暑期实习

第一题

题目：多多的骨牌

多多最近在玩一种骨牌游戏，在一条直线上n个骨牌，骨牌只有高度没有宽度，第i个骨牌在位置xi，其高度为hi，多多可以任意选择一些骨牌，将其按顺序向左或者向右放倒，向左放倒之后会占竭[xi-hi,xi]对，向右放倒后会占据[xi,xi+hi]。要求放倒的骨牌不能触碰到其他之前已经放倒的骨牌或者站立的骨牌。问多多最多可以放倒多少个骨牌。

输入描述

第一行输入一个数字n（1<=n<=10^5)，去示有n个号牌。

接下来n行，每行输入两个数字xi和hi（0<=xi<=10^9,1<=hi<=10^9),表示第i个骨牌的位置和高度。

输入保证xi递增且不会出现相等的情况。

输出描述

输出一个整数ans，表示最多能放倒的骨牌数。

示例输入

3

1 1

2 1

3 1

示例输出

2

先将第一个骨牌往左倒。再将第三个骨牌往右倒。第二个骨牌无论往左还是往右，都会触碰到其他骨牌。

参考题解

每一个骨牌都有3种可能，左倒、右倒、不倒。以此枚举即可。

当前骨牌i向左边倒的时候，判断下一个骨牌next是否可以向左倒，也就是 next-h > xi;否则只能向右倒。

当前骨牌不倒的时候，判断下一个骨牌可以向左倒或者向右倒

当前骨牌向右倒的时候，判断下一个骨牌可能的倒向。

每一个骨牌如果可以向左边倒的时候，优先往左边倒。

Python：

import bisect
from functools import lru_cache

n = int(input())
points, heights = [0 for _ in range(n)],[0 for _ in range(n)]
for i in range(n):
    x, h = map(int, input().split(" "))
    points[i], heights[i] = x, h

@lru_cache(maxsize=None)
def dfs(i,j):
    if i >= n: return 0
    if i == n - 1: return 1
    #可以不选择当前这一个， 那么下一个可以的区间就是大于等于x的
    if points[i+1] - heights[i+1] >= points[i]: cur = dfs(i+1,0)
    else:cur = dfs(i+1,1)
    # j表示可以往左边倒
    if j == 0:
        if points[i+1]-heights[i+1] > points[i]: return max(dfs(i+1,0)+1, cur)
        else:return max(dfs(i+1,1)+1,cur)
    else:
        #往右边倒，找到下一个 x大于等于 当前右边界
        right =  points[i]+heights[i]
        x = bisect.bisect_right(points, right)
        if x == n: return 0
        if points[x]-heights[x] > right: return max(cur, dfs(x,0)+1)
        else: return max(cur, dfs(x,1)+1)

print(dfs(0, 0))

第二题

题目：多多的字符串研究

多多最近痴迷于研究字符出，对于一个字符串s，多多想知道它所有不同的子串中，第k小的是什么。

输入描述

第一行包含一个字符串s。

第二行包含一个整数K。

s的长度不超过100，1<=k<=10000.

输出描述

输出第k小的字串，如果第k小的子串不存在，输出NOANSWER

示例输入

aab

4

示例输出

ab

字符串aab的子串从小到大依次为aaaaabb

参考题解

s的长度只有100，因此，枚举所有s的子串即可。

Python