2017-Sp30-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,600px)]]
== 流水账 ==
开场各自看题，cjb很快发现B是签到题，上机写，结果wa了一发，检查了下代码发现傻逼错误，修改后'''B2y8'''. sub上机测试了下F的结论，发现是对的，提交'''F1y18'''. yzc上机写G，写完后wa了，很惊讶，查了很久没看出来，最后cjb发现答案在隐秘的地方说要取模，三人吐血，'''G2y42'''. 之前写G的时候cjb和sub确认了一下H贪心的正确性，在yzc下机检查G的时候cjb上机写H，G过之后不就'''H1y46'''. 接下来三人陷入了短暂的卡题，不久后得出A只需要维护一下异或线性基就可以了，yzc上机写线段树，写了一段时间后获得tle，cjb建议修改成st表，修改后还是tle，zimpha哥哥帮忙把时限改得人道了一些，rejudge获得wa，cjb上机写暴力对拍，找到错后'''A3y109'''. 在yzc写A的时候，cjb思考K，sub思考J。A过了之后sub上机写J，'''J1y132'''. cjb和yzc开了很久K，在sub的提示下想到了基于单调性的解法，yzc上机写K，K wa了之后cjb继续上机写暴力对拍，拍出来找到错误，提交还是wa。cjb重新读了题，惊恐地发现题意错了...三人思考了一会儿之后感觉还是差不多，yzc写完又让cjb改了改暴力，拍过之后才提交，'''K3y198'''. 因为I改大了数据范围，所以莫队并不能过，三个人一起集智开C、E、和I，都没能开出来。sub想写一个贪心去做E，获得wa。cjb坚持开E，在四小时的时候终于提出了比较正确的模型，并上机开始写dinic，yzc清楚模型也加入了建边的思考，三个人在最后20min疯狂调整建边，心态都有点炸裂...最后1min sub提出了最后一个调整，改了之后发现通过了一个非常非常基础的数据，因为只剩下20s，cjb果断提交，在最后12s成功交了上去，返回了AC，'''E2y299'''. 最后8题结束了比赛，实际上如果I是现场的数据，我们也应该能过的，但是就不知道有没有这么好的运气能够在最后1min过掉E，所以8-9题应该也是我们的水平，从罚时上来看今天并不算太顺利。
== 总结 ==
=== chenjb ===
就比较自责了QAQ 这个K读错了题意（虽然真的好坑啊）浪费了队伍很多时间，虽然最后还是做出来了。。。这个E都是因为自己对最小割有点生疏了，不太扎实，最后也有点心态炸裂，还好sub神来一笔让我赶在最后12s提交AC了。。。感觉在去北京前要好好复习下网络流的模型呢。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：st表维护异或线性基，线段树可能会tle。
 * B：排序后贪心取。
 * E：令 d[i]为给出的无向图中节点 i 到节点 0 的最短路的长度。显然有： d[0]=0。 对于任意一条无向边(i,j)，有|d[i]-d[j]|<=1，所以对于已经存在的边，这个条件一定要满足。同时我们可以发现，任何一个d序列，只要满足上述条件，就是合法的，我们只需要找到最优的序列即可。建立源点S，汇点T。将原图中每个节点i拆成n+1个点，f[i][k](0≤k≤n)，令节点f[i][k]表示d[i]>=k。若最小割中，节点f[i][k](在 S 集中,代表满足了d[i]>=k。构图方法如下：[[BR]][[BR]]
           1.S向所有f[i][0]连inf的边，所有f[i][n]向T连inf的边，表示0<=d[i]<n。[[BR]][[BR]]
           2.对于每个节点，f[i][j]向f[i][j+1]连(A[i]-j)^2^的边，割这条边代表将f[i][j+1]归给T，也就是d[i]>=j但是d[i]<j+1，也就是d[i]=j，所以取(A[i]-j)^2^的流量来割。[[BR]][[BR]]
           3.对于1节点，因为要限制d[1]=0，所以特别地让d[1][i]到d[1][i+1]全都连inf的边来避免割掉，相应的，我们要求除了d[1]以外所有d都必须大于1，所以除了1节点，所有d[1][0]向d[1][1]连inf的边来避免割掉（之前连边的时候可以特判掉避免重复连边，但重复连了也不会影响正确性）[[BR]][[BR]]
           4.对于每一条已经存在的边(x,y)，将f[x][i]向f[y][i-1]连inf的边表示不允许这样割，这样会使得这两个点属于两个集合，导致不符合有|d[i]-d[j]|<=1的限制，同理f[y][i]向f[x][i-1]也是如此。[[BR]]
          最后求出最小割即为答案。
 * F：n/(n+m)，sub随意找到了。。。
 * G：xor按位统计即可。
 * H：自左向右贪心取，用线段树维护一下最小值和区间加。
 * I：(只能过10^5^，不能过zimpha哥哥的10^6^)离线询问然后莫队，实际上就是暴力维护有多少段恰好为k的1(1<=k<=10)。
 * J：状压DP
 * K：固定一个L之后，可行的R是一段后缀，L++的时候R是单调的，用线段树维护一下就可以了。
== 补题 ==

流水账

开场各自看题，cjb很快发现B是签到题，上机写，结果wa了一发，检查了下代码发现傻逼错误，修改后B2y8. sub上机测试了下F的结论，发现是对的，提交F1y18. yzc上机写G，写完后wa了，很惊讶，查了很久没看出来，最后cjb发现答案在隐秘的地方说要取模，三人吐血，G2y42. 之前写G的时候cjb和sub确认了一下H贪心的正确性，在yzc下机检查G的时候cjb上机写H，G过之后不就H1y46. 接下来三人陷入了短暂的卡题，不久后得出A只需要维护一下异或线性基就可以了，yzc上机写线段树，写了一段时间后获得tle，cjb建议修改成st表，修改后还是tle，zimpha哥哥帮忙把时限改得人道了一些，rejudge获得wa，cjb上机写暴力对拍，找到错后A3y109. 在yzc写A的时候，cjb思考K，sub思考J。A过了之后sub上机写J，J1y132. cjb和yzc开了很久K，在sub的提示下想到了基于单调性的解法，yzc上机写K，K wa了之后cjb继续上机写暴力对拍，拍出来找到错误，提交还是wa。cjb重新读了题，惊恐地发现题意错了...三人思考了一会儿之后感觉还是差不多，yzc写完又让cjb改了改暴力，拍过之后才提交，K3y198. 因为I改大了数据范围，所以莫队并不能过，三个人一起集智开C、E、和I，都没能开出来。sub想写一个贪心去做E，获得wa。cjb坚持开E，在四小时的时候终于提出了比较正确的模型，并上机开始写dinic，yzc清楚模型也加入了建边的思考，三个人在最后20min疯狂调整建边，心态都有点炸裂...最后1min sub提出了最后一个调整，改了之后发现通过了一个非常非常基础的数据，因为只剩下20s，cjb果断提交，在最后12s成功交了上去，返回了AC，E2y299. 最后8题结束了比赛，实际上如果I是现场的数据，我们也应该能过的，但是就不知道有没有这么好的运气能够在最后1min过掉E，所以8-9题应该也是我们的水平，从罚时上来看今天并不算太顺利。

总结

chenjb

就比较自责了QAQ 这个K读错了题意（虽然真的好坑啊）浪费了队伍很多时间，虽然最后还是做出来了。。。这个E都是因为自己对最小割有点生疏了，不太扎实，最后也有点心态炸裂，还好sub神来一笔让我赶在最后12s提交AC了。。。感觉在去北京前要好好复习下网络流的模型呢。

oipotato

subconscious

题解

• A：st表维护异或线性基，线段树可能会tle。
• B：排序后贪心取。
• E：令 d[i]为给出的无向图中节点 i 到节点 0 的最短路的长度。显然有： d[0]=0。 对于任意一条无向边(i,j)，有|d[i]-d[j]|<=1，所以对于已经存在的边，这个条件一定要满足。同时我们可以发现，任何一个d序列，只要满足上述条件，就是合法的，我们只需要找到最优的序列即可。建立源点S，汇点T。将原图中每个节点i拆成n+1个点，f[i][k](0≤k≤n)，令节点f[i][k]表示d[i]>=k。若最小割中，节点f[i][k](在 S 集中,代表满足了d[i]>=k。构图方法如下：
  
  

1.S向所有f[i][0]连inf的边，所有f[i][n]向T连inf的边，表示0<=d[i]

2.对于每个节点，f[i][j]向f[i][j+1]连(A[i]-j)²的边，割这条边代表将f[i][j+1]归给T，也就是d[i]>=j但是d[i]2的流量来割。

3.对于1节点，因为要限制d[1]=0，所以特别地让d[1][i]到d[1][i+1]全都连inf的边来避免割掉，相应的，我们要求除了d[1]以外所有d都必须大于1，所以除了1节点，所有d[1][0]向d[1][1]连inf的边来避免割掉（之前连边的时候可以特判掉避免重复连边，但重复连了也不会影响正确性）

4.对于每一条已经存在的边(x,y)，将f[x][i]向f[y][i-1]连inf的边表示不允许这样割，这样会使得这两个点属于两个集合，导致不符合有|d[i]-d[j]|<=1的限制，同理f[y][i]向f[x][i-1]也是如此。

最后求出最小割即为答案。

• F：n/(n+m)，sub随意找到了。。。
• G：xor按位统计即可。
• H：自左向右贪心取，用线段树维护一下最小值和区间加。
• I：(只能过10⁵，不能过zimpha哥哥的10⁶)离线询问然后莫队，实际上就是暴力维护有多少段恰好为k的1(1<=k<=10)。
• J：状压DP
• K：固定一个L之后，可行的R是一段后缀，L++的时候R是单调的，用线段树维护一下就可以了。

补题

附加文件

• 1.png by chenjb