美团 4.4 笔试

作者：努力的bingbing
链接：https://www.nowcoder.com/discuss/632022?type=2&channel=1009&source_id=discuss_center_discuss_hot_nctrack

1.

一天，小美在写英语作业时，发现了一个十分优美的字符串：
这个字符串没有任何两个字符相同。
于是，小美随手写下了一个字符串，
她想知道这个字符串的的所有子序列，有多少个是优美的。
由于答案可能会很大，输出对20210101取模后的结果。
一个字符串的子序列定义为：
原字符串删除0个或多个字符后剩下的字符保持原有顺序拼接组成的字符串为原串的子序列。
如：ab是acba的子序列，但bc则不是。在本题中。空串也为原串的子序列。
*

• 两个子序列不相同，当且仅当他们对应原串的下标不相同。如aab则含有两个子序列ab。
• /

2.

今天是小美的生日，妈妈给她专门订制了一个球形的大蛋糕。
小美决定对这个蛋糕切n刀。每次切小美会选择是横着切还是竖着切。
将整个球划分经纬度。
如果是横着切的话那么小美会选择一个纬度将整个球切成上下两部分；
如果是竖着切的话那么小美会选择一个经度将整个球切成两半。
*

• 小美想知道，切n刀之后整个球被划分成了多少个部分？
• 请注意本题中经纬度的表示如图：
• /

3.

• 小美发明了一个函数：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的正整数序列，定义其不高兴度为序列中所有数的不高兴度的总和。
  小美想要知道自己对于这个序列的总不高兴度为多少。
• /

4.

小美在路上看到一些小学生在玩跳方格，她也想跟着一起玩。
这个方格被划分为n×n的小方格，即有n行n列。
每一个小方格上面都是一个1~k的正整数。小美想依次从1,2,…,k这个顺序来跳。
一开始小美可以站在任意一个小方格。
从一个方格跳到另一个方格的花费为两个方格的曼哈顿距离。
小美想知道是否可以依照该顺序一直跳到k，如果可以，最小的总花费是多少。

两个格子(x1,y1),(x2,y2)的曼哈顿距离为：|x1-x2|+|y1-y2|。
例如(3,4),(1,6)的曼哈顿距离为|3-1|+|4-6|=4。

5.

第五题比较简单没记，前缀和处理输入就行。