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：

万能的 $STL$。

• 用一个 $unordere{d}_{m}ap$ 以用户 $ID$ 为 $key$ ，以 $vector<HistoryResult>$ 为 $val$ ，这样就可以把所有的用户的记录都保存下来了，这里起名 $mymap$。
• 开一个 $vector<HistoryResult>$ 做总的记录表，这里起名 $res$。
• 再开一个 $unordere{d}_{m}ap$ 以用户 $ID$ 为 $key$，以该用户的 $status$ 为 $val$ ，这里起名 $sta$。

再来是操作：

• 对于 $query$ 操作，我们遍历 $res$ 的第 $(pageNo-1)\ast pageSize+1$ 到第 $(pageNo\ast pageSize$ 个元素并存下。
• 对于 $getByUserId$ 操作，我们根据用户 $ID$ 在 $mymap$ 里获取一个用户的全部记录。
• 对于 $punish$ 操作，我们先根据用户 $ID$ 在 $sta$ 里记录的状态和当前处罚等级做比较，如果当前处罚等级小于 $sta$ 中记录的，就直接返回 $-1$，反之，将这个新记录存入 $mymap$ 和 $mymap$ 中，同时更新 $sta$ 里的状态为当前处罚等级。
• 对于 $relieve$ 操作，我们先判断用户 $ID$ 在 $sta$ 里记录的状态是否为 $0$，如果为 $0$，说明该用户当前没有惩罚，直接返回 $-1$；反之，将这个将这个新记录存入 $mymap$ 和 $mymap$ 中，同时更新 $sta$ 里的状态为 $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$ 的情况：

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

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

不用魔法的用时我们可以通过优先队列优化的 $dijkstra$ 求出。

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

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

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;
}