2017-C04-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(day4board.png)]]

== 流水账 ==
今天开场sub从A开始看，cjb从D开始看，yzc从K开始看，sub发现C是简单数学题，开始签，此时yzc跟cjb讲了K的题意，迅速讨论出来tarjan的做法，准备等sub做完C，此时sub交了一发'''C1y14'''. cjb接手打K的tarjan板子，然后yzc接手写其他部分，最后让cjb把板子调整为双联通分量后'''K1y44'''. cjb开始写E的AC自动机Dp,打完之后过不了样例，打印下来检查，sub上去写H，cjb突然发现板子抄错了，改了之后过了样例交得到一发wa，sub继续，最后'''H1y100'''， 然后yzc接手F，过样例后交了一发wa，cjb和sub讲自己程序，然后发现问题，cjb上机改，此时yzc表示要试一个数据，发现了问题，cjb改完提交，'''E2y113'''，yzc接手后很快就'''F2y115'''. 此时我们凭借题数优势暂时登顶. 然后sub想清楚了B，开始写B，期间一队过了H凭借罚时重回第一. cjb和yzc在场下把所有能开的坑都开了一波，两道概率都只有一点想法，最后两个人决定开一发A，感觉枚举一个折点非常合理，也找到了合适的板子. sub过了样例，交了一发RE，cjb让sub尝试n=1，发现RE，最后sub调整了代码，也加了一些别的可能的corner case，最后'''B2y170'''，又回到了榜首，但是一队205分钟的时候过了D. 最后的两个小时，cjb和yzc合力搞A，sub在考虑D，基本上是双开的情况，交替调试，A过了样例之后wa，最后不停加corner case，但一直在wa，尝试5发，最后发现1折不一定最优，此时剩下15分钟，我们合力协助sub调试D，但始终过不了样例，最后比赛结束，因为罚时排在了rk2. 后面两个小时没有过题，这是需要反思的地方. 但今天前中期还是比较平均的，手速还要加油.
== 总结 ==
=== chenjb ===
今天似乎没有什么可以总结的，今天的操作应该还行吧，前中后都没有出什么的问题，基本按照此前的计划和经验进行，于是就暴露了我们队菜的本色了，我的AC自动机dp因为自己的失误wa了一发，打得也不够快，还要加油，我们后两个小时A和D都没开出来实在是太可惜了，I的高斯消元居然看错了m的范围，本来还是可以一想的....所以菜啊，个人实力要提高，用力训练用力训练吧..
=== oipotato ===
今天我们队的整体情况大概就是菜吧。前期签到题莫名wa，读题太慢导致在前期积累了太多的罚时劣势，导致虽然中期一度登顶还是被屡屡超过。后期感觉很稳的A题D题，A题由于太naive一个错误结论改到了最后才发现了致命反例，D题很清楚的DPsub学长也没能搞出来，我们也没能帮他想清楚各种细节，错失了最后翻盘登顶的机会。今天的训练其实没有什么大失误吧，终究只是太菜，以后用力训练就是了。
=== subconscious  ===
今天的配合没出现大的失误,从签到到后期A题比较顺利,中期出现的空档主要还是代码能力不足,导致罚时爆炸.后期主要是我在写D题时给出了A题一个错误结论,A题炸裂后我的D题方程不断出错,且实际转移比较混乱,在考场上意识模糊,没有调出来,因此出现了后期乏力的情况.
== 题解 ==
 * A：A题大致思路就是从终点出发，倒着添加机械臂，每一次维护离终点的半径的范围（一个圆环），然后从起点倒着走回来，如果走不到现在要求的范围内，就尽可能接近要求的范围。
         yzc写代码的时候搞过的一些细节：[[BR]]
         1.一个点在圆环内圆里面时，如果和圆心的距离<内圆半径-机械臂长度，就要朝着和圆心相反方向走，不然就朝着圆心走[[BR]]
         2.如果只有一条边并且要求回原点，那直接往终点走会出现不存在方向就会re或者wa，然后我傻傻的给终点扰动了1e-6的坐标，避过了这种情况，但是让自己在后面的判断中多了一些加加减减eps的操作，A了之后想想应该只用特判一条边回原点这一种情况就好了[[BR]]
         3.可能出现新出现的机械臂大于现在要求的范围的外圆的情况，对于新的范围的内圆就不能再是原来的内圆半径-机械臂长度了（可能先半径排个序就不会有这种情况）
 * D：显然只存在四种不同的球,状态可以表示成a[i][j][k]代表只有A,只有B,AB都有三种球各出现了多少种,概率dp,统计边上总期望即可.
 * I：因为边数很少，所以我们可以利用得到的日记列出模13意义下的方程组，因为实际上题目保证唯一解，所以直接上高斯消元(除号变成逆元，处处取模....)，然后得到每条边的长度，跑最短路径即可.
 * J：注意到最优解中挑战者选取不同数字获胜的概率应该是相同的,因此可以每次计算出选取不同数字的获胜概率,然后不断调整.计算胜率可以容斥,调整部分乱搞即可.
