__故人__

每日一题

CF(8) UOJ(1) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

全部文章 / 每日一题（共3篇）

[HEOI2014]南园满地堆轻絮

分析出现了最大值最小这类关键字，一般要考虑二分答案。但首先我们必须考虑答案是否具有单调性。先钦定一个答案。那么。如果我们把绝对值符号拆开，这是由两个一次函数构成的，那么对于。仍满足上式。所以这个是满足单调性的。考虑二分答案，只有两个限制需要考虑。和。当没法同时满足两个条件时，返...

2020-09-03

2 478

MooFest

分析对于我们非常不好处理，可以考虑分治。先按由小到大排序。那么所有右侧的一定大于左侧。在处理某一层时，再按排序。这样处理答案就非常方便了。维护一个前缀和和一个后缀和。两个指针移一下。使用快排的时间复杂度为，可以在分治过程中归并排序从此复杂度为。代码 #include ...

2020-09-03

5 476

选择客栈

分析如果枚举左右端点复杂度的下界为。那么只能枚举一个端点，那么对于另一个端点，我们只关心这两个端点中间有没有最低消费不大于的。如果我们从左向右扫描，我们一定希望这个点越靠右越好，因为这可以影响更多的点对。对于每一个颜色记录上一个同颜色在哪里。那么只需要最小值点出现在的右边，那么就可以更...

2020-09-03

2 892