__故人__
__故人__
全部文章
每日一题
CF(8)
UOJ(1)
牛客小白月赛27(10)
算法模板(10)
随笔(20)
题解(117)
归档
标签
去牛客网
登录
/
注册
__故人__的博客
我太菜了/kk
全部文章
/ 每日一题
(共3篇)
[HEOI2014]南园满地堆轻絮
分析 出现了最大值最小这类关键字,一般要考虑二分答案。但首先我们必须考虑答案是否具有单调性。先钦定一个答案 。那么 。如果我们把绝对值符号拆开,这是由两个一次函数构成的,那么对于 。仍满足上式。所以这个是满足单调性的。考虑二分答案,只有两个限制需要考虑。 和 。当没法同时满足两个条件时,返...
2020-09-03
2
611
MooFest
分析 对于 我们非常不好处理,可以考虑 分治。先按 由小到大排序。那么所有右侧的 一定大于左侧。在处理某一层时,再按 排序。这样处理答案就非常方便了。维护一个前缀和和一个后缀和。两个指针移一下。使用快排的时间复杂度为 ,可以在分治过程中归并排序从此复杂度为 。 代码 #include ...
2020-09-03
5
613
选择客栈
分析 如果枚举左右端点复杂度的下界为 。那么只能枚举一个端点,那么对于另一个端点,我们只关心这两个端点中间有没有最低消费不大于 的。如果我们从左向右扫描,我们一定希望这个点越靠右越好,因为这可以影响更多的点对。对于每一个颜色记录上一个同颜色在哪里。那么只需要最小值点出现在 的右边,那么就可以更...
2020-09-03
2
1023