首页 > 20200802 拼多多秋招笔试题
头像
三更未眠
编辑于 2020-08-02 23:40
+ 关注

20200802 拼多多秋招笔试题

题意就略过哒...

第一题(96%)

????
不知道为啥不能全过。。。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long infl = 0x3f3f3f3f3f3f3f3fll;

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-1.txt", "r", stdin);
#endif // __LOCAL_WONZY__
    int k, n;
    cin >> k >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int cur = k;
    int back_cnt = 0;
    for(int i = 0; i < n; ++i) {
        cur -= arr[i];
        if(cur == 0) {
            break;
        } else if(cur < 0) {
            cur *= -1;
            back_cnt += 1;
        }
    }
    if(cur == 0 || k == 0) cout << "paradox" << endl;
    else {
        cout << cur << " " << back_cnt << endl;
    }
	return 0;
}

第二题(100%)

dfs枚举状态+hash
得亏我旁边有一个方形盒子... 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long infl = 0x3f3f3f3f3f3f3f3fll;

typedef vector<int> Node;

Node up_down_rotate(Node& nd) {
    // 右转一次: 前->右,右->后,后->左,左->前
    return Node({nd[0], nd[1], nd[5], nd[4], nd[2], nd[3]});
}

Node left_right_rotate(Node& nd) {
    // 下翻一次:前->下;上-》前;后-》上;下-》后;
    return Node({nd[5], nd[4], nd[2], nd[3], nd[0], nd[1]});
}

Node fore_back_rotate(Node& nd) {
    // 右翻一次:上->右,左-》上,下-》左;右-》下
    return Node({nd[2], nd[3], nd[1], nd[0], nd[4], nd[5]});
}

// 上下左右前后
void dfs(Node nd, unordered_set<int>& st) {
    int status = 0;
    for(int i = 0; i < nd.size(); ++i) {
        status = status * 6 + nd[i];
    }
    if(st.find(status) != st.end()) {
        return;
    }
    st.insert(status);
    // 右转一次: 前->右,右->后,后->左,左->前
    dfs(up_down_rotate(nd), st);
    dfs(left_right_rotate(nd), st);
    dfs(fore_back_rotate(nd), st);
}


int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-2.txt", "r", stdin);
#endif // __LOCAL_WONZY__
    int n;
    cin >> n;
    vector<Node> nodes(n, Node(6));
    unordered_map<int, int> st_cnt;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 6; ++j) {
            cin >> nodes[i][j];
        }
        unordered_set<int> st;
        dfs(nodes[i], st);
        int status = *min_element(st.begin(), st.end());
        st_cnt[status] += 1;
    }
    vector<int> ans;
    for(auto& pr : st_cnt) {
        ans.push_back(pr.second);
    }
    sort(ans.begin(), ans.end(), [](auto& x, auto& y) {
        return x > y;
    });
    cout << ans.size() << endl;
    for(auto& v : ans) {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}

第三题(100%)

双指针法/取尺法
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXT = 200005;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-3.txt", "r", stdin);
#endif // __LOCAL_WONZY__
    int n, m, t;
    cin >> n >> m >> t;
    vector<pair<int, int>> lunch(n+1), dinner(m+1);
    lunch[0] = dinner[0] = make_pair(0, 0);
    for(int i = 1; i <= n; ++i) {
        cin >> lunch[i].first >> lunch[i].second;
    }
    for(int i = 1; i <= m; ++i) {
        cin >> dinner[i].first >> dinner[i].second;
    }
    
    sort(lunch.begin(), lunch.end(), [](auto& a, auto& b) {
        return a.second > b.second; // 美味降序
    });
    sort(dinner.begin(), dinner.end(), [](auto& a, auto& b) {
        return a.second > b.second; // 美味降序
    });
    int ans = inf;
    set<int> dinner_st;
    for(int i = n, j = 0; i >= 0; --i) {
        // 放 dinner
        while(j <= m && dinner[j].second+lunch[i].second >= t) {
            dinner_st.insert(dinner[j].first);
            if(dinner[j].second >= t) ans = min(ans, dinner[j].first);
            ++j;
        }
        if(lunch[i].second >= t) ans = min(ans, lunch[i].first);
        if(!dinner_st.empty()) {
            ans = min(ans, lunch[i].first + (*dinner_st.begin()));
        }
    }
    if(ans == inf) cout << -1 << endl;
    else cout << ans << endl; 
	return 0;
}

第四题(20%)

不会做,只能暴力骗一点分....
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const long long MOD = 1e9 + 9;

const int MAXN = 10;
char G[MAXN][MAXN];
long long ans;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

vector<pair<int, int>> path;

bool check() {
    for(int x = 0; x < 6; ++x) {
        for(int y = 0; y < 6; ++y) {
            if(G[x][y] == '*') continue;
            for(int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if(nx < 0 || ny < 0 || nx >= 6 || ny >= 6) continue;
                if(G[nx][ny] == '*') continue;
                if(G[x][y] == G[nx][ny]) return false;
            }
        }
    }
    return true;
}

void dfs(int pos) {
    if(pos >= path.size()) {
        if(check()) {
            ans += 1;
            ans %= MOD;
        }
        return;
    }
    int x = path[pos].first, y = path[pos].second;
    for(int v = 0; v < 6; ++v) {
        bool flag = true;
        for(int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 || ny < 0 || nx >= 6 || ny >= 6) continue;
            if(G[nx][ny] == '*') continue;
            if(G[nx][ny] == v) flag = false;
        }
        if(!flag) continue;
        G[x][y] = v;
        dfs(pos + 1);
        G[x][y] = '#';
    }
}


int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-4.txt", "r", stdin);
#endif // __LOCAL_WONZY__
    path.clear();
    for(int i = 0; i < 6; ++i) {
        scanf("%s", G[i]);
        for(int j = 0; j < 6; ++j) {
            if(G[i][j] == '#')
                path.push_back(make_pair(i, j));
        }
    }
    dfs(0);
    cout << ans << endl;
	return 0;
}

全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