2017-Sp118-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，不久后cjb上机写B，wa了。发现有人过H，yzc试图上机抄平衡树，cjb劝说yzc使用rope，'''H1y27'''。之后sub上机写G，之后发现要java，cjb改了之后变成wa，检查发现sub读入写反了，修改后'''G2y61'''。之后cjb想到了B的wa原因，'''B2y68'''。yzc想了D的构造，获得wa，sub上机写几何题A，wa。yzc想到了正确的构造，上机'''D2y117'''。之后cjb开出了C，上机敲了个dinic然后让sub继续调A，A wa了很多发，之后sub写了对拍，'''A5y164'''。cjb上机写C，'''C1y189'''。yzc上机写I，wa了之后对拍拍不出来，cjb提出一个corner case，修改之后wa 32，cjb发现yzc进行了错误的哈希，修改后终于'''I6y242'''。最后一个小时sub上机写F，赛后十几分钟才通过。
== 总结 ==
=== chenjb ===
sub的几何和yzc的哈希都花了比正常要多的时间，导致后面第8题和第9题缺时间出，我前期也太浪了去搞B，理论上应该要挤出更多的30min来。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：大力四个顶点和圆心6个点分类讨论，如果有交点返回0即可。

 * B：二分答案T，然后贪心即可，具体贪心就是维护一个前面需要的时间pre，然后优先把坏棺材(C2)给做掉，不行再做(C1)，时刻留着(n-i+1)*t的时间给运输，有个细节就是pre要和i*t取max，不然前面运输时间不够。

 * C：原点向左边的点连流量为2的边，同理右边的点向汇点连流量为2的边，然后对于每个点i，向id[i][c]连流量为1的边，最后对于每条边(x,y,c)，id[x][c]向id[y][c]连流量为1的边，跑最大流，等于2*n即有解。

 * D：构造两个大小为delta+1的完全图，第一个取前k个点，第二个取前lambda个点，连边即可。存在解的条件是k<=lambda<=delta。

 * E：

 * F：记录前7个位置的最小表示法状态，大力dp转移即可，预处理合法性。

 * G：f[i][j]表示目前到第i种球，已经填了j个位置的方案数，dp转移即可，需要BigInteger。

 * H：用rope或平衡树模拟。

 * I：如果开头不是白色，在开头加一块白色，如果结尾不是黑色，在结尾加一块黑色，于是所有的操作都不会新增块数，只会改变相邻两块的长度，用set找到最长长度，维护哈希即可。

 * J：本题只要求拆成大小不为零的两块的方案数。一定是可以横向拉开或纵向拉开，横向拉开每一行黑块连续且白块连续，纵向同理。容斥加上重复的，即组合数结果。高精度即可。

流水账

开场各自看题，不久后cjb上机写B，wa了。发现有人过H，yzc试图上机抄平衡树，cjb劝说yzc使用rope，H1y27。之后sub上机写G，之后发现要java，cjb改了之后变成wa，检查发现sub读入写反了，修改后G2y61。之后cjb想到了B的wa原因，B2y68。yzc想了D的构造，获得wa，sub上机写几何题A，wa。yzc想到了正确的构造，上机D2y117。之后cjb开出了C，上机敲了个dinic然后让sub继续调A，A wa了很多发，之后sub写了对拍，A5y164。cjb上机写C，C1y189。yzc上机写I，wa了之后对拍拍不出来，cjb提出一个corner case，修改之后wa 32，cjb发现yzc进行了错误的哈希，修改后终于I6y242。最后一个小时sub上机写F，赛后十几分钟才通过。

总结

chenjb

sub的几何和yzc的哈希都花了比正常要多的时间，导致后面第8题和第9题缺时间出，我前期也太浪了去搞B，理论上应该要挤出更多的30min来。

oipotato

subconscious

题解

• A：大力四个顶点和圆心6个点分类讨论，如果有交点返回0即可。
• B：二分答案T，然后贪心即可，具体贪心就是维护一个前面需要的时间pre，然后优先把坏棺材(C2)给做掉，不行再做(C1)，时刻留着(n-i+1)*t的时间给运输，有个细节就是pre要和i*t取max，不然前面运输时间不够。
• C：原点向左边的点连流量为2的边，同理右边的点向汇点连流量为2的边，然后对于每个点i，向id[i][c]连流量为1的边，最后对于每条边(x,y,c)，id[x][c]向id[y][c]连流量为1的边，跑最大流，等于2*n即有解。
• D：构造两个大小为delta+1的完全图，第一个取前k个点，第二个取前lambda个点，连边即可。存在解的条件是k<=lambda<=delta。
• E：
• F：记录前7个位置的最小表示法状态，大力dp转移即可，预处理合法性。
• G：f[i][j]表示目前到第i种球，已经填了j个位置的方案数，dp转移即可，需要BigInteger。
• H：用rope或平衡树模拟。
• I：如果开头不是白色，在开头加一块白色，如果结尾不是黑色，在结尾加一块黑色，于是所有的操作都不会新增块数，只会改变相邻两块的长度，用set找到最长长度，维护哈希即可。
• J：本题只要求拆成大小不为零的两块的方案数。一定是可以横向拉开或纵向拉开，横向拉开每一行黑块连续且白块连续，纵向同理。容斥加上重复的，即组合数结果。高精度即可。

附加文件

• 1.png by chenjb