2017-Sp94-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，不久有人过B，yzc上机wa了下来检查代码，sub丢了个L给cjb，cjb上机获得tle。yzc找到B的错误，'''B2y29'''。cjb又上机fix了下L，还是tle，感受了一下算法是错的。yzc上机写K，'''K1y53'''。cjb上机写E，wa了，yzc和sub讨论了F，上机也wa了，之后sub上机D1y65，yzc重新F1y69。之后E wa了好几发，不得已写了对拍，'''E6y147'''。接下来一直在刚J，最后半小时才'''J2y280'''。sub表示会做L，没rush完。
== 总结 ==
=== chenjb ===
E卡了....下次要果断对拍，别的题真的是菜啊，四个半小时才搞出别人一个小时的题目，fuck。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：与某矩形相交的矩形数量等于总矩形数量-x轴上区间不相交的数量-y轴上不相交的数量+均不相交的数量，中间两项直接扫一遍，最后一项是四个数星星，编号用id代替权值，同样可容斥计算，判定合法即可。

 * B：读入的数字告诉我们哪些二进制位可以取1，从高到低统计答案即可。

 * C：二分答案十分自然，关键是如何统计答案，我们考虑以bfs的顺序遍历树。对于当前节点x，取集合s为已遍历的点里所有与x距离小于limit的点，可以证明集合s里任意两点距离小于limit，则集合s里任意两点颜色不同，所以x点的取值为k-|s|，统计答案即可。我们考虑这样证明，考虑任意两点a,b，设c1=lca(x,a),c2=lca(x,b),不妨设dist(root,c1)<=dist(root,c2)。由bfs顺序可得dist(root,b)<=dist(root,x)且dist(c2,b)<=dist(c2,x)，所以dist(a,b)=dist(a,c2)+dist(c2,b)<=dist(a,c2)+dist(c2,x)=dist(a,x)<limit。至于为啥dist(a,b)=dist(a,c2)+dist(c2,b)，只需要分c2=c1和c2!=c1，再加上dist(root,c1)<=dist(root,c2)就可以证明了，dist(a,c2)+dist(c2,x)=dist(a,x)同理，画画图就很清楚了。

 * D：f[i][j]第i次染色结束场上某种颜色的球还剩j个的方案数，最后输出n^2k+1^ - n * f[k][0]。

 * E：两个指针匹配，考虑改掉失配的地方或者前面满足ai>ai-1的地方，处理好corner case即可。

 * F：在地点xi额外计算的方案数等于x和xi-1共有的集合数量，减掉即可。

 * G：先贪心取最左的序列，然后从右往左，只要出现非法的位置就移动答案的最右字母去消掉，a和b都能消掉一个ab，两个指针扫一遍就可以了。

 * H：对于一个区间集合，显然可以选出一个仅有相邻区间才相交的区间集合使得与原集合覆盖的点集相同。在这个结论的基础上做DP即可判定是否可行。DP状态为f[i][j]表示最后两个区间的编号为i，j。

 * I：显然每个点被覆盖的次数分到两个集合中最优，考虑构造这种方案，每次添加或删除点时维护区间的两两匹配，最后染色即可。

 * J：考虑i次操作可完成排序的序列可最多拆分成2^i^的子序列，每个子序列中连续上升，每次取奇数位的子序列放到序列头即可。

 * K：贪心。

 * L：最短m显然不变，考虑次短长度为x，每根最终的棍子长度均要在x到x+m之间，对于每根棍子，可获得最多根号ai个x不能取值的区间，求区间并后取最大合法x直接统计答案即可。

 * M：
== 补题 ==

流水账

开场各自看题，不久有人过B，yzc上机wa了下来检查代码，sub丢了个L给cjb，cjb上机获得tle。yzc找到B的错误，B2y29。cjb又上机fix了下L，还是tle，感受了一下算法是错的。yzc上机写K，K1y53。cjb上机写E，wa了，yzc和sub讨论了F，上机也wa了，之后sub上机D1y65，yzc重新F1y69。之后E wa了好几发，不得已写了对拍，E6y147。接下来一直在刚J，最后半小时才J2y280。sub表示会做L，没rush完。

总结

chenjb

E卡了....下次要果断对拍，别的题真的是菜啊，四个半小时才搞出别人一个小时的题目，fuck。

oipotato

subconscious

题解

  • A：与某矩形相交的矩形数量等于总矩形数量-x轴上区间不相交的数量-y轴上不相交的数量+均不相交的数量，中间两项直接扫一遍，最后一项是四个数星星，编号用id代替权值，同样可容斥计算，判定合法即可。
  • B：读入的数字告诉我们哪些二进制位可以取1，从高到低统计答案即可。
  • C：二分答案十分自然，关键是如何统计答案，我们考虑以bfs的顺序遍历树。对于当前节点x，取集合s为已遍历的点里所有与x距离小于limit的点，可以证明集合s里任意两点距离小于limit，则集合s里任意两点颜色不同，所以x点的取值为k-|s|，统计答案即可。我们考虑这样证明，考虑任意两点a,b，设c1=lca(x,a),c2=lca(x,b),不妨设dist(root,c1)<=dist(root,c2)。由bfs顺序可得dist(root,b)<=dist(root,x)且dist(c2,b)<=dist(c2,x)，所以dist(a,b)=dist(a,c2)+dist(c2,b)<=dist(a,c2)+dist(c2,x)=dist(a,x)
  • D：f[i][j]第i次染色结束场上某种颜色的球还剩j个的方案数，最后输出n2k+1 - n * f[k][0]。
  • E：两个指针匹配，考虑改掉失配的地方或者前面满足ai>ai-1的地方，处理好corner case即可。
  • F：在地点xi额外计算的方案数等于x和xi-1共有的集合数量，减掉即可。
  • G：先贪心取最左的序列，然后从右往左，只要出现非法的位置就移动答案的最右字母去消掉，a和b都能消掉一个ab，两个指针扫一遍就可以了。
  • H：对于一个区间集合，显然可以选出一个仅有相邻区间才相交的区间集合使得与原集合覆盖的点集相同。在这个结论的基础上做DP即可判定是否可行。DP状态为f[i][j]表示最后两个区间的编号为i，j。
  • I：显然每个点被覆盖的次数分到两个集合中最优，考虑构造这种方案，每次添加或删除点时维护区间的两两匹配，最后染色即可。
  • J：考虑i次操作可完成排序的序列可最多拆分成2i的子序列，每个子序列中连续上升，每次取奇数位的子序列放到序列头即可。
  • K：贪心。
  • L：最短m显然不变，考虑次短长度为x，每根最终的棍子长度均要在x到x+m之间，对于每根棍子，可获得最多根号ai个x不能取值的区间，求区间并后取最大合法x直接统计答案即可。
  • M：

补题

附加文件