Difference between revisions of "2019 ICPC EC Final"

From EOJ Wiki
Jump to navigation Jump to search
 
(32 intermediate revisions by the same user not shown)
Line 12: Line 12:
  
 
Kilo_5723:
 
Kilo_5723:
 +
 +
* 对自己发挥还算满意,感觉可能还了一点 CCPC-Final 没怎么上机的债。
 +
* 题目很棒,每一道题做出来之后都感觉很妙(尤其是某数论求和形状的“构造题”)。
  
 
Weaver_zhu:
 
Weaver_zhu:
Line 18: Line 21:
  
 
Solved by Kilo_5723. 00:11 (+)
 
Solved by Kilo_5723. 00:11 (+)
 +
 +
题意:求 $(n+1) \times (m+1)$ 的网格里有多少线段的顶点和中点都在网格端点上。
 +
 +
题解:考虑对每个端点枚举中点的位置。$\sum_{i=0}^{n}\sum_{j=0}^{m}\left(2\lfloor\frac{i}{2}\rfloor\lfloor\frac{j}{2}\rfloor+\lfloor\frac{i}{2}\rfloor+\lfloor\frac{j}{2}\rfloor\right)$
  
 
== Problem B ==
 
== Problem B ==
Line 26: Line 33:
  
 
Solved by Kilo_5723. 02:04 (+2)
 
Solved by Kilo_5723. 02:04 (+2)
 +
 +
题意:令 $f(x)$ 在狄利克雷卷积意义下的 $k$ 次幂是 $f^k(x)$,已知 $f^k(i) \mod p$,求 $f(i) \mod p\;(1 \le i \le n)$。
 +
 +
题解:可以发现,$f^k(n)=\sum\prod_{i=1}^k f(a_i)\;(\prod_{i=1}^k a_i = n)$,其中 $a_i \neq 1$ 的 $i$ 最多有 $20$ 个。考虑将 $n$ 拆分为 $m$ 个不为 $1$ 的数的有序拆分方式 $n=\prod_{i=1}^m a_i\;(a_i \neq 1)$,那么每个拆分方式对答案的贡献就是 $C_k^m \cdot \prod_{i=1}^m f(a_i)$。
 +
 +
而 $\prod_{i=1}^m f(a_i)$ 是可以 dp 的。令 $dp_{n,m}=\prod_{i=1}^m f(a_i)$,则:
 +
 +
$$
 +
dp_{n,m}=\begin{cases}
 +
f(n) & (m=1)\\
 +
\sum_{d|n,d\neq 1,d\neq n}f(d)dp_{d,m-1}&(m>1)
 +
\end{cases}
 +
$$
 +
 +
转换一下方程:
 +
 +
$$
 +
\begin{aligned}
 +
f^k(n)&=\sum_{i=1}^{20} C_k^i dp_{n,i}\\
 +
f^k(n)&=k \cdot f(n)+\sum_{i=2}^{20} C_k^i dp_{n,i}\\
 +
f(n)&=\frac{f^k(n)-\sum_{i=2}^{20} C_k^i dp_{n,i}}{k}
 +
\end{aligned}
 +
$$
  
 
== Problem D ==
 
== Problem D ==

Latest revision as of 08:06, 17 December 2019

Replay

Xiejiadong:

  • 达成了 ICPC 整赛季全 Au 成就。
  • 由于某些原因,队伍三个人在三个不同的房间,似乎成了表面队友。
  • Kilo 成功 carry 全场,我全场在梦游。
  • 热身赛看到 dls ,就大概猜到了出题人。
  • 是很不错的一套题目,让我们根本摸不到模板。
  • tlgg 99min 一发过了大模拟太劲了。
  • 好像大家 G 题的大部分时间都用来调输入部分了。我用 getchar 只读入 `-` 和数字,似乎一遍就过去了。

Kilo_5723:

  • 对自己发挥还算满意,感觉可能还了一点 CCPC-Final 没怎么上机的债。
  • 题目很棒,每一道题做出来之后都感觉很妙(尤其是某数论求和形状的“构造题”)。

