Kick Start 2018

目录

• 1. Product Triplets
• 2. Combining Classes
• 3. Cave Escape

1. Product Triplets

Q：给定一组整数数组，找出满足a*b=c的三元组的个数。
A：

1. 特殊值0,1特殊对待，两个或三个0
2. 数组排序后，如果x<y<z且三者都非零，一定有A[z]>A[x],A[z]>A[y]，所以只要枚举x,y，在[y+1,N]的范围内寻找A[x]*A[y]是否存在即可。

2. Combining Classes

Q：每个班级的分数是([L_i,R_i])，区间内的分数有且只有一个。一共N个班级，有Q个查询，问第K高的分数是多少。
A：

1. 小数据集用二分查找
2. 横坐标是值，纵坐标是个数，算面积
   
   离散化分数，计算数据和，二分查找范围，计算结果。考虑边界问题。

3. Cave Escape

Q: 给一个矩阵，标记为obstacle的点不可以经过，trap的点经过会损失对应的energy。给定起点，终点和初始能量，问经过最优路径从起点到终点剩余的energy最大是多少。
A:
首先，不考虑能量够不够，每个状态直接用DFS/BFS可以得到一个最终能量值(E[s])，这个状态下能够到但是不在状态里的陷阱集合(adjTrap[s])，还有这个状态能不能出去(isAble[s])
这三个东西出来之后就可以DP了，设f为状态s可以取得的最大能量：

• (f[s])初始为-1
• 如果(isAble[s]==true)，那么(f[s]=E[s])
• 接下来遍历(adjTrap[s])里的每一个陷阱i，如果当前能量(E[s])能通过这个陷阱i，那么可以尝试通过，所以状态转移方程为：(f[s] = max(f[s],f[s|(1<<i)]))