Difference between revisions of "Training 5: Dynamic Programming"

From EOJ Wiki
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 ===
+
== Problem A ==
  
题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$
+
Solved by Weaver_zhu.
  
题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}i \times j[gcd(i,j)=k]$ 然后莫比乌斯反演得$\sum\limits_{k=1}^{n}mu[i] \times (1+...+\frac{n}{k}) \times (1+...+\frac{m}{k})$ 然后数论分块求和
+
Problem from HDU4578.
  
=== Problem B ===
+
== Problem B ==
  
题意: 求第$n$个不是完全平方数的正整数倍的数
+
Solved by Xiejiadong.
  
题解: 考虑容斥求出$n$以内有多少是完全平方倍数,枚举平方因子$i$贡献为$mu[i] \times n/(i*i)$因此二分每趟是$O(sqrt(n))$的,复杂度绰绰有余。
+
Problem form BZOJ1818.
  
=== Problem C ===
+
题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。
  
题意: $\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | i, k | j且\sum k \le a]$
+
题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。
  
题解:这道题想爆。$=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | gcd(i,j)且\sum k \le a]$先考虑没有$\le a$的情况。$f(i)$表示$i$的因数和。$g(n)=\sum\limits_{n|d}mu[d/n] \cdot \frac{n}{d} \cdot \frac{m}{d}$表示$gcd(i,j)=n$的个数。原式=$\sum\limits_{i=1}^{n}f(i)g(i)=\sum\limits_{i=1}^{n}f(i)\sum\limits_{i|d}mu[d/i] \cdot \frac{n}{d} \frac{m}{d}=\sum\limits_{d=1}^{n}\frac{n}{d}\frac{m}{d}\sum\limits_{i|d}f(i)mu[d/i]$。为了数论分块搞这个式子我们需要$F(i)$的前缀和。记$F(i)=f*mu$。只有当$f(i) \le a$时对答案做出贡献。然后就是离线操作,每次把新符合条件的$f(i)$枚举倍数新加到维护$F(i)$前缀和的树状数组中,然后再数论分块求和。复杂度$O(sqrt{(n)}logn+nsqrt{(n)})$
+
于是就是求行和列两两之间的交点个数。
  
 +
我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。
  
=== Problem D ===
+
== Problem C ==
  
题意: 给出$a_i$求有多少$b_i \le a_i$使得任意区间$gcd \ge 2$
+
Unsolved.
  
题解:这道题当时多校补题的时候想爆。考虑容斥求出整个$gcd=k$的情况数$F(k)$,然后答案为$\sum\limits_{i=2}^{k}F(i)$。发现$G(k)=\prod\limits_{i=1}^{n}{a_i/k}$是容斥中对应$gcd>=k$的式子,且$k$包含奇数素因子为正,偶数为负,发现其和莫比乌斯函数刚好是相反关系。(个人理解莫比乌斯函数就是整除偏序上的容斥)。每一次计算都一个一个值算$G(k)$太蠢了。应该将$a_i$转换成$cnt[a_i]++$再使用前缀和,然后一段一段加,每段长度为$i$,这样相同段的$n/i$都是一样的。复杂度就是那个著名的级数$O(nlogn)$了。
+
== 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$小数,权值线段树,差分维护。

在线段树上二分即可。