Difference between revisions of "Training 5: Dynamic Programming"
Jump to navigation
Jump to search
(Created page with "=== Problem A === 题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$ 题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\l...") |
|||
Line 1: | Line 1: | ||
− | + | == Problem A == | |
− | + | Solved by Weaver_zhu. | |
− | + | Problem from HDU4578. | |
− | + | == Problem B == | |
− | + | Solved by Xiejiadong. | |
− | + | Problem form BZOJ1818. | |
− | + | 题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。 | |
− | + | 题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。 | |
− | + | 于是就是求行和列两两之间的交点个数。 | |
+ | 我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。 | ||
− | + | == Problem C == | |
− | + | Unsolved. | |
− | 题解 | + | == Problem D == |
+ | |||
+ | Solved by Xiejiadong. | ||
+ | |||
+ | Problem from BZOJ3261. | ||
+ | |||
+ | 可持久化字典树。 | ||
+ | |||
+ | [[http://xiejiadong.com/?p=436 题解]] | ||
+ | |||
+ | == Problem E == | ||
+ | |||
+ | Unsolved. | ||
+ | |||
+ | == Problem F == | ||
+ | |||
+ | Solved by Xiejiadong. | ||
+ | |||
+ | Problem from Codeforces1080F. | ||
+ | |||
+ | 主席树。 | ||
+ | |||
+ | [[http://xiejiadong.com/?p=531 题解]] | ||
+ | |||
+ | == Problem G == | ||
+ | |||
+ | Unsolved. | ||
+ | |||
+ | == Problem H == | ||
+ | |||
+ | Solved by Xiejiadong. | ||
+ | |||
+ | Problem from BZOJ3551. | ||
+ | |||
+ | 主席树。 | ||
+ | |||
+ | BZOJ3545和BZOJ3551题目一样,只不过3551要求强制在线。 | ||
+ | |||
+ | 因为我的做法BZOJ3545也是支持在线的,所以就无所谓了。 | ||
+ | |||
+ | [[http://xiejiadong.com/?p=535 题解]] | ||
+ | |||
+ | == Problem I == | ||
+ | |||
+ | Solved by Xiejiadong. | ||
+ | |||
+ | Problem from Codeforces242E. | ||
+ | |||
+ | 看到异或,考虑拆位。 | ||
+ | |||
+ | 维护 $20$ 棵线段树,对于每一位需要维护一个 tag 表示当前有没有置反,维护区间和即可。 | ||
+ | |||
+ | == Problem J == | ||
+ | |||
+ | Unsolved. | ||
+ | |||
+ | == Problem K == | ||
+ | |||
+ | Solved by Xiejiadong. | ||
+ | |||
+ | 主席树。 | ||
+ | |||
+ | 求区间第$k$小数,权值线段树,差分维护。 | ||
+ | |||
+ | 在线段树上二分即可。 |
Revision as of 03:16, 12 September 2019
Problem A
Solved by Weaver_zhu.
Problem from HDU4578.
Problem B
Solved by Xiejiadong.
Problem form BZOJ1818.
题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。
题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。
于是就是求行和列两两之间的交点个数。
我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。
Problem C
Unsolved.
Problem D
Solved by Xiejiadong.
Problem from BZOJ3261.
可持久化字典树。
[题解]
Problem E
Unsolved.
Problem F
Solved by Xiejiadong.
Problem from Codeforces1080F.
主席树。
[题解]
Problem G
Unsolved.
Problem H
Solved by Xiejiadong.
Problem from BZOJ3551.
主席树。
BZOJ3545和BZOJ3551题目一样,只不过3551要求强制在线。
因为我的做法BZOJ3545也是支持在线的,所以就无所谓了。
[题解]
Problem I
Solved by Xiejiadong.
Problem from Codeforces242E.
看到异或,考虑拆位。
维护 $20$ 棵线段树,对于每一位需要维护一个 tag 表示当前有没有置反,维护区间和即可。
Problem J
Unsolved.
Problem K
Solved by Xiejiadong.
主席树。
求区间第$k$小数,权值线段树,差分维护。
在线段树上二分即可。