美团暑期实习

只留下了后两道编程题。。。 不过据说前两个编程题比较简单

编程题03 - 众数

具体题我就不抄了.. 大概意思是求滑动窗口（长度为k）内的所有最小众数（只有一个众数 直接输出， 有多个众数出现次数相同-> 输出最小的）

---

具体方案是维护这样一个数据结构：

• hash: 维护窗口内每个元素的出现次数

• vector<set<int>> A : 对于每个出现次数i而言 A[i]存放出现次数为i的所有元素

这样在进入窗口和弹出窗口的时候更新一下这两个就好了

void modify(vector<set<int>>& A, unordered_map<int, int>& hash, int val,  bool is_add)
{
    A[hash[val]].erase(val);
    if(is_add) hash[val]++;
    else hash[val]--;
    A[hash[val]].insert(val);
}

vector<int> solution(vector<int>& nums, int k)
{
    vector<int> res;
    unordered_map<int, int> hash;
    vector<set<int>> A(k + 1); // 出现次数为i的元素所在的集合
    for(int l = 0, r = 0, max_cnt = 0; r < nums.size(); r++)
    {
        modify(A, hash, nums[r], true);
        if(hash[nums[r]] > max_cnt) max_cnt = hash[nums[r]];
        if(l < r - k + 1)
        {
            modify(A, hash, nums[l++], false);
            if(A[max_cnt].empty()) max_cnt--;
        }
        if(r >= k - 1) res.push_back(*A[max_cnt].begin());
    }
    return res;
}

---

编程题04 - 树上DP

美团图论和dp是必考的 得了 这回考了个图论+dp的结合

具体题的意思: 给定一棵树，每一个节点有一个权重，选择其中某些节点，满足被选中的节点两两不相邻，求在所有的选择方案中，最大化被选择节点权值之和的情况下，被选择节点权值最小值尽可能大。

输入

第一行两个整数N和M，分别表示树的节点数和边数 第二行为N个整数，分别表示每个节点的权重 接下来M行，每行两个整数a和b，存在一条从a到b的边。

输出

输出两个整数，表示能选择的最大权值之和是多少，以及权值最小值是多少，用空格分割。

输入样例

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

输出样例

16 3

---

基础就是 树上一条边只能选一个节点， 求权值最大 可以说是树上DP的经典题了

这题比我做过的树上DP还要怪 我开始也没反应过来那个最大化被选择节点权值之和的情况下，被选择节点权值最小值尽可能大是啥意思

后来发现是在两个子节点权值一样 选哪个都可以的时候，选哪个权值大的child

剩下的建图和DFS（是的树上dp都是dfs写的）都是很经典的套路了

• f[i, 0] 表示不选node[i]的最大方案

• f[i, 1] 表示选node[i]的最大方案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int val[N];
int f[N][2], minv[N][2];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

void dfs(int u, int father)
{
    f[u][1] = val[u];
    minv[u][1] = val[u];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs(j, u);
        // // 一般处理
        // f[u][1] += f[j][0];
        // f[u][0] += max(f[j][1], f[j][0]);
        f[u][1] += f[j][0];
        minv[u][1] = min(minv[u][1], f[j][0]);
        // 带最大值的更新
        f[u][0] += max(f[j][0], f[j][1]);
        if(f[j][0] > f[j][1])
            minv[u][0] = min(minv[u][0], minv[j][0]);
        else if (f[j][0] < f[j][1])
            minv[u][0] = min(minv[u][0], minv[j][1]);
        else
            minv[u][0] = min(minv[u][0], max(minv[j][0], minv[j][1])); // 如果f一样 就挑大的
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", val + i);
    // 1. 建图
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    // 2. 树上dp
    dfs(1, -1);
    if(f[1][0] > f[1][1])
        cout << f[1][0] << ' ' << minv[1][0] << endl;
    else
        cout << f[1][1] << ' ' << minv[1][1] << endl;
    return 0;
}