Weaver_zhu:

Problem A

Solved by Kilo_5723. 00:11 (+)

题意:求 $(n+1) \times (m+1)$ 的网格里有多少线段的顶点和中点都在网格端点上。

题解:考虑对每个端点枚举中点的位置。$\sum_{i=0}^{n}\sum_{j=0}^{m}\left(2\lfloor\frac{i}{2}\rfloor\lfloor\frac{j}{2}\rfloor+\lfloor\frac{i}{2}\rfloor+\lfloor\frac{j}{2}\rfloor\right)$

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 02:04 (+2)

题意:令 $f(x)$ 在狄利克雷卷积意义下的 $k$ 次幂是 $f^k(x)$,已知 $f^k(i) \mod p$,求 $f(i) \mod p\;(1 \le i \le n)$。

题解:可以发现,$f^k(n)=\sum\prod_{i=1}^k f(a_i)\;(\prod_{i=1}^k a_i = n)$,其中 $a_i \neq 1$ 的 $i$ 最多有 $20$ 个。考虑将 $n$ 拆分为 $m$ 个不为 $1$ 的数的有序拆分方式 $n=\prod_{i=1}^m a_i\;(a_i \neq 1)$,那么每个拆分方式对答案的贡献就是 $C_k^m \cdot \prod_{i=1}^m f(a_i)$。

而 $\prod_{i=1}^m f(a_i)$ 是可以 dp 的。令 $dp_{n,m}=\prod_{i=1}^m f(a_i)$,则:

$$ dp_{n,m}=\begin{cases} f(n) & (m=1)\\ \sum_{d|n,d\neq 1,d\neq n}f(d)dp_{d,m-1}&(m>1) \end{cases} $$

转换一下方程:

$$ \begin{aligned} f^k(n)&=\sum_{i=1}^{20} C_k^i dp_{n,i}\\ f^k(n)&=k \cdot f(n)+\sum_{i=2}^{20} C_k^i dp_{n,i}\\ f(n)&=\frac{f^k(n)-\sum_{i=2}^{20} C_k^i dp_{n,i}}{k} \end{aligned} $$

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 03:07 (+1)

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 04:10 (+2)

题意:获得金银铜牌、获得一血、获得全场一血、顽强拼搏都能获得相应的 happiness 。

现在已知其他人的过题时间和错误提交次数,又知道做一道题目所需的时间和或产生的错误提交次数,合理安排做题顺序和时间,使得 happiness 最大。

题解:如果已经确定了自己的做题顺序,显然就只剩下两种情况了:

  • 尽可能快的解决所有题目,显然就是上一道题目结束以后,立即做下一道题目;
  • 为了获得顽强拼搏奖,除了最后一道题目意外,所有题目尽可能快的完成,最后一道题目在其他人的最后一套题目完成的同时完成;

只有 $10$ 道题目,所以可以直接 $10!$ 枚举顺序,然后确定当前方案排名的话,可以通过预处理其他人的排名情况,然后在其中二分。

细节比较多,不过不是很难实现。

Problem H

Solved by Kilo_5723. 04:23 (+6)

Problem I

Unsolved. (-1)

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Solved by Xiejiadong. 00:52 (+1)

题意:求一个 $\{1,2,3,\cdots ,n\}$ 的 subset $A$ 使得价值最大,价值的计算是:

  • 如果 $i\in A$ ,价值加上 $a_i$ ;
  • 如果 $i,j\in A,i,j\ge 2$ 切存在正整数 $k(k>1)$ 满足 $i^k=j$ ,价值减去 $b_j$ 。

题解:显然不同的幂次是几个没有任何关联的划分。

元素最多的划分是 $2$ 的幂次,因为 $n\le 10^5$ ,所以最多只有 $16$ 个。

针对每一个不相干的划分,单独统计他们能够取得的最大价值即可。计算的方式是直接暴力 dfs 。