网易2021算法

网易2021校招笔试-算法工程师（正式第二批）

... 也不知道考这么多图论干嘛 测试链接

01 - [编程题]项目经理

A公司和B公司有n个合作的子项目，每个子项目由A公司和B公司各一名员工参与。一名员工可以参与多个子项目。

一个员工如果担任了该项目的项目经理，它需要对所参与的该项目负责。一个员工也可以负责多个项目。

A公司和B公司需要保证所有子项目都能有人负责，问最少需要指定几名项目经理？

输入描述:

第一行为A公司的的人员id列表， 0< id数量 < 10000，用空格切分 第二行为B公司的人员id列表， 0< id数量 < 10000，用空格切分 第三行为有已经有多少个匹配数子项目合作关系n 下面有n行，每一行为每个子项目的合作对应关系，为两个id，第一个为A公司的员工id，第二个为B公司的员工id，用空格区分

输出描述:

一个整数，A公司和B公司合起来至少需要指定几名项目经理

输入例子1:

0 1 2
3 4 5
6
0 4
0 3
1 3
1 4
2 5
2 4

输出例子1:

3

例子说明1:

可行的一个保留人员方案是留下0,1,2即可，这样即可保证所有的子项目都有人cover到

---

二分图的最小覆盖点问题（没见过怎么可能想得到）

二分图的最大匹配问题，最少覆盖点问题，最少边覆盖问题，最大独立集问题 都是匈牙利算法

注意有两个程序的细节：

• 未指定输入个数在c++怎么读入: stringstream 注意cin 之后再读入要提前把读进去

• 输入节点是从0开始的 但匈牙利算法是以0作为未匹配标志 这里把所有点的编号整体向后移动一位

#pragma GCC optimize(3)  
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>

using namespace std;

const int N = 10010, M = 20020;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
int node1[N], node2[N];

// 匈牙利算法
bool find(int x)
{
    for(int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
    memset(h, -1, sizeof h);
    int x1, x2;
    string line;
    getline(cin, line);
    stringstream ss(line);
    while(ss >> x1)
    {
        node1[++n1] = x1 + 1;
    }
    getline(cin, line);
    stringstream ss2(line);
    while(ss2 >> x2)
    {
        node2[++n2] = x2 + 1;
    }
    cin >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a + 1, b + 1);
    }
    int res = 0;
    for(int i = 1; i <= n1; i++)
    {
        int x = node1[i];
        memset(st, false, sizeof st);
        if(find(x)) res++;
    }
    printf("%d\n", res);
    return 0;
}

02 - [编程题]分割字符串的最大得分

给你一个由若干 0 和 1 组成的字符串s，请你计算并返回将该字符串分割成两个子字符串（即左子字符串和右子字符串, 子字符串允许为空）所能获得的最大得分。 已知分割字符串的得分规则如下： 左子字符串中：0得2分，1得1分 右子字符串中：1得2分，0得1分 子字符串为空则得0分

输入描述:

一行包括一个由0和1组成的字符串s

输出描述:

一行一个整数表示答案。

输入例子1:

011101

输出例子1:

11

例子说明1:

当左子字符串 = "0" 且 右子字符串 = "11101"，得分最大= 2+ 9 = 11

输入例子2:

00111

输出例子2:

10

例子说明2:

当左子字符串 = "00" 且右子字符串 = "111" 时，得分最大 = 4 + 6 = 10

---

前后缀分解了 很经典的前后缀分解问题 分别预处理前缀分数和后缀分数 枚举中点即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
    string line;
    getline(cin, line);
    int n = line.size();
    line = " " + line;
    vector<int> f(n + 2, 0), g(n + 2, 0);
    // 预处理 f 和 g （递推）
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] + 1;
        if(line[i] == '0') f[i] += 1;
    }
    for(int i = n; i >= 1; i--)
    {
        g[i] = g[i + 1] + 1;
        if(line[i] == '1') g[i] += 1;
    }
    // 前后缀分解 ：枚举中点
    int res = 0;
    for(int i = 0; i <= n; i++)
        res = max(res, f[i] + g[i + 1]);
    printf("%d", res);
    return 0;
}

03 - [编程题]电影院选座

疫情逐步缓和后，电影院终于开业了，但是由于当前仍处于疫情期间，应尽量保持人群不聚集的原则。 所以当小易来电影院选定一排后，尽量需要选择一个远离人群的位置。 已知由0和1组成的数组表示当前排的座位情况,其中1表示已被选座，0表示空座 请问小易所选座位和最近人的距离座位数最大是多少？ 有如下假设：至少有一个人已选座，至少有一个空座位，且座位数限制为

输入描述:

一行由0和1组成的整数数组

输出描述:

仅一行一个整数表示答案

输入例子1:

1 0 0 0 1 0 1

输出例子1:

2

例子说明1:

小易第3个座位最合适，则和座位1/座位5的距离为2

输入例子2:

1 0 1 0 1

输出例子2:

1

例子说明2:

小易可以选择第2个座位或者第4个座位，距离为1

贪心吗 最大连续0的个数除以二上取整？

要注意的边界情况就是 0 0 0 0 0 1 这里的最大距离是5 所以两边的0要特判一下

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

const int N = 1010;
int n = 0;
int nums[N];

int main()
{
    int x;
    while(cin >> x)
    {
        nums[++n] = x;
    }
    // 统计连续0的个数
    int zeros = 0, res = 0;
    bool first = true;
    for(int i = 1; i <= n; i++)
    {
        if(nums[i] == 0)
           zeros++;
        // "前导0"的特判
        else if(first)
        {
            res = max(res, zeros);
            zeros = 0;
            first = false;
        }
        else{
            res = max(res, (zeros + 1) / 2);
            zeros = 0;
        }
    }
    // "后导0"的特判
    res = max(res, zeros);
    printf("%d\n", res);
    return 0;
}

04 - [编程题]仓库配送

网易严选建有N个自营仓分布在全国各地，标记为仓库1到N。 给定一个配货时间组（v,u,w)，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远，无法支持调拨转货。 指定一个出发仓库K，我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间？如果无法全部调拨到，则返回-1.

输入描述:

第一行三个正整数，由空格分割，分别表示仓库个数N，出发仓K，以及配送时间组个数M 接下来 M行，每行三个整数，由空格分割，分别表示（v,u,w)三个数，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间

输出描述:

一行一个数字表示答案，配送到所有可达仓库到最短时间

输入例子1:

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

输出例子1:

5

---

比第一题简单多了... 这题是最短路的板子题 所有最短路的最大值罢了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
using PII = pair<int, int>;
const int N = 10010, M = 50050;

int n, m, target;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.emplace(0, target);
    dist[target] = 0;
    while(heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.emplace(dist[j], j);
            }
        }
    }
}
int main()
{
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    memset(st, false, sizeof st);
    scanf("%d%d%d", &n, &target, &m);
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    dijkstra();
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dist[i] == 0x3f3f3f3f)
        {
            res = -1;
            break;
        }
        res = max(res, dist[i]);
    }
    printf("%d", res);
    return 0;
}