美团4.4除第4题ac思路

1. 字符串子集

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

思路

下标不同就当作是子序列不同，同时要求子序列所有元素都不同。直接当成组合问题做即可。
使用一个map存各个字符串出现的次数，结果所有出现过的字符(次数+1)相乘。[次数的含义代表选哪个下标，+1是代表不选]
例如aab就是map[a]=2,map[b]=1 答案(2+1)*(1+1)
注意的点，记得mod

2. 蛋糕块数

/**
 * @author zhangbingbing
 * @version 1.0
 * @date 2021/4/4 10:57
今天是小美的生日，妈妈给她专门订制了一个球形的大蛋糕。
小美决定对这个蛋糕切n刀。每次切小美会选择是横着切还是竖着切。
将整个球划分经纬度。
如果是横着切的话那么小美会选择一个纬度将整个球切成上下两部分；
如果是竖着切的话那么小美会选择一个经度将整个球切成两半。
 *
 * 小美想知道，切n刀之后整个球被划分成了多少个部分？
 *
 * 请注意本题中经纬度的表示如图：
 */
另外，在经度上，例如切90°和270°、0°和180°等视为两种不同的切法。

这道题比较有争议的是「另外，在经度上，例如切90°和270°、0°和180°等视为两种不同的切法。」这句话，我理解是经度0和经度180视作2刀，然后这个理解刚好过了。
确认这个理解本题就很好写代码了。记录经度总刀数和纬度总刀数

if(经度刀数==0)
    输出 1*(纬度刀数+1)
else
    输出 (经度刀数*2) * (纬度刀数+1)

3. 讨厌的数

/**
 * @author zhangbingbing
 * @version 1.0
 * @date 2021/4/4 11:08
 * 小美发明了一个函数：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的正整数序列，定义其不高兴度为序列中所有数的不高兴度的总和。
小美想要知道自己对于这个序列的总不高兴度为多少。
 */

三步走，先找到原数字的质因数，存到deque中(主要是可以同时前插和后插，从sqrt(num)开始遍历头尾插，遍历完deque刚好是按顺序的
deque转成string。这里吐槽一下 itoa的头文件到底是什么，垃圾平台死活掉不出来自己手写了一个
转成string直接find就好了。因为子串是连续的，find能找到就说明有。(这里需要注意的点是，对于每一个数，不高兴度至多增加1，假如搜到几个加几个不高兴度过54%)
这题刚好有代码在本地ide，我是真的debug了半天，大家轻喷。

#include<iostream>
#include<vector>
#include <map>
#include <string>
#include <cstring>
#include<deque>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

void selfitoa(int shuzi , char* c, int base){
    int tmp = shuzi;
    int weishu = 0;
    //算位数
    while(tmp != 0){
        tmp /= base;
        weishu++;
    }
    char ch;
    c[weishu] = '\0';
    while(shuzi!=0){
        ch = '0' + shuzi % base;
        c[weishu - 1] = ch;
        shuzi /= base;
        weishu--;
    }
    return;
}

int f(int num, int k){
    //找因子 拼成序列
    string str;
    deque<int> deq;
    for(int i = sqrt(num) ; i >= 1 ; --i){//sqrt向下取整
        if(num % i ==0){//是因子
            if(num/i == i){//刚好开方
                deq.push_back(i); 
                continue;
            }
            deq.push_front(i);//小在前
            deq.push_back(num/i);
        }
    }
    //因子全在deq里面了
    //因为是等于其中一个值  所以可以string的find
    char c[10];
    for(auto shuzi : deq){
        //拿到数字可以加
        selfitoa(shuzi, c, 10);//从头加到尾
        str += c;
    }
    //cout << str<<endl;
    //开始查找
    int pos1 = 0, pos2 = 0;
    string kk;
    selfitoa(k, c, 10);
    kk += c;
    pos2 = str.find(kk);
    int res = 0;
    while(pos2!=string::npos){
        res++;//找到
        break;
        pos1 = pos2 +1;
        pos2 = str.find(kk , pos1);
    }
    return res;
}

int main(){
    int n,k;
    cin>>n>>k;
    int num;
    int ans = 0 , times;
    for(int i = 0 ; i < n ; ++i){
        cin>>num;
        times = f(num, k);
        ans += times;
    }
    cout<<ans<<endl;
    return 0;
}

4. 跳格子

不会，第三题debug那个不高兴至多增加1的bug找了半小时，等评论区大佬。
皮了一下无脑输出-1，过0.09

5. 分糖果

前缀和就好了。算一个数组前k项的和，再搜一个最大值，O(N)复杂度，不需要任何优化。
想不到最简单的题在专项。