美团4.4笔试

写在前面：看到身边朋友的笔试题自己练一下，未投互联网。

一、优美字符串

题目：一天，小美在写英语作业时，发现了一个十分优美的字符串：这个字符串没有任何两个字符相同。于是，小美随手写下了一个字符串，她想知道这个字符串的的所有子序列，有多少个是优美的。由于答案可能会很大，输出对20210101取模后的结果。一个字符串的子序列定义为：原字符串删除0个或多个字符后剩下的字符保持原有顺序拼接组成的字符串为原串的子序列。如：ab是acba的子序列，但bc则不是。在本题中。空串也为原串的子序列。
思路：排列组合。统计每个字符出现的次数，记为cnt。每个字符有选择和不选择两种情况，选择的即为cnt种情况，不选的情况只有一种。所以每个字符为（cnt+1）种情况，所有出现过的字符的情况种类相乘，即为结果。
注：为防止溢出，每一步都要取模

str1='aabc'
x=set(str1)
res=1
for i in x:
    temp=str1.count(i)
    res=res*(temp+1)
    res=res%20210101

二、切分蛋糕

题目：今天是小美的生日，妈妈给她专门订制了一个球形的大蛋糕。小美决定对这个蛋糕切n刀。每次切小美会选择是横着切还是竖着切。将整个球划分经纬度。如果是横着切的话那么小美会选择一个纬度将整个球切成上下两部分；如果是竖着切的话那么小美会选择一个经度将整个球切成两半。小美想知道，切n刀之后整个球被划分成了多少个部分？另外，在经度上，例如切90°和270°，0°和180°等视为两种不同的切法。
思路：横着切一分为二，每切一次+1；竖着切过轴线，所以每切一次+2
注：初始值均为1

n=int(input())
long=[] #经度
la=[]   #纬度
for i in range(n):
    list1=list(map(int,input().split()))
    if list1[0]==1:
        long.append(list1[1])
    elif list1[0]==0:
        la.append(list1[1])
long1=long.copy()
for j in long:
    if j+180 in long:
        long1.pop(j)
x=len(long1)
y=len(la)
if x==0:
    print(1*(y+1))   #保证经度不切时初值也为1
else:
    print(2*x*(y+1))
print(2*x*(y+1))

二、讨厌数字

题目：小美发明了一个函数：f(x)，表示将x的所有正整数因子提取出来之后从小到大排列，再将数字拼接之后得到的数字串。例如：10的所有因子为1,2,5,10，那么将这些因子从小到大排序之后再拼接得到的数字串为12510，即f(10)=12510。小美十分讨厌数字k，如果f(x)中含有某个子串对应的数字等于k，那么她的不高兴度就会增加1。例如：f(8)=1248，那么其所有的子串为：1,2,4,8,12,24,48,124,248,1248，只要k等于其中任意一个值，那么小美的不高兴度就会增加1。对于每一个数，其不高兴度至多增加1。现在，有一个长度为n的正整数序列，定义其不高兴度为序列中所有数的不高兴度的总和。小美想要知道自己对于这个序列的总不高兴度为多少。
注：有可能未AC100%

n,k=map(int,input().split())
list1=list(map(int,input().split()))
def factor(x):
    res=''
    if x==0:
        return '0'
    elif x==1:
        return '1'
    else:
        for i in range(1,x+1):
            if x%i==0:
                res=res+str(i)
        return(res)
def unhappy(str1,k):
    res=0
    for i in range(len(str1)):
        for j in range(i,len(str1)+1):
            if str1[i:j]==k: 
                res=1
    return res
k=str(k)
result=0
for i in list1:
    fac=factor(i)
    temp=unhappy(fac,k)
    result=result+temp
print(result)

#美团##笔试题目#