简述题目：一、n组数据。给定字符串S、T，可对S进行任意字符修改，或删除末位字符。求操作多少次可以使得S为T的前缀。样例：aba 变 abb前缀，改或删最后一个字符都可，1次操作。abcd变efg，只能全删，4次操作。思路：能改则不删，只有S大于T才用删。分为S小于T直接求前len(S)个不同字符数，S大于T求 前len(T)不同字符数加上len(S)-len(T)二、一种糖果a个，另一种b个。分给n个人（a+b>n每人至少一个），每人的糖果只能全部为一种。求怎么分可以让每个人都尽可能多，即分得最少的人的糖果数也尽可能多，输出这个数量。样例：5 2 3     -5个人分 2+3 每人一个  输出14 7 10    a(3+4) b(5+5)  输出34 4 15    a(4)b(5+5+5) 输出4 思路： 可无限再分状态下，x = a/(a+b)*n人得到a，y = b/(a+b)*n人得到b，理想平均。由于人不可再分，得到a和得到b的人数必定有一个舍一个进。 即 x下取整人 得a，y上取整人得b，或x上取整人得b，y下取整得a。有了xy，直接用a//x，b//y得到 a糖果的最少分配和b糖果的最少分配。两者取最小得到一种分配情况下的最小值，两种情况求大者得到最终答案。  注意对全部分a和全部分b作特判，不然会除0异常。三、n个城市摆成一行，互相之间没有路。可使用 (L x) / (R x) 操作为x城市添加与 左边/右边 城市的一条双向路。可使用Q x操作查询城市x两边能到达最远的城市。共T次操作。样例：3 5   (3个城市5次操作)Q 2      P(初始状态查2，输出2  2   只能在原地)L 2       (向左连接2 和 1)Q 2      P(输出1 2)R 2       (向右连接2和3)Q 2      P(输出1 3)思路：想到建图，这里题目已经规定了点是按顺序排列的，因此有数组的属性，可以看作特殊的图。而且是一个双向链表。维护一张双向链表，并且从给定节点向两端遍历即可。我用的dfsclass Node:    def __init__(self, left=None, right=None):        self.left = left        self.right = rightdef ldfs(node):    if not node.left:        return 0    return ldfs(node.left) + 1def rdfs(node):    if not node.right:        return 0    return rdfs(node.right) + 1ar = [None] * (n + 2)      if oper == "Q":        l = ldfs(ar[x])        r = rdfs(ar[x])        print(x-l, " ", x+r)    if oper == "L":        if x <=1:            continue        ar[x].left = ar[x - 1]        ar[x-1].right = ar[x]    if oper == "R":        if x>=n:            continue        ar[x].right = ar[x + 1]        ar[x+1].left = ar[x]四、n个套娃，每个套娃有属性 体积a、容积b、单位价值c。如果套娃内部是空的，则满价值，如果有其他套娃占位，只计算空的部分的价值。比如单位价值2的容积5的套娃原价2*5，被体积3的填了，则价值改为2*2套娃可以互相套也可以不套完，求一种方式使得所有套娃总价值最低。样例：35 4 34 2 23 2 1 第二个放第一个里第一个没有价值，后两个2*2+2*1 输出6思路： 动态规划吧，我不太行。想着骗分，就按照容积为键排了个序，由小到大尝试往里放。暴力过了18%欢迎补充。五、n个自然数(>=0)集合，可以将一个数增加到任意值。求任意操作后，集合中没有出现的最小自然数，最大可能为多少。样例：55 0 0 2 2  可改为5 0 1 2 3  输出4思路：由小到大排个序，第i个数小于等于i的计数器加一，大于i的终止循环。输出计数器做了1+1+1+0.18+1[苦涩]第一次做美团笔试，不知道有机会不。