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

From EOJ Wiki
Jump to navigation Jump to search
 
(15 intermediate revisions by 3 users not shown)
Line 13: Line 13:
 
求 $g_m(n)$。
 
求 $g_m(n)$。
  
题解:可以把答案看作每个 $g_m(i)$ 的 $i-1$ 部分的贡献总和,试求每一个 $i-1$ 对 $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)$ 有多少贡献。
  
我们发现,假设 $i-1$ 对 $k$ 的贡献是 $f_i(k) \cdot (i-1) $,则 $f_i(i)=1,f_i(k)= \frac{2}{k-1} \cdot \sum_{j=1}^{k-1} f_i(j) (k>i)$。我们发现,
+
假设 $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}
 
\begin{equation} \begin{aligned}
&f_i(k+1)\\
+
&f_i(k)\\
=&\frac{2}{k} \cdot \sum_{j=i}^{k} f_i(j)\\
+
=&\frac{2}{k} \cdot \sum_{j=0}^{k-1} f_i(j)\\
=&\frac{2}{k} \cdot (f_i(k)+\sum_{j=i}^{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=i}^{k-1}f_i(j)+\sum_{j=i}^{k-1}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=i}^{k-1}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=i}^{k-1}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+2}{k} \cdot f_i(k)
+
=&\frac{k+1}{k} \cdot f_i(k-1) \;\;\;(k-1>i)
 
\end{aligned} \end{equation}
 
\end{aligned} \end{equation}
  
补充:发现了函数中 $i>m$ 的部分可以改写成 $g_m(i)=i-1+\frac{2}{i}\sum_{j=0}^{i-1} g_m(j)$。
+
显然,$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)}$。
 +
当 $n-m$ 较小的时候,可以直接计算。而当 $n>m-3$ 时,我们发现,
 +
 
 +
\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}) \\
 +
=&\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)}{i+1} \\
 +
=&\frac{2 \cdot (n+1)\cdot m }{m+2}-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1} + 2 \cdot (n+1) \cdot \sum_{i=m+3}^{n} \frac{1}{i} \;\;\; (n-m>3)
 +
\end{aligned} \end{equation}
 +
 
 +
其他的部分都可以很容易地求出,问题的难点只剩下了求 $\sum_{i=m+3}^{n} \frac{1}{i+1}$。
 +
 
 +
令 $F(i)=\sum_{i=1}^{n}$,则 $\sum_{i=m+3}^{n} \frac{1}{i}=F(n)-F(m+2)$。我们需要快速求出 $F(i)$。
 +
 
 +
有一个显然的处理方式,就是本地计算出每一个 $F(i)$,然后打出每一个 $F(10^6 \cdot k)$,大小为 $10^3$ 的表。这样对每一个 $F(i)$,我们只需要计算至多 $10^6$ 次逆元,在本题的时间限制中可以被接受。
  
 
== Problem B ==
 
== Problem B ==
Line 46: Line 64:
  
 
Upsolved by Kilo_5723 && Xiejiadong. (-5)
 
Upsolved by Kilo_5723 && Xiejiadong. (-5)
 +
 +
题意:给定 $40$ 个数,问其所有子集的和中 $4$ 出现的次数。
 +
 +
题解:枚举 $4$ 出现的位置。
 +
 +
折半查找。如果 $4$ 出现的位置是 $4\cdot 10^k$,那么对两半的所有数取 $mod 10^{k+1}$ 的值并基数排序,那么对第一半中的每一个数,要找的就是第二半的数中在 $[4\cdot 10^k,5 \cdot 10^k) \cup [14\cdot 10^k,15 \cdot 10^k)$ 的个数。对每一位求和就是答案。
  
 
== Problem D ==
 
== Problem D ==
 +
 +
Unsolved.
 +
 +
== Problem E ==
  
 
Solved by Weaver_zhu. 00:15:48 (+)
 
Solved by Weaver_zhu. 00:15:48 (+)
  
== Problem E ==
+
温暖的签到
 +
 
 +
== Problem F ==
  
 
Solved by Kilo_5723. 04:07:47 (+9)
 
Solved by Kilo_5723. 04:07:47 (+9)
  
== Problem F ==
+
题意:给出 $n$ 个价格,求至少需要多少硬币能表示每个价格。硬币的价值为 $10,20,50,100$。
 +
 
 +
题解:整个队伍盲人签到。
  
Unsolved.
+
除了 $100$ 的硬币最多会选 $4$ 个,枚举就行了,但每个人都写不对。
  
 
== Problem G ==
 
== Problem G ==

Latest revision as of 00:39, 12 September 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)}$。 当 $n-m$ 较小的时候,可以直接计算。而当 $n>m-3$ 时,我们发现,

\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}) \\ =&\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)}{i+1} \\ =&\frac{2 \cdot (n+1)\cdot m }{m+2}-\frac{2 \cdot (n+1) \cdot (n-2)}{n+1} + 2 \cdot (n+1) \cdot \sum_{i=m+3}^{n} \frac{1}{i} \;\;\; (n-m>3) \end{aligned} \end{equation}

其他的部分都可以很容易地求出,问题的难点只剩下了求 $\sum_{i=m+3}^{n} \frac{1}{i+1}$。

令 $F(i)=\sum_{i=1}^{n}$,则 $\sum_{i=m+3}^{n} \frac{1}{i}=F(n)-F(m+2)$。我们需要快速求出 $F(i)$。

有一个显然的处理方式,就是本地计算出每一个 $F(i)$,然后打出每一个 $F(10^6 \cdot k)$,大小为 $10^3$ 的表。这样对每一个 $F(i)$,我们只需要计算至多 $10^6$ 次逆元,在本题的时间限制中可以被接受。

Problem B

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

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

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

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

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

Problem C

Upsolved by Kilo_5723 && Xiejiadong. (-5)

题意:给定 $40$ 个数,问其所有子集的和中 $4$ 出现的次数。

题解:枚举 $4$ 出现的位置。

折半查找。如果 $4$ 出现的位置是 $4\cdot 10^k$,那么对两半的所有数取 $mod 10^{k+1}$ 的值并基数排序,那么对第一半中的每一个数,要找的就是第二半的数中在 $[4\cdot 10^k,5 \cdot 10^k) \cup [14\cdot 10^k,15 \cdot 10^k)$ 的个数。对每一位求和就是答案。

Problem D

Unsolved.

Problem E

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

温暖的签到

Problem F

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

题意:给出 $n$ 个价格,求至少需要多少硬币能表示每个价格。硬币的价值为 $10,20,50,100$。

题解:整个队伍盲人签到。

除了 $100$ 的硬币最多会选 $4$ 个,枚举就行了,但每个人都写不对。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.