首页 > 美团 4.4 笔试 100%样例 代码及基本思路
头像
_王泥煤
编辑于 2021-04-16 18:02
+ 关注

美团 4.4 笔试 100%样例 代码及基本思路

考试代码没存,但是题目都不复杂,看到别人发题目了,就重写了一下,毕竟思路都在......


第一题

找出所有字符都不相同的字符串
只要判断第i个字符的出现情况
假设第i个字符在原字符串中出现了a[i]次
那么我就有a[i]+1种策略,1种是不选,另一种是选择这a[i]个中的其中一个
原题明确说了,下标不同但是字符相同的子序列被认为是不同的,所以以上策略不需要考虑重复,直接遍历i,每个a[i]+1相乘即可

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

#include
using namespace std;
const int mod = 20210101;
int main() {
    string s; cin>>s;
    int cnt[26]; memset(cnt, 0, sizeof(cnt));
    for(char& c : s) ++cnt[c - 'a'];
    int ans = 1;
    for(int i = 0; i < 26; ++i) {
        ans = 1ll * ans * (cnt[i] + 1) % mod;
    }
    cout<<ans<<endl;
    return 0;
}

第二题

横切的时候,每多切一刀多一份,也就是横切次数+1份
竖切的时候,每多切一刀多2份,特殊情况是竖切0刀仍有1份,也就是max(1, 竖切次数*2)
所以答案就是(cnt[0]+1)*max(1, cnt[1]*2)
我的cnt[0]初始化就是1,所以在答案里面没有+1

这题我认为题目描述有问题,横着切不保证和赤道平行,这也就算了
最主要的是竖着切不保证过圆心(这种情况下3刀显然可以切成7份而不是6份)
题目虽然说了“90和270,0和180被视为两种不同的切法”
但是我初读题的时候以为是为了对应下面的条件“保证切的经度纬度各不相同”,让0和180能作为合法的输入
因为你不管认为他是几刀,你怎么切都不能在过圆心的情况下,在0度和180度两刀切出4份来,这是物理规律
要么你题目完全排除掉现实因素,直接给我抽象一个非球体的几何体,要么你这个题目就不成立
就好像是在说:“你今年10岁,你爷爷今年100岁,但我认为10=100,所以你爷爷和你一样大”
拿着一个错误的条件来推错误的结论,真的就很荒谬

/**
今天是小美的生日,妈妈给她专门订制了一个球形的大蛋糕。
小美决定对这个蛋糕切n刀。每次切小美会选择是横着切还是竖着切。
将整个球划分经纬度。
如果是横着切的话那么小美会选择一个纬度将整个球切成上下两部分;
如果是竖着切的话那么小美会选择一个经度将整个球切成两半。
 *
 * 小美想知道,切n刀之后整个球被划分成了多少个部分?
 *
 * 请注意本题中经纬度的表示如图:
 */

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    int cnt[2] = {1, 0};
    while(n--) {
        int t, x; scanf("%d%d", &t, &x);
        ++cnt[t];
    }
    printf("%d\n", cnt[0] * max(1, cnt[1]*2));
    return 0;
}

第三题

暴力题
主要是敢写&会写
流程很简单。。跟着题目说的步骤走就完了
先找每个数的所有因数,这一步可以用O(√n)解决
然后把因数从小到大输出到字符串s
最后在这个字符串s中找有没有数字k
这一步需要先把数字k输出到字符串t中,做字符串子串查询
字符串子串查询是KMP的经典问题,会让我联想到这个东西
但是由于题目给的k的范围只有2e4,长度不会超过5,所以暴力即可,不需要KMP

/**
 * 小美发明了一个函数: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的正整数序列,定义其不高兴度为序列中所有数的不高兴度的总和。
小美想要知道自己对于这个序列的总不高兴度为多少。
 */
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn], t[100];
int main() {
    int n, k; scanf("%d%d", &n, &k);
    sprintf(t, "%d", k); // 把k当做字符串输出到t中 
    int ans = 0;
    while(n--) {
        int x; scanf("%d", &x);

        // 找x的所有因数 
        set<int> st;
        for(int i = 1; i*i <= x; ++i) {
            if(x % i == 0) { // set自动去重,i=x/i的情况重复插入不会出现问题 
                st.insert(i);
                st.insert(x / i);
            }
        }

        // 把因数输出成字符串 
        int idx = 0;
        for(int u : st) {
            sprintf(s+idx, "%d", u);
            while(s[++idx]); // 找当前的字符串结尾('\0') 
        }

        // 在s中找t 
        for(int i = 0; i < idx; ++i) {
            bool flag = true;
            for(int j = 0; j < strlen(t); ++j) {
                if(s[i+j] != t[j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) { // 找到了 
                ++ans;
                break;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

第四题

一种暴力
要说是dp也行吧
问题具有最优子结构性质
代码也符合状态转移的特征
只是数组不叫dp而已

就是标记到达每个点时已经走过的距离
代码有注释自己看

/**
小美在路上看到一些小学生在玩跳方格,她也想跟着一起玩。
这个方格被划分为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。
 */

#include<bits/stdc++.h>
using namespace std;
typedef struct Node {
    int x, y, d;
    // d表示到达这个点的距离,初始化设置为很大的数,认为不可达 
    // 后续要进行加减操作的,不能用INT_MAX 
    Node(int x = 0, int y = 0, int d = 9999999) : x(x), y(y), d(d) {}
    int dis(const Node& node) const {
        return abs(x - node.x) + abs(y - node.y);
    }
} Node;
int main() {
    int n, k; scanf("%d%d", &n, &k);
    vector<vector<Node>> vec(k+1, vector<Node>());
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) {
            int v; scanf("%d", &v);
            vec[v].push_back(Node(i, j));
        }
    // 标记为1的点是起始位置,距离初始化为0
    for(Node& n : vec[1])
        n.d = 0;
    for(int i = 2; i <= k; ++i) { // 从标记为2的点开始遍历,一直到标记为k的点 
        for(Node& v : vec[i]) { // 找所有标记为i的点 
            int d = 9999999; // 判断到这个点的距离,初始化默认为不可达 
            for(Node& u : vec[i-1]) { // 标记为i的点是从标记为i-1的点过来的 
                // 找到离v最近的u的距离 
                d = min(d, u.d + v.dis(u));
            }
            v.d = d;
        }
    }

    // 找标记为k的点的最小距离 
    int ans = 9999999;
    for(Node& node : vec[k])
        ans = min(ans, node.d);
    if(ans > 100000)
        ans = -1;
    printf("%d\n", ans);
    return 0;
}

第五题

找不到题目
大意是有一个长度为A的数组和长度为B的数组
数组的每个数都代表了一颗糖果的甜度(可能为0或负值)
拿糖果的时候必须从第一个开始拿,可以拿任意多个,问最多甜度多少

也就是维护两个前缀和,然后找前缀和的最大值,相加就行了。。非常简单

#include<bits/stdc++.h>
using namespace std;
int main() {
    int A, B; scanf("%d%d", &A, &B);
    int v = 0; // 用一个变量维护遍历到当前位置时的前缀和,相当于sum[i] 
    int maxA = 0, maxB = 0;
    while(A--) {
        int t; scanf("%d", &t);
        v += t;
        maxA = max(maxA, v);
    }
    v = 0;
    while(B--) { // 跟上面一模一样的
        int t; scanf("%d", &t);
        v += t;
        maxB = max(maxB, v);
    }
    printf("%d", maxA + maxB);
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