2017-Sp61-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc读了A，判定是个小模拟题，打算继续读题，cjb搞定登录后发现D比较短，让yzc先去读D，yzc读了之后没有什么想法，于是cjb让yzc先去写A，过了一会儿发现D被版切了，cjb和sub讨论了下D，得到了做法，换下yzc，'''D1y25'''，yzc继续调试A，'''A1y34'''。sub在研究K，cjb和yzc讨论了下B，yzc提出了一个堆的做法，写了发现有问题，sub给了个分根号讨论的做法，yzc快写完发现根本不用分根号做，不久后'''B1y67'''。sub想好了K，上机写K，不久后wa了一发，yzc此前和cjb讨论了E，yzc上机写E，发现样例过不去，做法有问题下机思考，sub上机改K，'''K2y85'''。cjb和yzc读了几何题H，把题意丢给了sub，sub询问了一个细节，cjb感觉抄个多边形和直线切的板子就好了，不久后'''H1y120'''。cjb提出了另一个几何题I的做法，三个人讨论了一下之后sub上机写I，cjb和yzc研究F的式子，sub wa了2发后'''I3y174'''。期间yzc上机对F做了各种尝试，I过了之后yzc也把式子推好了，只差一步需要优化，cjb和yzc化简成了卷积的形式，但是sub表示不是很能ntt或者fft，yzc决定强行递推。yzc推了式子后上机开始写，cjb想出了E，和sub讨论后确认了做法。yzc下机思考的时候sub上机写E。yzc最后在封榜的时候过了样例，'''F1y242'''。三个人一起研究sub的代码，过了样例后sub因为并查集写错tle了一发，'''E2y254'''。最后三个人一起讨论J，得到了一个做法，cjb上机写J，yzc帮忙补充了一部分，最后RE了两发之后发现yzc对qsort的cmp定义有问题，修改后'''J3y290'''。
== 总结 ==
=== chenjb ===
今天总体打得还行，但是中间F和E做得有点慢，sub犯了点小错误增加了几发罚时，不过封榜后过了3个题，最后rush出了一个题还是挺不错的，要保持。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * J：因为最大流等于最小割，等价于求任意点对最小割，因为度数最大为3，所以答案肯定是0~3，0显然是不连通，1显然是不属于同一强连通分量，关键是如何判断2还是3，我们枚举每一条边，删去后跑双联通tarjan得到belong数组，对于两个点，倘若删去任何一条边他们都属于同一个双连通分量的话，那么他们的最小割就为3(等价于任意删掉两条边，他们依然联通)，剩下的点答案就是2了。
[https://wiki.icpc-camp.org/dreadnought/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20Grand%20Prix%20of%20Europe Dreadnought]
== 补题 ==

流水账

开场各自看题，yzc读了A，判定是个小模拟题，打算继续读题，cjb搞定登录后发现D比较短，让yzc先去读D，yzc读了之后没有什么想法，于是cjb让yzc先去写A，过了一会儿发现D被版切了，cjb和sub讨论了下D，得到了做法，换下yzc，D1y25，yzc继续调试A，A1y34。sub在研究K，cjb和yzc讨论了下B，yzc提出了一个堆的做法，写了发现有问题，sub给了个分根号讨论的做法，yzc快写完发现根本不用分根号做，不久后B1y67。sub想好了K，上机写K，不久后wa了一发，yzc此前和cjb讨论了E，yzc上机写E，发现样例过不去，做法有问题下机思考，sub上机改K，K2y85。cjb和yzc读了几何题H，把题意丢给了sub，sub询问了一个细节，cjb感觉抄个多边形和直线切的板子就好了，不久后H1y120。cjb提出了另一个几何题I的做法，三个人讨论了一下之后sub上机写I，cjb和yzc研究F的式子，sub wa了2发后I3y174。期间yzc上机对F做了各种尝试，I过了之后yzc也把式子推好了，只差一步需要优化，cjb和yzc化简成了卷积的形式，但是sub表示不是很能ntt或者fft，yzc决定强行递推。yzc推了式子后上机开始写，cjb想出了E，和sub讨论后确认了做法。yzc下机思考的时候sub上机写E。yzc最后在封榜的时候过了样例，F1y242。三个人一起研究sub的代码，过了样例后sub因为并查集写错tle了一发，E2y254。最后三个人一起讨论J，得到了一个做法，cjb上机写J，yzc帮忙补充了一部分，最后RE了两发之后发现yzc对qsort的cmp定义有问题，修改后J3y290。

总结

chenjb

今天总体打得还行，但是中间F和E做得有点慢，sub犯了点小错误增加了几发罚时，不过封榜后过了3个题，最后rush出了一个题还是挺不错的，要保持。

oipotato

subconscious

题解

  • J：因为最大流等于最小割，等价于求任意点对最小割，因为度数最大为3，所以答案肯定是0~3，0显然是不连通，1显然是不属于同一强连通分量，关键是如何判断2还是3，我们枚举每一条边，删去后跑双联通tarjan得到belong数组，对于两个点，倘若删去任何一条边他们都属于同一个双连通分量的话，那么他们的最小割就为3(等价于任意删掉两条边，他们依然联通)，剩下的点答案就是2了。

Dreadnought

补题

附加文件