打折机票

对每张票按照出发的时间排序，询问时，二分查找出对应的区间 于是问题转化为经典的 RMQ 模型，可以用线段树或者 Sparse Table 等方法， 注意特判无解的情况。

Note：出题人傻逼的标程输出反了，大家就当做 joke 吧= =）

展胜地的鲤鱼旗

本题 O(n) 的做法很多。

做法一：

考虑平衡的子串一定是 (...)(...)(...) 结构的，一种方法时，从左向右扫一遍， 对于每个左括号 i，尝试匹配一个右括号 pi，（如果没有匹配设 pi 为 -1） 初始每个左括号设为没有被标记，顺序枚举没被标记的有匹配的左括号 i，标记它，然后看 pi+1 位置是不是有匹配的左括号，如果是，标记它，然后重复上述操作，这样得到一系列合法的括号，它们互不相交，但是相连，比如说有k个，那么对应着k*(k+1)/2个平衡的子串。 因为每个括号只会被标记一次，因此复杂度为 O(n)。

方法二，考虑动态规划 F[i] 代表以第 i 个字符为结尾的平衡串个数， 预处理出每个与右括号匹配的左括号 j，如果存在的话， 那么 f[i]=f[j]+1; 复杂度也是 O(n)。

筑地市场

二分答案 + 数位 DP，状态里保存是否有 4 以及是否有 7。 （实际保存是否出现过 4 或者 7 就可以了。。）

扫地机器人的救赎

计算几何中经典的 ESPO 问题（Euclidean shortest path with obstacles） 对于最后的门，则需要考虑三种可能的路径（连接左端点，右端点，以及垂直） 暴力预处理出所有图中的边的复杂度为 O(n3)，（实际每个多边形只会有一个入口，利用这个性质分析的话，可以得到更紧的界）

通过扫描线 + 计较排序，实时计算可行的边的话，可以达到更好的复杂度。 gen 的数据都是逆时针的，但是里面混入的手工的数据我忘记是顺时针还是逆时针了。 所以干脆不限定方向。。。

实际交上来的程序。。跑的结果都不一样。。 （应该是明显错误的）