== 补题 ==
 * A(√)
 * D(√)
 * I(√)
 * J(√)

流水账

今天开场sub从A开始看，cjb从D开始看，yzc从K开始看，sub发现C是简单数学题，开始签，此时yzc跟cjb讲了K的题意，迅速讨论出来tarjan的做法，准备等sub做完C，此时sub交了一发C1y14. cjb接手打K的tarjan板子，然后yzc接手写其他部分，最后让cjb把板子调整为双联通分量后K1y44. cjb开始写E的AC自动机Dp,打完之后过不了样例，打印下来检查，sub上去写H，cjb突然发现板子抄错了，改了之后过了样例交得到一发wa，sub继续，最后H1y100， 然后yzc接手F，过样例后交了一发wa，cjb和sub讲自己程序，然后发现问题，cjb上机改，此时yzc表示要试一个数据，发现了问题，cjb改完提交，E2y113，yzc接手后很快就F2y115. 此时我们凭借题数优势暂时登顶. 然后sub想清楚了B，开始写B，期间一队过了H凭借罚时重回第一. cjb和yzc在场下把所有能开的坑都开了一波，两道概率都只有一点想法，最后两个人决定开一发A，感觉枚举一个折点非常合理，也找到了合适的板子. sub过了样例，交了一发RE，cjb让sub尝试n=1，发现RE，最后sub调整了代码，也加了一些别的可能的corner case，最后B2y170，又回到了榜首，但是一队205分钟的时候过了D. 最后的两个小时，cjb和yzc合力搞A，sub在考虑D，基本上是双开的情况，交替调试，A过了样例之后wa，最后不停加corner case，但一直在wa，尝试5发，最后发现1折不一定最优，此时剩下15分钟，我们合力协助sub调试D，但始终过不了样例，最后比赛结束，因为罚时排在了rk2. 后面两个小时没有过题，这是需要反思的地方. 但今天前中期还是比较平均的，手速还要加油.

总结

chenjb

今天似乎没有什么可以总结的，今天的操作应该还行吧，前中后都没有出什么的问题，基本按照此前的计划和经验进行，于是就暴露了我们队菜的本色了，我的AC自动机dp因为自己的失误wa了一发，打得也不够快，还要加油，我们后两个小时A和D都没开出来实在是太可惜了，I的高斯消元居然看错了m的范围，本来还是可以一想的....所以菜啊，个人实力要提高，用力训练用力训练吧..

oipotato

今天我们队的整体情况大概就是菜吧。前期签到题莫名wa，读题太慢导致在前期积累了太多的罚时劣势，导致虽然中期一度登顶还是被屡屡超过。后期感觉很稳的A题D题，A题由于太naive一个错误结论改到了最后才发现了致命反例，D题很清楚的DPsub学长也没能搞出来，我们也没能帮他想清楚各种细节，错失了最后翻盘登顶的机会。今天的训练其实没有什么大失误吧，终究只是太菜，以后用力训练就是了。

subconscious

今天的配合没出现大的失误,从签到到后期A题比较顺利,中期出现的空档主要还是代码能力不足,导致罚时爆炸.后期主要是我在写D题时给出了A题一个错误结论,A题炸裂后我的D题方程不断出错,且实际转移比较混乱,在考场上意识模糊,没有调出来,因此出现了后期乏力的情况.

题解

• A：A题大致思路就是从终点出发，倒着添加机械臂，每一次维护离终点的半径的范围（一个圆环），然后从起点倒着走回来，如果走不到现在要求的范围内，就尽可能接近要求的范围。

yzc写代码的时候搞过的一些细节：

1.一个点在圆环内圆里面时，如果和圆心的距离<内圆半径-机械臂长度，就要朝着和圆心相反方向走，不然就朝着圆心走

2.如果只有一条边并且要求回原点，那直接往终点走会出现不存在方向就会re或者wa，然后我傻傻的给终点扰动了1e-6的坐标，避过了这种情况，但是让自己在后面的判断中多了一些加加减减eps的操作，A了之后想想应该只用特判一条边回原点这一种情况就好了

3.可能出现新出现的机械臂大于现在要求的范围的外圆的情况，对于新的范围的内圆就不能再是原来的内圆半径-机械臂长度了（可能先半径排个序就不会有这种情况）

• D：显然只存在四种不同的球,状态可以表示成a[i][j][k]代表只有A,只有B,AB都有三种球各出现了多少种,概率dp,统计边上总期望即可.
• I：因为边数很少，所以我们可以利用得到的日记列出模13意义下的方程组，因为实际上题目保证唯一解，所以直接上高斯消元(除号变成逆元，处处取模....)，然后得到每条边的长度，跑最短路径即可.
• J：注意到最优解中挑战者选取不同数字获胜的概率应该是相同的,因此可以每次计算出选取不同数字的获胜概率,然后不断调整.计算胜率可以容斥,调整部分乱搞即可.

补题

• A(√)
• D(√)
• I(√)
• J(√)

附加文件

• day4board.png by chenjb