2022-team8-004

从 Trac 迁移的文章

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

原文章内容如下：

= 概览 =

通过数：6/11 Rank：4/13 dirt: 60%

== Rank和提交情况 ==

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

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

= 流水账 =

双排，但是结果好像还可以，主要是别人发挥不大好。开局E出的有点慢，之后节奏不错，轮流出题。最后H的做法逐渐发现有问题，逐渐打补丁，导致最后代码比较臃肿，不大好调。K庆幸没有卡精度。最后感觉知道H比较简单的写法，没来及写。

= 总结 =

=== xqj： ===
~~这里是总结~~

=== rtx： ===
博弈问题还是要思路更灵活一些。实数运算题不要怕，说不定就没有卡精度（雾）。如果代码的补丁越大越多，越来越臃肿，可以尝试想想有没有更简洁的方法。

=== wch： ===
代码确实应该完全想清楚之后再开始写，不能觉得自己会了就开始rush，不然可能会越来越繁琐，到最后根本调不出来。
如果看完一题题意发现自己不会但是很多人过，可以选择马上和队友讲而不是仔细强行独自坐着思考。

= 题解 =

 * A：

 * B：

 * C：枚举一条射线A[i]->A[j],假如所有的K个标记点都在它的左边，那么把i到j的距离设置为这条线的长度。此后，做一遍Floyd求从i出发回到i的最短路长度，即为所求图形的周长最小值。

 * D：

 * E：一种必胜策略：不管后手干什么，先手总是把后手操作的那一杯水倒入最左边的那一杯。如果后手也是这样做的，那么先手则随便选一杯倒入第一杯。可以发现，如果进行这样的操作，那么总的操作次数是固定的：(n/x)*(x-1)+max(0,n%x-1)，其中x=a/b。那么胜负情况就判出来了。

 * F：

 * G：

 * H：

 * I：考虑点分治，假设当前枚举了一个重心，那么我们只需要考虑经过当前重心的所有合法路径的长度。那么暴力dfs一遍统计一下就好了。

 * J：可以发现，不管决策的顺序如何，每棵子树花费的总时间总是固定的，而且在一棵子树里面花费的时间是连续的一段。那么我们需要做的就是确定访问每棵子树的顺序，使得总代价最小。思考交换相邻两棵子树的顺序造成的代价变化，如果<0就交换，这样排序一遍之后就确定顺序了。

 * K：首先二分中垂线的长度。确定中垂线长度之后，可以用三角函数求出来每个点在多边形里面所需要的旋转角度的区间，假如区间交不是空集，那么当前长度是可以的。

 * L：

 * M：

概览

通过数：6/11 Rank：4/13 dirt: 60%

Rank和提交情况

流水账

双排，但是结果好像还可以，主要是别人发挥不大好。开局E出的有点慢，之后节奏不错，轮流出题。最后H的做法逐渐发现有问题，逐渐打补丁，导致最后代码比较臃肿，不大好调。K庆幸没有卡精度。最后感觉知道H比较简单的写法，没来及写。

总结

xqj：

这里是总结

rtx：

博弈问题还是要思路更灵活一些。实数运算题不要怕，说不定就没有卡精度（雾）。如果代码的补丁越大越多，越来越臃肿，可以尝试想想有没有更简洁的方法。

wch：

代码确实应该完全想清楚之后再开始写，不能觉得自己会了就开始rush，不然可能会越来越繁琐，到最后根本调不出来。

如果看完一题题意发现自己不会但是很多人过，可以选择马上和队友讲而不是仔细强行独自坐着思考。

题解

  • A：
  • B：
  • C：枚举一条射线A[i]->A[j],假如所有的K个标记点都在它的左边，那么把i到j的距离设置为这条线的长度。此后，做一遍Floyd求从i出发回到i的最短路长度，即为所求图形的周长最小值。
  • D：
  • E：一种必胜策略：不管后手干什么，先手总是把后手操作的那一杯水倒入最左边的那一杯。如果后手也是这样做的，那么先手则随便选一杯倒入第一杯。可以发现，如果进行这样的操作，那么总的操作次数是固定的：(n/x)*(x-1)+max(0,n%x-1)，其中x=a/b。那么胜负情况就判出来了。
  • F：
  • G：
  • H：
  • I：考虑点分治，假设当前枚举了一个重心，那么我们只需要考虑经过当前重心的所有合法路径的长度。那么暴力dfs一遍统计一下就好了。
  • J：可以发现，不管决策的顺序如何，每棵子树花费的总时间总是固定的，而且在一棵子树里面花费的时间是连续的一段。那么我们需要做的就是确定访问每棵子树的顺序，使得总代价最小。思考交换相邻两棵子树的顺序造成的代价变化，如果<0就交换，这样排序一遍之后就确定顺序了。
  • K：首先二分中垂线的长度。确定中垂线长度之后，可以用三角函数求出来每个点在多边形里面所需要的旋转角度的区间，假如区间交不是空集，那么当前长度是可以的。
  • L：
  • M：
附加文件