Difference between revisions of "2019 Multi-University,HDU Day 9"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 29: | Line 29: | ||
显然，$f_i(k)=f_i(i+1) \cdot \prod_{j=i+2}^{k}\frac{j+1}{j}=\frac{2}{i+1} \cdot \frac{k+1}{i+2}=\frac{2 \cdot (k+1)}{(i+1)\cdot(i+2)}$，因此 $g_m(i)$ 的 $i-1$ 对 $g_m(k)$ 的贡献是 $\frac{2 \cdot (k+1) \cdot (i-1)}{(i+1)\cdot(i+2)}$。 | 显然，$f_i(k)=f_i(i+1) \cdot \prod_{j=i+2}^{k}\frac{j+1}{j}=\frac{2}{i+1} \cdot \frac{k+1}{i+2}=\frac{2 \cdot (k+1)}{(i+1)\cdot(i+2)}$，因此 $g_m(i)$ 的 $i-1$ 对 $g_m(k)$ 的贡献是 $\frac{2 \cdot (k+1) \cdot (i-1)}{(i+1)\cdot(i+2)}$。 | ||
| − | + | 现在，若 $n=m$ 答案显然为 $0$，而若 $n>m$，我们要求的是 $[m+1,n-1]$ 中所有数对 $g_m(n)$ 的贡献和 $+ n-1$，即 $n-1+\sum_{i=m+1}^{n-1}\frac{2 \cdot (n+1) \cdot (i-1)}{(i+1)\cdot(i+2)}$。我们发现 | |
| + | \begin{equation} \begin{aligned} | ||
| + | &\sum_{i=m+1}^{n-1}\frac{2 \cdot (n+1) \cdot (i-1)}{(i+1)\cdot(i+2)}\\ | ||
| + | =&\sum_{i=m+1}^{n-1}(\frac{2 \cdot (n+1) \cdot (i-1)}{i+1}-\frac{2 \cdot (n+1) \cdot (i-1)}{i+2})\\ | ||
| + | =&\frac{2 \cdot (n+1)\cdot m }{m+2} + (\sum_{i=m+2}^{n-1} \frac{2 \cdot (n+1) \cdot (i-1)}{i+1})-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1}-(\sum_{i=m+1}^{n-2}\frac{2 \cdot (n+1) \cdot (i-1)}{i+2}) \\ | ||
| + | =&\frac{2 \cdot (n+1)\cdot m }{m+2}-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1} + (\sum_{i=m+2}^{n-1} \frac{2 \cdot (n+1) \cdot (i-1)}{i+1})-(\sum_{i=m+2}^{n-1}\frac{2 \cdot (n+1) \cdot (i-2)}{i+1}) \\ | ||
| + | =& (n-m>3) | ||
| + | \end{aligned} \end{equation} | ||
| + | 当 $n-m$ 较小的时候，可以直接计算。 | ||
== Problem B == | == Problem B == | ||
Revision as of 16:21, 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)$。
题解：函数中 $i>m$ 的部分可以改写成 $g_m(i)=i-1+\frac{2}{i}\sum_{j=0}^{i-1} g_m(j)$，可以把答案看作每个 $g_m(i)$ 的 $i-1$ 部分的贡献总和，试求每一个 $i-1$ 对 $g_m(n)$ 有多少贡献。
假设 $g_m(i)$ 的 $i-1$ 对 $g_m(k)$ 的贡献是 $f_i(k) \cdot (i-1) $，则 $f_i(k)=0(k<i),f_i(i)=1,f_i(k)= \frac{2}{k} \cdot \sum_{j=0}^{k-1} f_i(j) (k>i)$。我们发现，
\begin{equation} \begin{aligned} &f_i(k)\\ =&\frac{2}{k} \cdot \sum_{j=0}^{k-1} f_i(j)\\ =&\frac{2}{k} \cdot (f_i(k-1)+\sum_{j=0}^{k-2}f_i(j))\\ =&\frac{2}{k} \cdot (\frac{2}{k-1} \cdot \sum_{j=0}^{k-2}f_i(j)+\sum_{j=0}^{k-2}f_i(j))\\ =&\frac{2}{k} \cdot (1+\frac{2}{k-1}) \cdot \sum_{j=0}^{k-2}f_i(j)\\ =&\frac{2}{k} \cdot \frac{k+1}{k-1} \cdot \frac{k-1}{2} \cdot( \frac{2}{k-1} \cdot \sum_{j=0}^{k-2}f_i(j))\\ =&\frac{k+1}{k} \cdot f_i(k-1) (k-1>i) \end{aligned} \end{equation}
显然，$f_i(k)=f_i(i+1) \cdot \prod_{j=i+2}^{k}\frac{j+1}{j}=\frac{2}{i+1} \cdot \frac{k+1}{i+2}=\frac{2 \cdot (k+1)}{(i+1)\cdot(i+2)}$，因此 $g_m(i)$ 的 $i-1$ 对 $g_m(k)$ 的贡献是 $\frac{2 \cdot (k+1) \cdot (i-1)}{(i+1)\cdot(i+2)}$。
现在，若 $n=m$ 答案显然为 $0$，而若 $n>m$，我们要求的是 $[m+1,n-1]$ 中所有数对 $g_m(n)$ 的贡献和 $+ n-1$，即 $n-1+\sum_{i=m+1}^{n-1}\frac{2 \cdot (n+1) \cdot (i-1)}{(i+1)\cdot(i+2)}$。我们发现 \begin{equation} \begin{aligned} &\sum_{i=m+1}^{n-1}\frac{2 \cdot (n+1) \cdot (i-1)}{(i+1)\cdot(i+2)}\\ =&\sum_{i=m+1}^{n-1}(\frac{2 \cdot (n+1) \cdot (i-1)}{i+1}-\frac{2 \cdot (n+1) \cdot (i-1)}{i+2})\\ =&\frac{2 \cdot (n+1)\cdot m }{m+2} + (\sum_{i=m+2}^{n-1} \frac{2 \cdot (n+1) \cdot (i-1)}{i+1})-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1}-(\sum_{i=m+1}^{n-2}\frac{2 \cdot (n+1) \cdot (i-1)}{i+2}) \\ =&\frac{2 \cdot (n+1)\cdot m }{m+2}-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1} + (\sum_{i=m+2}^{n-1} \frac{2 \cdot (n+1) \cdot (i-1)}{i+1})-(\sum_{i=m+2}^{n-1}\frac{2 \cdot (n+1) \cdot (i-2)}{i+1}) \\ =& (n-m>3) \end{aligned} \end{equation} 当 $n-m$ 较小的时候，可以直接计算。
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.