2023顺丰全球高校菁英挑战赛——编程方向个人题解

A：

遍历所给字符串，按照小写字母、大写字母、数字三种类型分别把字符加到三个字符串上。然后输出。

AC代码

void solve()
{
	string s;
	cin >> s;
	string a, b, c;
	for (auto& i : s)
	{
		if (i >= 'a' && i <= 'z')a += i;
		else if (i >= 'A' && i <= 'Z')b += i;
		else c += i;
	}
	if (a.size())cout << a << endl;
	if (b.size())cout << b << endl;
	if (c.size())cout << c << endl;
}

B：

万能的 $S T L$ 。

用一个 $u n o r d e r e d_{m} a p$ 以用户 $I D$ 为 $k e y$ ，以 $v e c t o r < H i s t o r y R e s u l t >$ 为 $v a l$ ，这样就可以把所有的用户的记录都保存下来了，这里起名 $m y m a p$ 。
开一个 $v e c t o r < H i s t o r y R e s u l t >$ 做总的记录表，这里起名 $r e s$ 。
再开一个 $u n o r d e r e d_{m} a p$ 以用户 $I D$ 为 $k e y$ ，以该用户的 $s t a t u s$ 为 $v a l$ ，这里起名 $s t a$ 。

再来是操作：

对于 $q u e r y$ 操作，我们遍历 $r e s$ 的第 $(p a g e N o - 1) * p a g e S i z e + 1$ 到第 $(p a g e N o * p a g e S i z e$ 个元素并存下。
对于 $g e t B y U s e r I d$ 操作，我们根据用户 $I D$ 在 $m y m a p$ 里获取一个用户的全部记录。
对于 $p u n i s h$ 操作，我们先根据用户 $I D$ 在 $s t a$ 里记录的状态和当前处罚等级做比较，如果当前处罚等级小于 $s t a$ 中记录的，就直接返回 $- 1$ ，反之，将这个新记录存入 $m y m a p$ 和 $m y m a p$ 中，同时更新 $s t a$ 里的状态为当前处罚等级。
对于 $r e l i e v e$ 操作，我们先判断用户 $I D$ 在 $s t a$ 里记录的状态是否为 $0$ ，如果为 $0$ ，说明该用户当前没有惩罚，直接返回 $- 1$ ；反之，将这个将这个新记录存入 $m y m a p$ 和 $m y m a p$ 中，同时更新 $s t a$ 里的状态为 $0$ 。

AC代码

class HistoryResult
{
public:
	HistoryResult(int id, int userId, string operatorUserName, int status)
	{
		this->id = id;
		this->userId = userId;
		this->operatorUserName = operatorUserName;
		this->status = status;
	}

	int getId() const
	{
		return id;
	}

	int getUserId() const
	{
		return userId;
	}

	string getOperatorUserName() const
	{
		return operatorUserName;
	}

	int getStatus() const
	{
		return status;
	}

private:
	int id;
	int userId;
	string operatorUserName;
	int status;
};

int cnt = 0;
vector<HistoryResult>res;
unordered_map<int, vector<HistoryResult>>mymap;
unordered_map<int,int>sta;

class Main
{
public:

	/**
	 * 查询处罚记录，记录按照id升序排序
	 *
	 * @param pageNo   第几页
	 * @param pageSize 页数大小
	 * @return 查询结果
	 */
	vector<HistoryResult> query(int pageNo, int pageSize)
	{
		vector<HistoryResult>v;
		int l = (pageNo - 1) * pageSize, r = min(pageNo * pageSize, (int)res.size());
		for (int i = l; i < r; i++)v.push_back(res[i]);

		return v;
	}

	/**
	 * 查询某个用户的处罚记录，记录按照id升序排序
	 *
	 * @param userId 用户
	 * @return 处罚记录
	 */
	vector<HistoryResult> getByUserId(int userId)
	{
		vector<HistoryResult>v;
		for (auto i : mymap[userId])v.push_back(i);

		return v;
	}

	/**
	 * 处罚操作, 如果用户已经有被处罚了，新的处罚不能低于当前处罚等级才能生效
	 *
	 * @param operatorUserName 操作者的名字
	 * @param userId           处罚的用户
	 * @param punishStatus     处罚类型
	 * @return 返回处罚的记录id, 处罚不成功返回-1
	 */
	int punish(string operatorUserName, int userId, int punishStatus)
	{
		if (sta[userId] != 0 && sta[userId] >= punishStatus)
		{
			return -1;
		}
		mymap[userId].push_back(HistoryResult(++cnt, userId, operatorUserName, punishStatus));
		
		sta[userId]=(punishStatus);
		res.push_back(mymap[userId].back());
		return cnt;
	}

	/**
	* 解除当前处罚
	*
	* @param operatorUserName 操作者的名字
	* @param userId           解除处罚的用户
	* @return 如果当前用户正在被处罚中，解除当前处罚，返回处罚记录id，如果用户没有被处罚，返回-1表示解除处罚非法
	*/
	int relieve(string operatorUserName, int userId)
	{
		if (sta[userId]==0)
		{
			return -1;
		}
		mymap[userId].push_back(HistoryResult(++cnt, userId, operatorUserName, 0));
		sta[userId] = 0;
		res.push_back(mymap[userId].back());
		return cnt;
	}
};

C：

注意题目并不保证道路连通。

先讨论走不到 $n$ 的情况：

因为他不会在起点和终点使用魔法（也不会作为魔法的目的地），所以如果地点只有两个，且没有道路连通，必走不到。
又因为不连通，所以如果起点和重点没有与之相连的点，也走不到。

然后就是贪心策略了，答案分为两种，一种是用一次魔法，一种是不用魔法。

不用魔法的用时我们可以通过优先队列优化的 $d i j k s t r a$ 求出。

如果使用魔法，那么最优解当然是先从起点去往一个离他最近的点，再使用魔法传送到离重点最近的点，这样可以让我们少走没用的点。

两个方法的用时取最小值输出即可。

AC代码

const int N = 2e5 + 50, MOD = 1e9 + 7;

vector<int>graph[N];
unordered_map<int, unordered_map<int, int>>mymap;

int st[N], f[N];

void solve()
{
	int n, m, x, u, v, w;
	cin >> n >> m >> x;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v >> w;
		if (!mymap[u].count(v))
		{
			graph[u].push_back(v);
			graph[v].push_back(u);
			mymap[u][v] = w;
			mymap[v][u] = w;
		}
		else
		{
			mymap[u][v] = min(mymap[u][v],w);
			mymap[v][u] = min(mymap[v][u], w);
		}
	}
	if (graph[1].empty() || graph[n].empty())
	{
		cout << -1 << endl;
		return;
	}
	else if (n == 2)
	{

	}
	for (int i = 2; i <= n; i++)f[i] = 1e18;
	priority_queue<PII, vector<PII>, greater<PII>>que;
	que.push({ 0,1 });
	while (!que.empty())
	{
		auto t = que.top();
		que.pop();
		if (st[t.second])continue;
		int idx = t.second;
		st[idx] = 1;
		for (auto& i : graph[idx])
		{
			if (f[i] > f[idx] + mymap[idx][i])
			{
				f[i] = mymap[idx][i] + f[idx];
				que.push({ f[i],i });
			}
		}
	}
	int ans = x, mn = 1e18;
	for (auto& i : graph[1])
	{
		mn = min(mn, mymap[i][1]);
	}
	ans += mn;
	mn = 1e18;
	for (auto& i : graph[n])
	{
		mn = min(mn, mymap[i][n]);
	}
	ans += mn;
	cout << min(ans, f[n]);
}

