今天进行了一次测试，以下是对本次比赛的总结：

T1

题目：

老板开了一家公司，他拿到了今天的打卡记录（按时间顺序）。

对于同一个人的名字：

• 第 1 次出现表示 进公司；
• 第 2 次出现表示 出公司；
• 第 3 次出现再次表示 进公司；
• 以此类推（每出现一次就在“进/出”之间切换）。

老板想知道：在这一天中，最多有多少个人同时在公司上班？

思路：

用map存储每个人的进出情况，key是名字，value是进出情况，然后模拟即可。

T2

题目：

给定一个长度为 n 的整数序列 a1​,a2​,…,an​。
你可以从中选择两个不同的位置 i,j（要求 i=j）。如果 ai​+aj​ 可以表示成 2 的幂（例如 1,2,4,8,16,…），我们就认为这是一种合法的选择。
现在你需要回答：有多少种合法的选择？
说明：选择 (i,j) 与选择 (j,i) 视为同一种选择，即只统计无序对的数量（等价于统计满足 1≤i<j≤n 的对数）。

思路：

因为是两个数相加，所以在输入x的时候只需要寻找之前有多少个与此数相加等于2^n的，也就是寻找前面数字为2^n-x的数量即可。还是使用map，在全部寻找完后，将这个数加进map就可以了。

T3

题目：

给定一个长度为 n 的正整数序列 a1​,a2​,…,an​。
你需要对每个 ai​ 输出：它的所有不同质因数的乘积。
质因数：能整除该正整数的质数。
例如 60 的质因数有 2,3,5，因此对应的质因数乘积为 2×3×5=30。

思路：

这道题首先需要用素数筛来离线筛出质数，然后该怎么找质因数乘积呢？我最开始是将每个数输入进去然后在线处理，将质数遍历一遍找。但即使在做了许多优化后还是TLE了（n,ai<=1*10^6）。一种正确方法是离线处理，在进行素数筛时，便将每个数的质因数乘积都统计出来就可以了。

T4

题目：

给定一个长度为 n 的整数序列 a1​,a2​,…,an​。
你可以从中任选三个数，如果这三个数能凑成一个三角形，我们就认为这是一个三角形选择。
现在问你有多少种三角形选择？需要满足选择的三个数字的下标i<j<k，且ai​,aj​,ak​能组成一个三角形。

思路：

在这里，我使用的是寻找不符合的个数。我将i,j都遍历了，k则使用二分去找>=i+j的位置。因为数据不大，所以卡过去了。
但还有一种方法是先遍历i，然后使用双指针来找j和k，就能省掉二分的logn。

T5

题目：

有一个 n×m 的方格矩阵，每个格子 (i,j) 内都有一个数字 ai,j​。
你需要从左上角 (1,1) 走到右下角 (n,m)。每一步只能走到相邻的格子（上下左右四个方向之一）。
但是你不能走到一个数字与当前格子数字相同的相邻格子。也就是说，如果你当前在 (x,y)，下一步要走到相邻格子 (nx,ny)，必须满足：
a[x,y]​=a[nx,ny​]
请问最少需要走多少步才能到达 (n,m)？如果无法到达，输出 −1。

思路：

裸的BFS。v数组统计一下到达每个位置的最小步数即可。

T6

题目：

动物园里有什么？！！有大象、有老虎、有狮子...
现在有 n 个动物园，每个动物园内都有若干种动物，以及这个动物园的门票价格。
小朋友的钱是有限的，因此你想用最少的钱看遍所有的动物种类。
如果无论怎么买票都无法看全所有动物种类，则输出 −1。

思路：

这道题我是用的二进制。外层是循环选了哪些动物园，内部根据选的动物园来看有没有看满动物以及价格。但时间复杂度会稍微大一点，不过因为数据范围小，依旧是被我卡过去了。

还有一种方法是进行dfs。dfs虽然看上去时间复杂度仍然没变，但中间有很多可以剪枝优化的地方，复杂度相对来说就会低一点。

如果大家有其他想法的，可以补充。