网易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 之后再读入要提前把
\n读进去 - 输入节点是从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;
}
