新鲜出炉的阿里、虾皮和网易笔试题解

5 2
1 2 3 4 5
3 2 5 4 1

5 3
1 2 3 4 5
3 2 1 4 5

// cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;
int t, n, k;
int in[N], out[N], vis[N];
int solve(int n, int k) {
    memset(vis, 0, sizeof(vis));
    set<int> st;
    for (int i = 1; i <= k; ++i) st.insert(in[i]);
    int j = k + 1, i = 1;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (st.count(out[i]) == 0) ans++, vis[out[i]] = 1;
        else st.erase(st.find(out[i]));
        while (j <= n && st.size() < k) {
            if (!vis[in[j]]) st.insert(in[j]);
            ++j;
        }
    }
    return ans;
}
int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i) scanf("%d", &in[i]);
        for (int i = 1; i <= n; ++i) scanf("%d", &out[i]);
        cout << solve(n, k) << endl;
    }
    return 0;
}
/*
2
5 2
1 2 3 4 5
3 2 5 1 4
5 3
1 2 3 4 5
3 2 1 4 5
*/

// cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 1;
int vis[N], prime[N], cnt = 0;
void init() {
    vis[1] = 0;
    prime[++cnt] = 1;
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j * i < N; ++j) {
            vis[j * i] = 1;
        }
    }
}

const int MAXN = 5e5 + 7;
char str[MAXN];
int dp[MAXN], pre[MAXN], val[MAXN], mp[N];
int main()
{
    init();
    for (int i = 1; i <= cnt; ++i) mp[prime[i]] = i;
    scanf("%s", str + 1);
    int L = strlen(str + 1);
    for (int i = 1; i <= L; ++i) {
        for (int j = max(0, i - 4 + 1); j < i; ++j) {
            int temp = 0;
            if (str[j + 1] == '0') temp = 0; // 有前导零
            else for (int k = j + 1; k <= i; ++k) temp *= 10, temp += str[k] - '0';
            if (mp[temp] > 0 && (dp[j] + (mp[temp] > 0)) > dp[i]) {
                pre[i] = j, val[i] = mp[temp] - 1; // 记录前继
                dp[i] = dp[j] + (mp[temp] > 0);
            }

        }
    }
    cout << dp[L] << endl;
    int cur = L;
    vector<int> ans;
    while (cur) {
        ans.push_back(val[cur]);
        cur = pre[cur];
    }
    for (int i = dp[L] - 1; i >= 0; --i) printf("%d%c", ans[i], " \n"[i == 0]);
    return 0;
}

// cpp
class Solution {
public:
    int solve(string command, string input) {
        int m = command.size();
        int n = input.size();
        vector<vector<int>> dp(m + 7, vector<int>(n + 7));
        for (int i = 0; i <= n; ++i) dp[0][i] = i;
        for (int j = 0; j <= m; ++j) dp[j][0] = j;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                if (command[i - 1] == input[j - 1]) dp[i][j] = min(dp[i - 1][j - 1], dp[i][j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j]);
            }
        }
        return dp[m - 1][n - 1];
    }
    string didYouMean(vector<string>& commands, string input) {
        int ans = 0;
        string val;
        for (auto &i: commands) {
            int temp = solve(i, input);
            if (temp < ans) ans = temp, val = i;
        }
        return val;
    }
};

// cpp
class Solution {
public:
    bool check(int n, int m, int k, vector<int> &weights) {
        int cnt = 0, temp = 0;
        for (int i = 0; i < n; ++i) {
            if (temp + weights[i] <= k) temp += weights[i];
            else cnt++, temp = weights[i]; 
        }
        if (temp) cnt++;
        return cnt <= m;
    }
    long long Solve(int n, int m, vector<int>& weights) {
        int L = 0, R = 0;
        for (auto &i: weights) R += i, L = min(L, i); 
        int ans = 0;
        while (L <= R) {
            int mid = L + R >> 1;
            if (check(n, m, mid, weights)) ans = mid, R = mid - 1;
            else L = mid + 1;
        }
        return ans;
    }
};

class Solution {
public:
    int minEffort(vector<int>& cases) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto &i: cases) pq.push(i);
        int ans = 0;
        while (pq.size() > 1) {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            ans += x + y;
            pq.push(x + y);
        }
        return ans;
    }
};