每日归档： 2019年6月12日

题面 典型A* 算法题。 因为估价公式为fx+gx，估价必须小于实际距离，所以用最短路径，就一定小于实际距离。 … 继续阅读题解 P2901 【[USACO08MAR]牛慢跑Cow Jogging】

题面 树状数组求逆序对 先把东边城市排个序，然后求西边城市的逆序对就行了。 考虑到数据范围，本人用的树状数组实 … 继续阅读题解 SP4226 【MSE06H – Japan】

题面 这就是一道求逆序对的模板吧 为了使代码的常数不要太辣鸡，所以要用金坷垃， 呸，要用树状数组。 首先对于树 … 继续阅读题解 UVA10810 【Ultra-QuickSort】

题面 伸展树Splay 把前驱和后继求出来进行比较，累加到ans里后就可以再删去 时间复杂度O（nlogn） … 继续阅读题解 P2286 【[HNOI2004]宠物收养场】

题面 我绝对是Splay的受害者。 代码丑长不说，还特容易毒瘤（身后有一段不得不说的故事） 但还是写出来了呵呵 … 继续阅读题解 P2234 【[HNOI2002]营业额统计】

题面 倍增优化DP：开车旅行 复杂度：O(（N+M）logN) 关键信息： 1.所在城市。 2.已行驶的天数（ … 继续阅读题解 P1081 【开车旅行】

题面 1.因为每个法器是必须拿的，所以说同一种拿法按不同顺序最终反噬值相等 2.既然这道题要取到最小值，所以让 … 继续阅读题解 P5132 【Cozy Glow之拯救小马国】

题面 第一眼看觉得没这么简单，还觉得是dp 后来仔细一看，这就是一道组合数学题 因为只要2个z和一个y就能组成 … 继续阅读题解 luogu P2646 【数数zzy】

第一种解法：O(n^2)算法： 每个数最开始的最长不下降子序列都是1（它自己） 直接从1到n枚举，最长子序列再 … 继续阅读LIS两种解法

1.upper_bound和lower_bound用法 两个函数的用法类似，在一个左闭右开的有序区间里进行二分 … 继续阅读一些比较有用的STL函数（转）整合