2017-Sp121-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc上了一下A，过了，'''A1y10'''。有人过了J，三个人迅速得出了做法，cjb上机准备了tarjan，之后sub表示要抢K一血，上了K，wa了一发样例后艹过了，'''K2y50'''。cjb给yzc理论了B的正确性，让他上了一下，也过了，'''B1y62'''。cjb和yzc读了G，丢给sub，sub上了一下，'''G2y93'''。cjb觉得F很稳，上了很久，很难过，觉得样例错了就交了一发喜获wa，之后冷静下来发现自己社保了，上了一下就过了，'''F2y145'''。sub和yzc理论完了D，sub上了D，'''D2y169'''。之后让yzc去写H，三个人感觉稳了开始浪，结果yzc写了30min发现根本不行，cjb赶紧上E，tle了两发后就过了，'''E3y224'''。yzc继续上H，感觉不太行，cjb和sub赶紧上J，'''J1y284'''。之后yzc写H，完场9s交了一发，结束后7min获得通过。sub在yzc写H的时候尝试爆C失败，三个人微笑打出GG。
== 总结 ==
=== chenjb ===
让yzc上机写H的时候大意了，应该直接把简单的E给过了，yzc吃到了写递归下降的经验: 如果题目辣鸡就不能递归下降....写F的时候对残余网络的理解sb了，反向边也属于残余网络....md yzc赛后7min过....把自己浪死了fuck
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：根据题意模拟。

 * B：根据两次开关信息得到：有的灯属于某些开关集合，有的灯一定不属于某些开关集合，&起来输出即可。

 * C：dp[i]表示走到i这个点并且保存需要的期望步数，显然答案是dp[n]-1。观察转移式子可以发现i到j这一段的概率积小于0.5时，一定没有i后面的点对j的贡献优，发现i-j之间最多只有70个非1概率就能小于0.5了，于是避开概率为1的点后暴力转移即可。

 * D：显然w确定后每个f[i]取下界，在w变大过程中动态维护f[i]的取值即可。

 * E：二分正方形边长，因为中心在x轴上，直接求出离x轴高度为mid/2的弦横坐标区间，区间求并看是否存在>=mid即可。

 * F：跑出残余网络后S在残余网络上能到的点集合为A，能到达T的点集合为B，A和B显然因为最大流=割而不相交，则变大一定是取那些残余网络上(x,y)，x属于B，y属于A的边。

 * G：容斥，从d天选择k天强制>=x，容斥即可。

 * H：观察发现全局只有两种操作，一种是‘ , ’ 一种是 ‘@’，暴力递归维护即可。

 * I：大力判断两个多边形有没有交线。1，2染色判定显然。每个联通块按照度大小从大到小暴力判定3染色方案即可，注意显然的剪枝。无解输出4。

 * J：tarjan后在dag上单调队列维护多重背包，注意特判强连通分量大小为1的时候是01背包。

 * K：枚举三层的六边形情况，如果每一种情况的中心点在第一次变换和第二次变换的结果相同就是yes，否则no。

 * [https://wiki.icpc.camp/wood-cube/JAG%20Autumn%202014 WoodCube]

流水账

开场各自看题，yzc上了一下A，过了，A1y10。有人过了J，三个人迅速得出了做法，cjb上机准备了tarjan，之后sub表示要抢K一血，上了K，wa了一发样例后艹过了，K2y50。cjb给yzc理论了B的正确性，让他上了一下，也过了，B1y62。cjb和yzc读了G，丢给sub，sub上了一下，G2y93。cjb觉得F很稳，上了很久，很难过，觉得样例错了就交了一发喜获wa，之后冷静下来发现自己社保了，上了一下就过了，F2y145。sub和yzc理论完了D，sub上了D，D2y169。之后让yzc去写H，三个人感觉稳了开始浪，结果yzc写了30min发现根本不行，cjb赶紧上E，tle了两发后就过了，E3y224。yzc继续上H，感觉不太行，cjb和sub赶紧上J，J1y284。之后yzc写H，完场9s交了一发，结束后7min获得通过。sub在yzc写H的时候尝试爆C失败，三个人微笑打出GG。

总结

chenjb

让yzc上机写H的时候大意了，应该直接把简单的E给过了，yzc吃到了写递归下降的经验: 如果题目辣鸡就不能递归下降....写F的时候对残余网络的理解sb了，反向边也属于残余网络....md yzc赛后7min过....把自己浪死了fuck

oipotato

subconscious

题解

  • A：根据题意模拟。
  • B：根据两次开关信息得到：有的灯属于某些开关集合，有的灯一定不属于某些开关集合，&起来输出即可。
  • C：dp[i]表示走到i这个点并且保存需要的期望步数，显然答案是dp[n]-1。观察转移式子可以发现i到j这一段的概率积小于0.5时，一定没有i后面的点对j的贡献优，发现i-j之间最多只有70个非1概率就能小于0.5了，于是避开概率为1的点后暴力转移即可。
  • D：显然w确定后每个f[i]取下界，在w变大过程中动态维护f[i]的取值即可。
  • E：二分正方形边长，因为中心在x轴上，直接求出离x轴高度为mid/2的弦横坐标区间，区间求并看是否存在>=mid即可。
  • F：跑出残余网络后S在残余网络上能到的点集合为A，能到达T的点集合为B，A和B显然因为最大流=割而不相交，则变大一定是取那些残余网络上(x,y)，x属于B，y属于A的边。
  • G：容斥，从d天选择k天强制>=x，容斥即可。
  • H：观察发现全局只有两种操作，一种是‘ , ’ 一种是 ‘@’，暴力递归维护即可。
  • I：大力判断两个多边形有没有交线。1，2染色判定显然。每个联通块按照度大小从大到小暴力判定3染色方案即可，注意显然的剪枝。无解输出4。
  • J：tarjan后在dag上单调队列维护多重背包，注意特判强连通分量大小为1的时候是01背包。
  • K：枚举三层的六边形情况，如果每一种情况的中心点在第一次变换和第二次变换的结果相同就是yes，否则no。
  • WoodCube
附加文件