2021-team02-003

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team02 返回]

[[Image(Rank.png,1000px)]]



= 概述 =

 solved: 9/11

 rank: ??

= 流水账 =

开场pb，cxt，cy分别签E，I，C，各WA了一发，然后pb和cxt都过了，cy的C一直过不去，后来cxt重写了一遍过去了。

三个人分别开了一会题，剩下BDK。cy和cxt讨论D之后cy上机写D，cxt准备写K，pb在开B，并由于三手题面想了一会假题意。

最后一小时cxt上机写K，pb和cy想B,最后都没有过。（赛后30分钟cy过了B）

= 总结 =

=== pb： ===
最后太困了睡着了，谢罪，如果不睡着和cy讨论一下B可能效果好一点


=== Creatix： ===
自闭了，最后这个 K 我觉得我真的需要大量时间才能给出一个有证明的做法，还要大量时间才能实现出来。熟练度不够。

不过可喜可贺最后我终于给出了一个（自认为）完整的证明。

=== Eden_CY： ===
这场太演了，开场卡C卡了太久，A和D也挂了好几发，贡献大量罚时，如果后期多一点时间B是可以过的。

= 题解 =

 * A：把每个人的不同分数的区间取出来，按权值从大到小丢到线段树，同时查询人数。

 * B：dp的方法:f[i][j]表示i的子树平衡深度为j最少选多少点，按1到n检查能不能加入，加入时更新到根路径的f值。

 * C：从左到右放，优先放在右端点，如果下一段满了就移回去。

 * D：发现v可以去掉，f[i][j]表示到i经过j条边的最短路，用直线y=x*i+f[n][i]建上凸壳，只有在凸壳上的线对应的经过边数是有用的，再倒回去标记哪些点能到达。

 * E：

 * F：

 * G：

 * H：

 * I：

 * J：

 * K：真的有一点点难搞……首先，一定存在一种最有解，使得如果一次跳跃选择了不到d，那么这次一定是卡在右端点。然后，把所有跳跃尽可能往左移。于是，对于这种最优解，我们记所有岛屿的右端点为关键点，容易发现两个关键点之间的转移一定是跳若干个d（可能0步 & 如果某次跳到了岛上，这次视为跳到岛的左端点），然后走一段，然后跳一个d到某个关键点。dp即可。

[/wiki/2021-team02 返回]

概述

solved: 9/11

rank: ??

流水账

开场pb，cxt，cy分别签E，I，C，各WA了一发，然后pb和cxt都过了，cy的C一直过不去，后来cxt重写了一遍过去了。

三个人分别开了一会题，剩下BDK。cy和cxt讨论D之后cy上机写D，cxt准备写K，pb在开B，并由于三手题面想了一会假题意。

最后一小时cxt上机写K，pb和cy想B,最后都没有过。（赛后30分钟cy过了B）

总结

pb：

最后太困了睡着了，谢罪，如果不睡着和cy讨论一下B可能效果好一点

Creatix：

自闭了，最后这个 K 我觉得我真的需要大量时间才能给出一个有证明的做法，还要大量时间才能实现出来。熟练度不够。

不过可喜可贺最后我终于给出了一个（自认为）完整的证明。

Eden_CY：

这场太演了，开场卡C卡了太久，A和D也挂了好几发，贡献大量罚时，如果后期多一点时间B是可以过的。

题解

  • A：把每个人的不同分数的区间取出来，按权值从大到小丢到线段树，同时查询人数。
  • B：dp的方法:f[i][j]表示i的子树平衡深度为j最少选多少点，按1到n检查能不能加入，加入时更新到根路径的f值。
  • C：从左到右放，优先放在右端点，如果下一段满了就移回去。
  • D：发现v可以去掉，f[i][j]表示到i经过j条边的最短路，用直线y=x*i+f[n][i]建上凸壳，只有在凸壳上的线对应的经过边数是有用的，再倒回去标记哪些点能到达。
  • E：
  • F：
  • G：
  • H：
  • I：
  • J：
  • K：真的有一点点难搞……首先，一定存在一种最有解，使得如果一次跳跃选择了不到d，那么这次一定是卡在右端点。然后，把所有跳跃尽可能往左移。于是，对于这种最优解，我们记所有岛屿的右端点为关键点，容易发现两个关键点之间的转移一定是跳若干个d（可能0步 & 如果某次跳到了岛上，这次视为跳到岛的左端点），然后走一段，然后跳一个d到某个关键点。dp即可。
附加文件