算法组月赛视频讲解

▶ 点击查看讲解视频

T1: 传送门

选择结构

分 $3$ 种情况讨论：

• 不走传送门
• $x\rightarrow y$
• $y\rightarrow x$

T2: 数字魔法

数组

可以先将给定的数组排序，之后对应位置的元素变成1~n即可。我们需要分别统计加的总和以及减的总和，如果这两个相等则有解，否则无解。

T3: 经济危机

枚举、队列

• $60\%$：对员工按照老板设置的价值上限排序，然后按价值从小到大贪心查找黄金能匹配的员工即可，$O(n^2)$
• $100\%$：将员工的劳动价值从小到大排序，然后从小到大枚举价值，如果价值达到了某个员工的最低工资，那么存储员工的最高工资。然后再尝试将该价值的黄金与最高工资的最小值匹配即可。员工的最高工资可用集合或优先队列维护，$O(nlgn)$

T4: 寻宝

BFS

使用 BFS 搜索出所有按照题目要求交替花色的最长路径及其长度(使用并查集也可)。如某条路径中 # 有 $a$ 个，. 有 $b$ 个，则该条路径的贡献即为 $a\times b$