2017-Sp201-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc很快和sub讨论出了A，cjb上机同时在敲凸包板子预备G题，之后yzc上机wa了，查出错误'''A2y32'''。三人试图做B和I无果，sub表示F很可做，需要三、四元环板子，cjb上机敲板子，yzc和sub讨论了C题，决定上机试一试。之后yzc上机写C，wa了之后开始拍，调了好几个bug后发现了counter case，只好放弃。sub上机写F，不小心加了取模'''F2y178'''。I和B已经被板切，没什么想法，后来三个人终于想出了I，cjb和yzc交替作业'''I1y240'''。sub上机写B，半小时后发现做法假了，没办法就GG了。今天rk11，MIT 6题，搞笑网友和jls都是5题，然后6支4题队，学军3题罚时比我们优秀。
== 总结 ==
=== chenjb ===
今天比较难受，B和I都出不出来，I用到了树剖的性质(所有重链头的子树大小是nlogn)，B方向一直不对，最后才想到，sub认为至少还需要1h，而这1h浪费在了我们做C上，调试也花了一定时间，最后才发现做法是不对的，还是要求稳。还有sub把取模看串题这种小错误还是要谨慎一点，重视细节。
=== oipotato ===
沉默(无奈地摇摇头)，sub是猪！
=== subconscious  ===
傻逼，啊算了没什么。
== 题解 ==
 * A：从写spj的角度反向考虑这个问题，第一次使用魔法，一定是从前往后第n个不同的箱子出现的位置，可见一开始球在这个箱子里，这个时候球要被换到另一个箱子，这个箱子是从现在开始往后出现的第n个不同的箱子，按这样做了k次之后，剩下还得把所有箱子都出现一次，才能保证能搜到宝藏。于是我们考虑每一次都把剩余次数最少的箱子安排在最后一个，模拟k轮之后再把所有箱子都询问一遍，如果所有箱子次数都足够，则模拟过程就是方案，否则就是不可能。

 * B：把全0解排除，发现0-8对称，前缀和后可以通过建图维护联通块数量求和，全0的情况可以视为在离散化后相邻两点加一条边，暴力剪枝即可。

 * C：

 * D：

 * E：

 * F：逐次迭代计算长度为1、2、3、4的路径，需要计算从每个点开始3、4元环数量，注意没有取模。

 * G：

 * H：考虑把偶数位置的操作看成-Ai，0号位置操作为X，-1号位置操作为-∞。则我们需要维护的就是更改S或某个Ai，并维护min(S,max(0,x+Ai))的最终状态。如果我们能找到一个i，满足i的结果是0或S，且对于任意j>i，均有j的结果直接是x+Aj,则直接就能求出最终状态。考虑所有满足以下条件的[l,r]区间：abs(Al+...+Ar)>=S，则显然i至少在满足条件的最大的l后面。显然，abs值最大的对应的r就是我们需要的i，用线段树维护即可。

 * I：把合并操作建成一棵树，考虑从每个叶子出发，在log条重链上依次二分，二分的时候暴力把相关信息建图用tarjan判矛盾，因为重链头的子树大小和是nlogn级别的，所以复杂度是两个log的。

流水账

出门各自看题，yzc很快和sub讨论出了A，cjb上机同时在敲凸包板子预备G题，之后yzc上机wa了，查出错误A2y32。三人试图做B和I无果，sub表示F很可做，需要三、四元环板子，cjb上机敲板子，yzc和sub讨论了C题，决定上机试一试。之后yzc上机写C，wa了之后开始拍，调了好几个bug后发现了counter case，只好放弃。sub上机写F，不小心加了取模F2y178。I和B已经被板切，没什么想法，后来三个人终于想出了I，cjb和yzc交替作业I1y240。sub上机写B，半小时后发现做法假了，没办法就GG了。今天rk11，MIT 6题，搞笑网友和jls都是5题，然后6支4题队，学军3题罚时比我们优秀。

总结

chenjb

今天比较难受，B和I都出不出来，I用到了树剖的性质(所有重链头的子树大小是nlogn)，B方向一直不对，最后才想到，sub认为至少还需要1h，而这1h浪费在了我们做C上，调试也花了一定时间，最后才发现做法是不对的，还是要求稳。还有sub把取模看串题这种小错误还是要谨慎一点，重视细节。

oipotato

沉默(无奈地摇摇头)，sub是猪！

subconscious

傻逼，啊算了没什么。

题解

  • A：从写spj的角度反向考虑这个问题，第一次使用魔法，一定是从前往后第n个不同的箱子出现的位置，可见一开始球在这个箱子里，这个时候球要被换到另一个箱子，这个箱子是从现在开始往后出现的第n个不同的箱子，按这样做了k次之后，剩下还得把所有箱子都出现一次，才能保证能搜到宝藏。于是我们考虑每一次都把剩余次数最少的箱子安排在最后一个，模拟k轮之后再把所有箱子都询问一遍，如果所有箱子次数都足够，则模拟过程就是方案，否则就是不可能。
  • B：把全0解排除，发现0-8对称，前缀和后可以通过建图维护联通块数量求和，全0的情况可以视为在离散化后相邻两点加一条边，暴力剪枝即可。
  • C：
  • D：
  • E：
  • F：逐次迭代计算长度为1、2、3、4的路径，需要计算从每个点开始3、4元环数量，注意没有取模。
  • G：
  • H：考虑把偶数位置的操作看成-Ai，0号位置操作为X，-1号位置操作为-∞。则我们需要维护的就是更改S或某个Ai，并维护min(S,max(0,x+Ai))的最终状态。如果我们能找到一个i，满足i的结果是0或S，且对于任意j>i，均有j的结果直接是x+Aj,则直接就能求出最终状态。考虑所有满足以下条件的[l,r]区间：abs(Al+...+Ar)>=S，则显然i至少在满足条件的最大的l后面。显然，abs值最大的对应的r就是我们需要的i，用线段树维护即可。
  • I：把合并操作建成一棵树，考虑从每个叶子出发，在log条重链上依次二分，二分的时候暴力把相关信息建图用tarjan判矛盾，因为重链头的子树大小和是nlogn级别的，所以复杂度是两个log的。
附加文件