淘宝笔试（9月13日）

T1 用堆乱搞就行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define lowbit(x) x & (-x)
const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e9;

int a[N];

void solve(){
    int m, n;
    cin >> m >> n;
    ll maxx = 0, minn = 0;
    priority_queue<int> q;
    priority_queue<int, vector<int> , greater<int>> p;
    for(int i = 1; i <= m; ++i){
        cin >> a[i];
        q.push(a[i]);
        p.push(a[i]);
    }
    int tmp = n;
    while(q.size() && tmp--){
        maxx += q.top();
        if(q.top() != 1)
            q.push(q.top() - 1);
        q.pop();
    }
    tmp = n;
    while(p.size() && tmp--){
        minn += p.top();
        if(p.top() != 1)
            p.push(p.top() - 1);
        p.pop();
    }
    cout << minn << " " << maxx << '\n';
}

// 2 2
// 5 1

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

T2 简单dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define lowbit(x) x & (-x)
const int N = 200 + 10, mod = 1e9 + 7, inf = 1e9;

int nopr[N], dp[N][N];

void solve(){
    for(int i = 2; i <= 200; ++i){
        for(int j = 2; j < i; ++j){
            if(i % j == 0) nopr[i] = 1;
        }
    }
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(i == 1) dp[i][j] = 1;
            else{
                for(int k = 1; k <= m; ++k){
                    if(j != k && nopr[k + j]){
                        dp[i][k] = (dp[i - 1][j] + dp[i][k]) % mod;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; ++i) ans = (ans + dp[n][i]) % mod;
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

T3 不会，可能也是dp