Difference between revisions of "Training 5: Dynamic Programming"

From EOJ Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Solved by Weaver_zhu.
+
Unsolved.
 
 
Problem from HDU4578.
 
  
 
== Problem B ==
 
== Problem B ==
  
Solved by Xiejiadong.
+
Unsolved.
 
 
Problem form BZOJ1818.
 
 
 
题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。
 
 
 
题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。
 
 
 
于是就是求行和列两两之间的交点个数。
 
 
 
我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。
 
  
 
== Problem C ==
 
== Problem C ==
Line 25: Line 13:
 
== Problem D ==
 
== Problem D ==
  
Solved by Xiejiadong.
+
Unsolved.
 
 
Problem from BZOJ3261.
 
 
 
可持久化字典树。
 
 
 
[[http://xiejiadong.com/?p=436 题解]]
 
  
 
== Problem E ==
 
== Problem E ==
Line 38: Line 20:
  
 
== Problem F ==
 
== Problem F ==
 
Solved by Xiejiadong.
 
 
Problem from Codeforces1080F.
 
 
主席树。
 
 
[[http://xiejiadong.com/?p=531 题解]]
 
 
== Problem G ==
 
  
 
Unsolved.
 
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:17, 12 September 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.