拼多多研发笔试题(3过，最后一题卒)

//暴力覆盖就可以了
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN = 1e2 + 5;
const int INF = 0x3f3f3f3f;
int n, k;
int T[MAXN];
int main(){
    while(~scanf("%d%d", &n, &k)){
        memset(T, 0, sizeof(T));
        int a, b;
        for(int i = 0;i < n;i ++){
            scanf("%d%d", &a, &b);
            for(int j = a;j <= b;j ++){
                T[j + 50] ++;
            }
        }
        int maxs = -INF;
        int mins = INF;
        for(int i = 0;i < MAXN;i ++){
            if(T[i] >= k) {
                maxs = max(maxs, i - 50);
                mins = min(mins, i - 50);
            }
        }
        if(mins == INF && maxs == -INF){
            printf("error\n");
        }
        else{
            printf("%d %d\n", mins, maxs);
        }
    }
    return 0;
}


//纯粹模拟题
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int MAXN = 1e2 + 5;
const int INF = 0x3f3f3f3f;
int n, m;

struct Food{
    int mw;
    int xs;
    bool cmc;
    bool gmgq;
    int id;
    bool operator < (const Food & a) const{
        if(mw == a.mw) return xs > a.xs;
        return mw > a.mw;
    }
}F[MAXN];

int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i = 0;i < n;i ++){
            scanf("%d%d", &F[i].mw, &F[i].xs);
            F[i].id = i;
            F[i].cmc = false;
            F[i].gmgq = false;
        }
        int curs = n;
        while(curs >= m){
            sort(F, F + n);
            int cs = 0;
            for(int i = 0;i < n;i ++){
                if(!F[i].gmgq && !F[i].cmc && cs < 2){
                    F[i].cmc = true;
                    cs ++;
                    curs --;
                }
                else{
                    if(!F[i].cmc && !F[i].gmgq) {
                        F[i].mw -= F[i].xs;
                        if(F[i].mw <= 0) F[i].gmgq = true, curs --;
                    }
                }
            }
        }
        vector<pair<int, int> > vec;
        for(int i = 0;i < n;i ++){
            int k = 0;
            if(F[i].cmc) k = -1;
            else if(F[i].gmgq) k = 0;
            else k = F[i].mw;
            vec.push_back(make_pair(F[i].id, k));
        }
        sort(vec.begin(), vec.end());
        for(int i = 0;i < n;i ++){
            printf("%d\n", vec[i].second);
        }
    }
    return 0;
}

//是一个动态规划DP
//dp[i][j]表示以位置i为结尾长度为j的本质不同的上升子序列的个数
//dp[i][j] = dp[k][j - 1]{k从i-1遍历减小 && A[k]没有被访问过}
//最终求和的时候也要考虑A[k]有没有被访问，然后输出结果就可以了
//当然此题还可以用其他方法，用bitset位操作直接DFS递归可以拿到90%的分
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <bitset>
#include <map>
#include <unordered_set>

using namespace std;
const int MAXN = 20 + 5;
const int INF = 0x3f3f3f3f;
const int XX = 200 + 5;
int n, m;
int A[MAXN];
int dp[MAXN][MAXN];
bool vis[XX];
int main() {
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &A[i]);
            A[i] += 100;
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i ++) dp[i][1] = 1;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                memset(vis, false, sizeof(vis));
                for(int k = i - 1; k >= 1; k --) {
                    if(A[i] > A[k] && !vis[A[k]]) {
                        vis[A[k]] = true;
                        dp[i][j] += dp[k][j - 1];
                    }
                }
            }
        }
        int sum = 0;
        memset(vis, false, sizeof(vis));
        for(int i = n; i >= 1; i --) {
            if(vis[A[i]]) continue;
            vis[A[i]] = true;
            for(int j = 2; j <= n; j ++) {
                sum += dp[i][j];
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

	



	//最后一题，暴力map，只拿到了10%,没时间做了，恩，应该使用可持久化数据结构来做，***树好像做不了，所以已卒