Difference between revisions of "2018 ICPC Asia-East Continent Final"

From EOJ Wiki
Jump to navigation Jump to search
 
(31 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
= ECNU Foreigners =
 +
 
== Replay ==
 
== Replay ==
  
 
ultmaster:
 
ultmaster:
  
−
* 没来。
+
* 没来：没怎么看到我会做的题。这一定是因为题目太少了。（甩锅.jpg）
−
* 待更。
+
* 前期一直在 200 多名徘徊。
 +
* 好像不管哪里少 20 分钟都能进顺位五啊？为什么又是这种不尴不尬的位置啊？
 +
* 难得的单线作战。
 +
 
 +
kblack:
 +
 
 +
* 演爆了。
 +
* <del>好像不用女装了？</del>
 +
 
 +
zerol:
 +
 
 +
* kblack 虽然演了，但是多次阻止了惨剧发生，修复了队友。（那么修自己的 bug 容易还是修队友的 bug 容易？）
 +
* 难得来了一次，没有遗憾。（那是假的，随便哪里少一发罚时，kblack 就女装了好吗？）
  
 
== Problem A ==
 
== Problem A ==
Line 15: Line 29:
  
 
Solved by zerol. 02:53 (+1)
 
Solved by zerol. 02:53 (+1)
 +
 +
题意：问一个长度为 200 的 01 串在长为 $10^9$ 的 $|\mu(i)|$ 的数列中第一次出现的位置，或者不存在。
 +
 +
题解：考虑素数的平方的倍数一定是 0，计算答案模 4, 9, 25, 49, 121, 169 的可能的余数，然后 CRT 求出这个数，然后从小到大判断。注意如果可能性太多肯定是无解的（比如全是 0）。
  
 
== Problem D ==
 
== Problem D ==
Line 25: Line 43:
  
 
Solved by kblack. 01:16 (+1)
 
Solved by kblack. 01:16 (+1)
 +
 +
小学数学题，死于式子抄漏。
  
 
== Problem H ==
 
== Problem H ==
Line 35: Line 55:
  
 
Solved by zerol. 01:40 (+)
 
Solved by zerol. 01:40 (+)
 +
 +
题意：初始攻击 A 和攻击增长速率 D 均为 0。每一回合 A 会增加 D，然后选择以下的一种：
 +
 +
1. 造成 $A+a_i$ 伤害。
 +
 +
2. $D$ 增长 $b_i$。
 +
 +
3. $A$ 增长 $c_i$。
 +
 +
求最大能造成的总伤害。
 +
 +
题解：倒着 DP。两维状态，一维是之前增加 D 能对之后攻击造成的贡献次数，一维是增加 A 的贡献。复杂度 $O(n^4)$。
 +
 +
zerol：kblack 送我的题。
  
 
== Problem J ==
 
== Problem J ==
  
 
Solved by zerol & kblack. 04:07 (+3)
 
Solved by zerol & kblack. 04:07 (+3)
 +
 +
题意：求 $\max_{p_i} \min_j \{  \sum_{i=1}^n p_ilcp(s_i, s_j) \}$ 其中 $\sum p_i = 1$，也就是说求一个选后缀的概率分布，使得和某一个后缀的 lcp 的期望的最小值最大。
 +
 +
题解：考虑后缀树，每个后缀结点往根的路径上贡献 $p_i$，然后使得后缀结点到根的路径上的和的最小值最大。后缀自动机建后缀树后树形 dp，求出每棵子树的答案。如果遇到后缀结点直接归 0，否则就是子节点的调和平均，往父节点贡献时加上边权。
 +
 +
zerol: 后缀自动机建后缀树没反向插入（还好被 kblack 看出来了），问题是还能过样例。
  
 
== Problem L ==
 
== Problem L ==
  
 
Solved by zerol. 01:14 (+3)
 
Solved by zerol. 01:14 (+3)
 +
 +
题意：有两种车站，可以花费代价 1 去同一种车站，也可以花费 1 走一条边，问每个点到所有其他点的最短路之和。（保证两两可达）
 +
 +
题解：最大距离不超过 3，并忽略所有同一种车站之间的边。考虑每一个点，到同一种的其他车站代价都是 1。另一种的代价计算然后分两种情况
 +
 +
这个点有度：那么与这个点直接相邻的点代价为 1，否则为 2。
 +
 +
这个点没度：那么另一侧有度的点代价为 2，否则为 3。
 +
 +
zerol：反复确认题意才读懂的。
 +
 +
kblack: 罚时都是我的，自闭签到，为了不女装（逃
 +
 +
= One,Two,Three,AK =
 +
 +
== Replay ==
 +
 +
oxx1108:
 +
 +
* 金牌题就是个暴力
 +
 +
* 唯一一场前期没崩，结果就水了个金
 +
 +
* 勇敢而又错误地去开H，差点提前结束比赛
 +
 +
dreamcloud:
 +
 +
Xiejiadong:
 +
 +
* 抱着 oxx 的大腿，捡了块金牌。
 +
 +
* 西工大真荒凉。女生真少，真是个学习的好地方（并不觉得）。
 +
 +
* 这个H是真的读不懂啊。
 +
 +
* 打题两小时，划水三小时，最后直接躺地上了。
 +
 +
== Problem C ==
 +
 +
Solved by oxx1108. 04:18 (+2)
 +
 +
题意：问一个长度为 200 的 01 串在长为 $10^9$ 的 $|\mu(i)|$ 的数列中第一次出现的位置，或者不存在。
 +
 +
题解：考虑素数的平方的倍数一定是 0，暴力枚举所有答案模 4 * 9 * 25 * 49 的余数，再对于可行的枚举倍数。特判掉0特别多的就没剩多少了。
 +
 +
== Problem D ==
 +
 +
Solved by dreamcloud. 00:10 (+)
 +
 +
== Problem F ==
 +
 +
Solved by oxx1108. 01:21 (+1)
 +
 +
题意：求三维空间一个点到另一个点不经过球的最小距离。
 +
 +
题解：两点和球心画出三角形余弦定理算一下角度就行。
 +
 +
== Problem G ==
 +
 +
Unsolved. (-1)
 +
 +
最后半小时没事干了，随便写写，似乎算法对了？
 +
 +
== Problem I ==
 +
 +
Solved by Xiejiadong & oxx1108. 01:54 (+)
 +
 +
显然dp。
 +
 +
正着推不出来，那就倒着推。
 +
 +
$dp[i][j][k]$表示到$i$回合，已经攻击了$j$次，攻击回合的和为$k$的最大攻击和。
 +
 +
状态数量已经接近$10^8$，$O(1)$转移，要注意常数的优化。
 +
 +
== Problem L ==
 +
 +
Solved by Xiejiadong. 00:34 (+1)
 +
 +
大力讨论。
 +
 +
1.如果这个点的度数为0
 +
 +
* 对面度数为0的点，需要三步
 +
 +
* 对面度数不为0的点，需要两步
 +
 +
* 自己这边除自己以外，需要一步
 +
 +
2.如果这个点的度数不为0
 +
 +
* 对面直接相连的点，需要一步
 +
 +
* 对面不直接相连的点，需要两步
 +
 +
* 自己这边除自己以外，需要一步
 +
 +
不过要注意，给的边，可能是同一边的点，巨坑

Latest revision as of 11:44, 18 December 2018

ECNU Foreigners

Replay

ultmaster:

  • 没来：没怎么看到我会做的题。这一定是因为题目太少了。（甩锅.jpg）
  • 前期一直在 200 多名徘徊。
  • 好像不管哪里少 20 分钟都能进顺位五啊？为什么又是这种不尴不尬的位置啊？
  • 难得的单线作战。

kblack:

  • 演爆了。
  • 好像不用女装了？

zerol:

  • kblack 虽然演了，但是多次阻止了惨剧发生，修复了队友。（那么修自己的 bug 容易还是修队友的 bug 容易？）
  • 难得来了一次，没有遗憾。（那是假的，随便哪里少一发罚时，kblack 就女装了好吗？）

Problem A

Unsolved. (-11)

比赛还剩半小时，无事可做。

Problem C

Solved by zerol. 02:53 (+1)

题意：问一个长度为 200 的 01 串在长为 $10^9$ 的 $|\mu(i)|$ 的数列中第一次出现的位置，或者不存在。

题解：考虑素数的平方的倍数一定是 0，计算答案模 4, 9, 25, 49, 121, 169 的可能的余数，然后 CRT 求出这个数，然后从小到大判断。注意如果可能性太多肯定是无解的（比如全是 0）。

Problem D

Solved by ultmaster. 00:19 (+)

温暖的签到。（被 kblack 抢机了。

Problem F

Solved by kblack. 01:16 (+1)

小学数学题，死于式子抄漏。

Problem H

Unsolved. (-1)

配合演出。

Problem I

Solved by zerol. 01:40 (+)

题意：初始攻击 A 和攻击增长速率 D 均为 0。每一回合 A 会增加 D，然后选择以下的一种：

1. 造成 $A+a_i$ 伤害。

2. $D$ 增长 $b_i$。

3. $A$ 增长 $c_i$。

求最大能造成的总伤害。

题解：倒着 DP。两维状态，一维是之前增加 D 能对之后攻击造成的贡献次数，一维是增加 A 的贡献。复杂度 $O(n^4)$。

zerol：kblack 送我的题。

Problem J

Solved by zerol & kblack. 04:07 (+3)

题意：求 $\max_{p_i} \min_j \{ \sum_{i=1}^n p_ilcp(s_i, s_j) \}$ 其中 $\sum p_i = 1$，也就是说求一个选后缀的概率分布，使得和某一个后缀的 lcp 的期望的最小值最大。

题解：考虑后缀树，每个后缀结点往根的路径上贡献 $p_i$，然后使得后缀结点到根的路径上的和的最小值最大。后缀自动机建后缀树后树形 dp，求出每棵子树的答案。如果遇到后缀结点直接归 0，否则就是子节点的调和平均，往父节点贡献时加上边权。

zerol: 后缀自动机建后缀树没反向插入（还好被 kblack 看出来了），问题是还能过样例。

Problem L

Solved by zerol. 01:14 (+3)

题意：有两种车站，可以花费代价 1 去同一种车站，也可以花费 1 走一条边，问每个点到所有其他点的最短路之和。（保证两两可达）

题解：最大距离不超过 3，并忽略所有同一种车站之间的边。考虑每一个点，到同一种的其他车站代价都是 1。另一种的代价计算然后分两种情况

这个点有度：那么与这个点直接相邻的点代价为 1，否则为 2。

这个点没度：那么另一侧有度的点代价为 2，否则为 3。

zerol：反复确认题意才读懂的。

kblack: 罚时都是我的，自闭签到，为了不女装（逃

One,Two,Three,AK

Replay

oxx1108:

  • 金牌题就是个暴力
  • 唯一一场前期没崩，结果就水了个金
  • 勇敢而又错误地去开H，差点提前结束比赛

dreamcloud:

Xiejiadong:

  • 抱着 oxx 的大腿，捡了块金牌。
  • 西工大真荒凉。女生真少，真是个学习的好地方（并不觉得）。
  • 这个H是真的读不懂啊。
  • 打题两小时，划水三小时，最后直接躺地上了。

Problem C

Solved by oxx1108. 04:18 (+2)

题意：问一个长度为 200 的 01 串在长为 $10^9$ 的 $|\mu(i)|$ 的数列中第一次出现的位置，或者不存在。

题解：考虑素数的平方的倍数一定是 0，暴力枚举所有答案模 4 * 9 * 25 * 49 的余数，再对于可行的枚举倍数。特判掉0特别多的就没剩多少了。

Problem D

Solved by dreamcloud. 00:10 (+)

Problem F

Solved by oxx1108. 01:21 (+1)

题意：求三维空间一个点到另一个点不经过球的最小距离。

题解：两点和球心画出三角形余弦定理算一下角度就行。

Problem G

Unsolved. (-1)

最后半小时没事干了，随便写写，似乎算法对了？

Problem I

Solved by Xiejiadong & oxx1108. 01:54 (+)

显然dp。

正着推不出来，那就倒着推。

$dp[i][j][k]$表示到$i$回合，已经攻击了$j$次，攻击回合的和为$k$的最大攻击和。

状态数量已经接近$10^8$，$O(1)$转移，要注意常数的优化。

Problem L

Solved by Xiejiadong. 00:34 (+1)

大力讨论。

1.如果这个点的度数为0

  • 对面度数为0的点，需要三步
  • 对面度数不为0的点，需要两步
  • 自己这边除自己以外，需要一步

2.如果这个点的度数不为0

  • 对面直接相连的点，需要一步
  • 对面不直接相连的点，需要两步
  • 自己这边除自己以外，需要一步

不过要注意，给的边，可能是同一边的点，巨坑

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=2018_ICPC_Asia-East_Continent_Final&oldid=2359"