Difference between revisions of "2019 Multi-University,HDU Day 9"

From EOJ Wiki
Jump to navigation Jump to search
Line 15: Line 15:
 
题解:可以把答案看作每个 $g_m(i)$ 的 $i-1$ 部分的贡献总和,试求每一个 $i-1$ 对 $g_m(n)$ 有多少贡献。
 
题解:可以把答案看作每个 $g_m(i)$ 的 $i-1$ 部分的贡献总和,试求每一个 $i-1$ 对 $g_m(n)$ 有多少贡献。
  
我们发现,假设 $i-1$ 对 $k$ 的贡献是 $f_i(k) \cdot (i-1) $,则 $f_i(i)=1,f_i(k)= \frac{2}{k} \cdot \sum_{j=i}^{k-1} f_i(j) (k>i)$。我们发现,$f_i(k+1)=\frac{2}{k+1} \cdot \sum_{j=i}^{k} f_i(j)=\frac{2}{k+1} \cdot \sum_{j=i}^{k-1}f_i(j)+f_i(k)=\frac{2}{k+1} \cdot (1+\frac{2}{k}) \cdot \sum_{j=i}^{k-1}f_i(j)$。
+
我们发现,假设 $i-1$ 对 $k$ 的贡献是 $f_i(k) \cdot (i-1) $,则 $f_i(i)=1,f_i(k)= \frac{2}{k} \cdot \sum_{j=i}^{k-1} f_i(j) (k>i)$。我们发现,$f_i(k+1)=\frac{2}{k+1} \cdot \sum_{j=i}^{k} f_i(j)=\frac{2}{k+1} \cdot (f_i(k)+\sum_{j=i}^{k-1}f_i(j))=\frac{2}{k+1} \cdot (1+\frac{2}{k}) \cdot \sum_{j=i}^{k-1}f_i(j)$。
  
 
补充:我们发现函数中 $i>m$ 的部分可以改写成 $g_m(i)=i-1+\frac{2}{i}\sum_{j=0}^{i-1} g_m(j)$。
 
补充:我们发现函数中 $i>m$ 的部分可以改写成 $g_m(i)=i-1+\frac{2}{i}\sum_{j=0}^{i-1} g_m(j)$。

Revision as of 14:45, 19 August 2019

Problem A

Solved by Kilo_5723. 02:16:39 (+)

题意:给出\begin{equation} g_m(i)=\left\{ \begin{aligned} &0&(1 \le i \le m) \\ &i-1+\frac{1}{i}\sum_{j=1}^i(g_m(j-1)+g_m(i-j))&(m<i) \end{aligned} \right. \end{equation} 求 $g_m(n)$。

题解:可以把答案看作每个 $g_m(i)$ 的 $i-1$ 部分的贡献总和,试求每一个 $i-1$ 对 $g_m(n)$ 有多少贡献。

我们发现,假设 $i-1$ 对 $k$ 的贡献是 $f_i(k) \cdot (i-1) $,则 $f_i(i)=1,f_i(k)= \frac{2}{k} \cdot \sum_{j=i}^{k-1} f_i(j) (k>i)$。我们发现,$f_i(k+1)=\frac{2}{k+1} \cdot \sum_{j=i}^{k} f_i(j)=\frac{2}{k+1} \cdot (f_i(k)+\sum_{j=i}^{k-1}f_i(j))=\frac{2}{k+1} \cdot (1+\frac{2}{k}) \cdot \sum_{j=i}^{k-1}f_i(j)$。

补充:我们发现函数中 $i>m$ 的部分可以改写成 $g_m(i)=i-1+\frac{2}{i}\sum_{j=0}^{i-1} g_m(j)$。

Problem B

Solved by Xiejiadong && Kilo_5723. 03:38:23 (+)

题意:给出一些从边界出发的直线,求平面被分割成了几块。

题解:可以对交点分类讨论,因为保证了出发点不会同行也不会同列,所以只有两种交点是有贡献的:

  • + 交点,且贡献为 $1$ ;
  • 」 交点,贡献为 $0.5$ ,且只出现在边界上,共 $4$ 个,贡献为 $1$ 。

所以统计 + 交点个数,+1 就好了,需要区间加,单点询问,直接上树状数组。

Problem C

Upsolved by Kilo_5723 && Xiejiadong. (-5)

Problem D

Solved by Weaver_zhu. 00:15:48 (+)

Problem E

Solved by Kilo_5723. 04:07:47 (+9)

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.