2017-Sp62-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：2016 MIPT Workshop Warsaw U Contest
 * 现场排名：https://contest.yandex.com/contest/3322/standings/
 * Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7334/standings/
== 流水账 ==
开场各自看题，因为只有一份题，所以拆开了，cjb先读了F，讨论了一下感觉可做，让yzc先上机写，yzc上机写了一会儿感觉不行，就下机思考。dls交了一发J wa了，三人讨论了J，感觉很简单，yzc上机敲了一发获得wa。此时发现有人过了G，三人迅速讨论了G得到了做法，yzc上机写G，wa了一发后获得通过，'''G2y48'''。cjb和sub讨论了J，打算去fix J的代码，改了改还是wa，决定放弃。发现有人过了K，三个人讨论了K，得到了做法，yzc上机写K，'''K1y85'''。发现有人过了I，三个人也讨论了一下，也很快得到了做法，yzc上机'''I1y108'''。之后cjb提出了一个B的做法，和yzc讨论了觉得很靠谱，就上机写了起来，yzc补充了一部分代码，很快过了样例，提交获得wa，cjb造了个数据找到了yzc的bug，改了之后还是wa，决定对拍。yzc上机写了对拍程序，找到了一个算法的bug，修补不了只好暂时放弃。三个人开始讨论B和H，sub期间提出了一个支配者树的B做法，cjb上机敲板子，yzc完善，但是过不了对拍，还是有问题。之后sub提出了F的正确做法，yzc上机'''F2y233'''。之后三个人讨论了B和D，始终得不到很好的做法，最后试图用随机卡B，没有成功。在camp里rk 5，次于thu的两个队、pku 1个队和fdu的wood cube，毛营中排17名。
== 总结 ==
=== chenjb ===
从题数上看，5-6题才算比较满意，和Nightfall以及Wood Cube保持在一个梯度，但是要追赶他们的还有很多，应该拿Nightfall和Wood Cube作为第一个努力的目标。自己感觉整场比赛脑子动得比较多，但是几道图论题最后都没能做出来，B花费了很多时间，用了很多做法，但是比起以前做ASC, sub没有以前那么辛苦，我和yzc都能够在思维上提出东西，这也是一个进步，要继续保持。比赛节奏上，因为大家都做得比较慢，感觉前期要注意读题，比赛中有好几次看到有人过了才去了解题意(这也有我的锅，没读懂...)，另外就是要好好补题啊，感觉这些题确实是能提高我们的水平的。
=== oipotato ===
和强队的差距很明显。赛场上觉得很难的题听完题解后觉得很自然，要找找原因为什么找不到正确的切入点，不能光靠套路做题。
=== subconscious  ===
这场节奏正常的话应该是5题以上的，大量时间花在了最后放弃的题和一些假的签到题上。开题也非常混乱，过程中时有三开和连续换题等奇葩情况，不过最后罚时海星，再次感谢yzc。读题失败导致的问题有点影响心情，本场整体感觉就是被思维题花式吊打，导致作为嘴炮选手的我非常不爽，不过这也是毛子的风格...本场的题确实很好，其实所有题都很可做，接下来也要努力补题啊！
== 题解 ==
 * A：
   * 题意：场上有k个方块，从(m/2,0)点方向为左上角开始弹球，弹球碰撞瞬间转向，同时方块消失，求最少消完所有方块的时间。n<=2e5，m<=2e5，k<=2e5，m奇数，gcd(n,m)=1。
   * 做法：用（x，y，vx，vy）四元组表示状态，通过在无方块时从起点开始到达每个四元组的时间标号，每个方块可以拆成八个四元组，全部丢set里，每次lower_bound到下一个碰撞位置即可。注意有些状态不在同一个同余系内。
 * B：
   * 题意：对于一张有向图，定义a是key point当且仅当所有其他点要不能到它，要不它能到达，求所有的key point，n<=100000,m<=1000000。
   * 做法：强联通分量缩点，然后怼新图跑出一个拓扑序列，考虑i是key point当且仅当它前面的点能到它，同时它能到达后面的点(这部分可以通过将图和拓扑序列取反变成和前一部分一样)，显然我们对于i前面的所有点不保留其连向>i序号的边，那么如果存在一个点没有出边，那么i显然不合法，否则如果所有点都有<=i的出边，根据矛盾性可以证明其充要性，所以直接对于每个点记录其在拓扑序里连出最小的点，扫一遍就好了。
 * D：
   * 题意：给定一个序列，定义序列的子集的顺序以子集的元素和为第一关键字，以所有元素在序列中的下标升序排序后的字典序为第二关键字，求第k小的子集。
   * 做法：对于这类题，一个很自然会想到的做法就是找到一个枚举方法使得能逐渐增大的取到所有方案。于是一开始先把最小值塞进去，每一次扩展时，把最大值改为更大的一个或者直接在原集合中塞进更大的一个，显然这样可以取遍所有的集合。用堆维护这些集合即可，由于每一次更新只会多出1个集合，所以堆中的元素个数只会有k个。
 * E：
  * 题意：对于一张无向图，询问这张图是否有简单环(边和点都不重复经过)？如果有，他们的环长一样吗？如果一样，是多少？简单环的个数有多少？n<=100000,m<=1000000
  * 做法：用'''点双联通分量'''（注意不是边双联通分量)缩点,这样对于每一个双联通分量，如果里面没有度数大于2的点，则是一个简单环，如果有超过两个度数大于2的点，则简单环环长一定不等，对于恰有两个度数大于2的点，我们从一个点dfs到另一个点，直接记录路径长度和条数更新答案即可。
 * H：
   * 题意：对于一张有向图，询问q次，每次求从a到b长度为l且不额外经过a或b的路径数量(不简单)，n<=100,m<=n(n-1)/2,q<=500000。
   * 做法：f1代表a到b长度为l的路径数量，没有额外条件。f2代表a到b长度为l的不额外经过a的路径数量。f3代表从a走回到a长度为l且不经过b的路径数量。f1显然可直接dp求得。枚举最后一次经过a的时间，f2可在f1基础上由f1和f2递推获得。枚举最后一次经过b的时间，f3可在f1基础上由f1和f2递推获得。枚举第一次经过b的时间，ans可在f2基础上由ans和f3递推获得。

 [[BR]] [[BR]]* [https://wiki-nightfall.icpc-camp.org/Day1 Solution by Nightfall]
== 补题 ==
 * ~~A~~ by sub
 * ~~B~~ by cjb
 * C
 * ~~D~~ by yzc
 * ~~E~~  by cjb
 * ~~H~~ by sub
 * J

• 题目来源：2016 MIPT Workshop Warsaw U Contest
• 现场排名：https://contest.yandex.com/contest/3322/standings/
• Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7334/standings/

流水账

开场各自看题，因为只有一份题，所以拆开了，cjb先读了F，讨论了一下感觉可做，让yzc先上机写，yzc上机写了一会儿感觉不行，就下机思考。dls交了一发J wa了，三人讨论了J，感觉很简单，yzc上机敲了一发获得wa。此时发现有人过了G，三人迅速讨论了G得到了做法，yzc上机写G，wa了一发后获得通过，G2y48。cjb和sub讨论了J，打算去fix J的代码，改了改还是wa，决定放弃。发现有人过了K，三个人讨论了K，得到了做法，yzc上机写K，K1y85。发现有人过了I，三个人也讨论了一下，也很快得到了做法，yzc上机I1y108。之后cjb提出了一个B的做法，和yzc讨论了觉得很靠谱，就上机写了起来，yzc补充了一部分代码，很快过了样例，提交获得wa，cjb造了个数据找到了yzc的bug，改了之后还是wa，决定对拍。yzc上机写了对拍程序，找到了一个算法的bug，修补不了只好暂时放弃。三个人开始讨论B和H，sub期间提出了一个支配者树的B做法，cjb上机敲板子，yzc完善，但是过不了对拍，还是有问题。之后sub提出了F的正确做法，yzc上机F2y233。之后三个人讨论了B和D，始终得不到很好的做法，最后试图用随机卡B，没有成功。在camp里rk 5，次于thu的两个队、pku 1个队和fdu的wood cube，毛营中排17名。

总结

chenjb

从题数上看，5-6题才算比较满意，和Nightfall以及Wood Cube保持在一个梯度，但是要追赶他们的还有很多，应该拿Nightfall和Wood Cube作为第一个努力的目标。自己感觉整场比赛脑子动得比较多，但是几道图论题最后都没能做出来，B花费了很多时间，用了很多做法，但是比起以前做ASC, sub没有以前那么辛苦，我和yzc都能够在思维上提出东西，这也是一个进步，要继续保持。比赛节奏上，因为大家都做得比较慢，感觉前期要注意读题，比赛中有好几次看到有人过了才去了解题意(这也有我的锅，没读懂...)，另外就是要好好补题啊，感觉这些题确实是能提高我们的水平的。

oipotato

和强队的差距很明显。赛场上觉得很难的题听完题解后觉得很自然，要找找原因为什么找不到正确的切入点，不能光靠套路做题。

subconscious

这场节奏正常的话应该是5题以上的，大量时间花在了最后放弃的题和一些假的签到题上。开题也非常混乱，过程中时有三开和连续换题等奇葩情况，不过最后罚时海星，再次感谢yzc。读题失败导致的问题有点影响心情，本场整体感觉就是被思维题花式吊打，导致作为嘴炮选手的我非常不爽，不过这也是毛子的风格...本场的题确实很好，其实所有题都很可做，接下来也要努力补题啊！

题解

• A：
  • 题意：场上有k个方块，从(m/2,0)点方向为左上角开始弹球，弹球碰撞瞬间转向，同时方块消失，求最少消完所有方块的时间。n<=2e5，m<=2e5，k<=2e5，m奇数，gcd(n,m)=1。
  • 做法：用（x，y，vx，vy）四元组表示状态，通过在无方块时从起点开始到达每个四元组的时间标号，每个方块可以拆成八个四元组，全部丢set里，每次lower_bound到下一个碰撞位置即可。注意有些状态不在同一个同余系内。
• B：
  • 题意：对于一张有向图，定义a是key point当且仅当所有其他点要不能到它，要不它能到达，求所有的key point，n<=100000,m<=1000000。
  • 做法：强联通分量缩点，然后怼新图跑出一个拓扑序列，考虑i是key point当且仅当它前面的点能到它，同时它能到达后面的点(这部分可以通过将图和拓扑序列取反变成和前一部分一样)，显然我们对于i前面的所有点不保留其连向>i序号的边，那么如果存在一个点没有出边，那么i显然不合法，否则如果所有点都有<=i的出边，根据矛盾性可以证明其充要性，所以直接对于每个点记录其在拓扑序里连出最小的点，扫一遍就好了。
• D：
  • 题意：给定一个序列，定义序列的子集的顺序以子集的元素和为第一关键字，以所有元素在序列中的下标升序排序后的字典序为第二关键字，求第k小的子集。
  • 做法：对于这类题，一个很自然会想到的做法就是找到一个枚举方法使得能逐渐增大的取到所有方案。于是一开始先把最小值塞进去，每一次扩展时，把最大值改为更大的一个或者直接在原集合中塞进更大的一个，显然这样可以取遍所有的集合。用堆维护这些集合即可，由于每一次更新只会多出1个集合，所以堆中的元素个数只会有k个。
• E：
  • • 题意：对于一张无向图，询问这张图是否有简单环(边和点都不重复经过)？如果有，他们的环长一样吗？如果一样，是多少？简单环的个数有多少？n<=100000,m<=1000000
    • 做法：用点双联通分量（注意不是边双联通分量)缩点,这样对于每一个双联通分量，如果里面没有度数大于2的点，则是一个简单环，如果有超过两个度数大于2的点，则简单环环长一定不等，对于恰有两个度数大于2的点，我们从一个点dfs到另一个点，直接记录路径长度和条数更新答案即可。
• H：
  • 题意：对于一张有向图，询问q次，每次求从a到b长度为l且不额外经过a或b的路径数量(不简单)，n<=100,m<=n(n-1)/2,q<=500000。
  • 做法：f1代表a到b长度为l的路径数量，没有额外条件。f2代表a到b长度为l的不额外经过a的路径数量。f3代表从a走回到a长度为l且不经过b的路径数量。f1显然可直接dp求得。枚举最后一次经过a的时间，f2可在f1基础上由f1和f2递推获得。枚举最后一次经过b的时间，f3可在f1基础上由f1和f2递推获得。枚举第一次经过b的时间，ans可在f2基础上由ans和f3递推获得。

* Solution by Nightfall

补题

• A by sub
• B by cjb
• C
• D by yzc
• E by cjb
• H by sub
• J

附加文件

• 1.png by chenjb
• 180130chn.en.pdf by chenjb
• day01editorial.pdf by chenjb