首页 > 8.22 美团笔试
头像
zyx_xiao
编辑于 2020-08-22 18:09
+ 关注

8.22 美团笔试

1.判断命名是否合法
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
char s[10005];
bool num(char c){
    return c>='0' && c<='9';
}
bool A(char c){
    return c>='A' && c<='Z';
}
bool a(char c){
    return c>='a' && c<='z';
}
bool f(){
    int l = strlen(s);
    int f = false;
    for(int i = 0 ; i < l ; i++){
        if(!A(s[i]) && !a(s[i]) && !num(s[i]))
            return false;
        if(i==0 && num(s[i]))
            return false;
        if(num(s[i])){
            f = true;
        }
    }
    return f;
}
int main()
{
    scanf("%d", &n);
    while(n--){
        scanf("%s", s);
        if(f())
            printf("Accept\n");
        else
            printf("Wrong\n");
    }
    return 0;
}

2. 取最大的m个值
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
struct Node{
    int id, w;
    Node(){}
    Node(int i, int w):id(i), w(w){}
    bool operator<(const Node a) const{
        if(w == a.w)
            return id < a.id;
        return w > a.w;
    }
};
Node a[100005];
int main()
{
    int v, w;
    scanf("%d %d", &n, &m);
    for(int i = 0 ; i < n ; i++){
        scanf("%d %d", &v, &w);
        a[i].id = i+1;
        a[i].w = v + w*2;
    }
    sort(a, a+n);
    vector<int> ans;
    for(int i = 0 ; i < m ; i++)
        ans.push_back(a[i].id);
    sort(ans.begin(), ans.end());
    for(int i = 0 ; i < m ; i++){
        printf("%d%c", ans[i], i==m-1?'\n':' ');
    }
    return 0;
}

3. 倒着想。每次加一个点,判断左右是否有点,有的话就合并。合并用到并查集
#define MAXN 50005
int a[MAXN];
int b[MAXN];
int sum[MAXN];
int ans[MAXN];

class UnionFind{
public:
    int n, count;
    vector<int> father;
    UnionFind(int num){
        n = count = num;
        father.resize(n);
        for(int i = 0 ; i < n ; i++)
            father[i] = i;
    }
    int find(int x){
        if(father[x] == x)
            return x;
        return find(father[x]);
    }
};
int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i++)
        scanf("%d", &a[i]);
    for(int i = 0 ; i < n ; i++)
        scanf("%d", &b[i]);
    ans[n-1] = 0;
    int mmax = 0;
    UnionFind u(n);
    for(int i = n-1 ; i >= 0 ; i--){
        int id = b[i] - 1;
        sum[id]+= a[id];
        if(id > 0 && sum[id-1] > 0){
            int x = u.find(id);
            int y = u.find(id - 1);
            if(x != y){
                sum[x] += sum[y];
                u.father[y] = x;
            }
        }
        if(id < n-1 && sum[id+1] > 0){
            int x = u.find(id);
            int y = u.find(id + 1);
            if(x != y){
                sum[x] += sum[y];
                u.father[y] = x;
            }
        }
        mmax = max(mmax, sum[u.find(id)]);
        if(i > 0)
            ans[i-1] = mmax;
    }
    for(int i = 0 ; i < n ; i++)
        printf("%d\n", ans[i]);
    return 0;
}

4. 感觉之前见过,还是不会...


全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