__故人__

分类

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

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

Working out

分析一个节点到左上，右上，左下，右下的最大值路径是确定的。那么我们考虑见面的点是哪个点。因为见面点是不能计算贡献的，所以我们考虑第一个人和第二个人是分别从哪个方向来的。经过讨论也只有两种可能。枚举每一个点算出值就可以了。时间复杂度为。代码 #include<bits/stdc++.h&...

2020-09-08

3 650

摆渡车

题意安排摆渡车出发的时间，使这些同学的等车时间之和最小。分析一根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么 $$f_i = \min_{j\le i-m} \lbrace f_j+\sum_...

2020-09-07

7 760

牛客IOI周赛18-普及组

分析数据范围很小，可以考虑快排，再通过去重函数一下直接求解。时间复杂度为。也可以开四个变量扫一次得出答案。代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 10...

2020-09-04

5 715

Tree

题意给你一棵树，要你实现两个操作，且强制在线。在新建一个节点链接到原有节点。查询当前节点到根节点有多少个值大于等于的，且路径长度小于一定值。分析如果我们暴力求解。那么插入节点的时间复杂度为，查询操作的时间复杂度为。考虑平衡时间复杂度。因为是没有修改操作的，那么当插入一个...

2020-09-04

1 617

[HEOI2014]南园满地堆轻絮

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

2020-09-03

2 611

MooFest

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

2020-09-03

5 613

选择客栈

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

2020-09-03

2 1023

CF1119F Niyaz and Small Degrees

题意有一个个结点的树，每条边有边权，结点度数就是与之相连的边数量。对于，删掉一些边使每个结点的度数不大于，求出删掉的边的权值和最小值。分析简化问题求解时的问题。考虑，定义为，结点为根子树满足，且与父亲的边是否断掉的最小代价。那么对于一个度数大于的节点，如果...

2020-09-03

3 767

CF161C Abracadabra

题意给你一个字符串的生成方式，求问和的最长公共子序列。第一步时字符串仅包含单个字符在第步中，我们将第步中得到的字符串复制两次，并在这两个串中间插入字母表中的第个字符。分析无论任何时候这个串都是一个回文串，且第步时，回文中心是。那么可以递归构造这两个字符串。...

2020-09-02

2 730