2017-Sp239-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，很快读完了所有题，但是没有很能下手的，sub试图推了一下E崩了，转去搞G，'''G2y42'''。然后sub觉得B很简单，去写了，wa了之后感觉存在不能解决的东西(赛后讲题的时候说是不存在的)。之后sub推E，'''E1y118'''。cjb和yzc此前讨论了I，sub闲下来之后帮忙确定了做法，yzc上机用力地写，然后开始RE，cjb叉了一下之后变成了wa。sub推出了F，'''F1y190'''。之后yzc拉屎发现一个重大错误，改了之后变成了RE，尝试了很久，终于找到了问题，结果TLE了，卡了卡常终于'''I10y232'''。之后sub上机写D，cjb和yzc开A，sub写D比计划中快了很多，'''D3y270'''。cjb迅速上机rush Tarjan，yzc跟上补充，过了样例就交，此前让sub准备了几个数据，wa了之后上数据，找到错误马上交，'''A2y284'''。
== 总结 ==
=== chenjb ===
今天屁都没干，队友带着躺赢啊，这不太好啊，还是得努力听听做法，能帮忙早点搞定I就不用这么虚了...还有这个A明明是煞笔题啊，怎么就没有静下心来认真想想啊，明明是唯一一个图论题...cjbsb!!!!还有就是sub以后估计的时候可以再准备多一会儿，希望今天这种意外惊喜多发生，更重要的是以后能够更准确预判。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：剖出环后如果能到达一个>=k的环就能通过它走过所有点，不然就只能到自己能到的点，直接dfs获得。

 * B：显然不能交叉，问题转为区间dp，注意凸包贡献。

 * C：一定有一列是全纵向的或者有一行是全横向的或者有一个旋转中心，旋转中心一定是一条线，其他可以用组合数算出来，前缀和优化运算，O(n^2^).

 * D：拆成线段往x轴投影的梯形求和，每个梯形先讨论矩形部分，再讨论三角形部分，三角形计算是等差数列。

 * E：从0开始编号，可以发现i的答案是i的二进制子集的异或和，高维前缀和或者倍增即可。

 * F：每次考虑最大的，显然要把最大之上其他的移掉，才能移动到B，把其他移掉视为一个子问题，这个子问题变成普通汉诺塔，因此递归即可。

 * G：可以发现是格雷码1的数量，从高向低逐位确定即可。

 * H：f[i][0/1][0/1]表示最低i位，是否有进位，是否需要高位+1产生有效位的状态，分类讨论进行转移。

 * I：有两种情况，一种是AB是两棵子树，另一种是C为根的时候，B在A的子树内，第一种直接枚举C为根即可，第二种枚举A作为根，C是某个儿子，是否存在别的子树里有无满足条件的A，用线段树维护即可。

 * J：二分答案后贪心，考虑第一关键字从小到大枚举，第二关键字是经典贪心，每个要求选尽可能接近的去凑，这样效率是O(m^2^)，所以要通过离散化优化成O(n^2^)，将第一关键字和第二关键字同时离散化，可以划分成方格图，累积统计即可，注意对角线上的点控制区域是一个三角形，用等差数列求和。

流水账

出门各自看题，很快读完了所有题，但是没有很能下手的，sub试图推了一下E崩了，转去搞G，G2y42。然后sub觉得B很简单，去写了，wa了之后感觉存在不能解决的东西(赛后讲题的时候说是不存在的)。之后sub推E，E1y118。cjb和yzc此前讨论了I，sub闲下来之后帮忙确定了做法，yzc上机用力地写，然后开始RE，cjb叉了一下之后变成了wa。sub推出了F，F1y190。之后yzc拉屎发现一个重大错误，改了之后变成了RE，尝试了很久，终于找到了问题，结果TLE了，卡了卡常终于I10y232。之后sub上机写D，cjb和yzc开A，sub写D比计划中快了很多，D3y270。cjb迅速上机rush Tarjan，yzc跟上补充，过了样例就交，此前让sub准备了几个数据，wa了之后上数据，找到错误马上交，A2y284。

总结

chenjb

今天屁都没干，队友带着躺赢啊，这不太好啊，还是得努力听听做法，能帮忙早点搞定I就不用这么虚了...还有这个A明明是煞笔题啊，怎么就没有静下心来认真想想啊，明明是唯一一个图论题...cjbsb!!!!还有就是sub以后估计的时候可以再准备多一会儿，希望今天这种意外惊喜多发生，更重要的是以后能够更准确预判。

oipotato

subconscious

题解

  • A：剖出环后如果能到达一个>=k的环就能通过它走过所有点，不然就只能到自己能到的点，直接dfs获得。
  • B：显然不能交叉，问题转为区间dp，注意凸包贡献。
  • C：一定有一列是全纵向的或者有一行是全横向的或者有一个旋转中心，旋转中心一定是一条线，其他可以用组合数算出来，前缀和优化运算，O(n2).
  • D：拆成线段往x轴投影的梯形求和，每个梯形先讨论矩形部分，再讨论三角形部分，三角形计算是等差数列。
  • E：从0开始编号，可以发现i的答案是i的二进制子集的异或和，高维前缀和或者倍增即可。
  • F：每次考虑最大的，显然要把最大之上其他的移掉，才能移动到B，把其他移掉视为一个子问题，这个子问题变成普通汉诺塔，因此递归即可。
  • G：可以发现是格雷码1的数量，从高向低逐位确定即可。
  • H：f[i][0/1][0/1]表示最低i位，是否有进位，是否需要高位+1产生有效位的状态，分类讨论进行转移。
  • I：有两种情况，一种是AB是两棵子树，另一种是C为根的时候，B在A的子树内，第一种直接枚举C为根即可，第二种枚举A作为根，C是某个儿子，是否存在别的子树里有无满足条件的A，用线段树维护即可。
  • J：二分答案后贪心，考虑第一关键字从小到大枚举，第二关键字是经典贪心，每个要求选尽可能接近的去凑，这样效率是O(m2)，所以要通过离散化优化成O(n2)，将第一关键字和第二关键字同时离散化，可以划分成方格图，累积统计即可，注意对角线上的点控制区域是一个三角形，用等差数列求和。
附加文件