D:

首先看一看不能完成任务的情况：

因为跨城送货只能是 $B$ 来做，所以如果 $B$ 类快递员的数量小于跨城任务数 $y$ ，则任务无法完成。
因为每个快递员只能送一个货，所以如果两类小哥的数量小于任务总数，则任务无法完成。

剩下的其实就很简单了，还是贪心思想。

我们把两类小哥的工资和满意度以数对的形式分别存在两个数组里，以工资为第一关键字从小到大排，以满意度为第二关键字从大到小排。

然后因为跨城送货只能是 $B$ 来做，所以先把前 $y$ 个 $B$ 类小哥派去送跨城，剩下的当作 $A$ 类就行。

然后在剩下的 $A$ 类里取前 $x$ 个派去送，任务结束。

AC代码

vector<PII>A, B;

bool cmp(PII& a, PII& b)
{
	if (a.first != b.first)return a.first < b.first;
	return a.second > b.second;
}

void solve()
{
	char c;
	int n, x, y, u, w;
	cin >> n >> x >> y;
	for (int i = 1; i <= n; i++)
	{
		cin >> c >> u >> w;
		if (c == 'A')A.push_back({ u,w });
		else B.push_back({ u,w });
	}
	if (y > B.size() || x + y > n)
	{
		cout << -1 << endl;
		return;
	}
	
	sort(B.begin(), B.end(),cmp);
	int res = 0;
	for (int i = 0; i < y; i++)res += B[i].second;
	for (int i = y; i < B.size(); i++)A.push_back(B[i]);
	sort(A.begin(), A.end(),cmp);
	for(int i=0;i<x;i++) res += A[i].second;
	cout << res;
}