2017-Sp291-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,800px)]]

== 流水账 ==
=== chenjb ===
这场的D本该过的，被hdu莫名其妙的输出小数位数搞了很神秘；yzc的构造只差一点点了，感觉如果D再顺利点应该ojbk，只是我帮不上什么忙比较遗憾，还是要努力参与进这种脑力风暴。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：模拟。

 * B：考虑相邻x之间有多少个y，问题变成Σ(x/i)==delta_y，枚举每一种取多少个，扫一遍即可。

 * C：强行状压dp，f[i][mask][j]表示到第i行，当前行状态为mask，总共有j个空格子的方案数。

 * D：往视角方向映射到平面上，变成二维，计算三角形内线段长度，注意双方都有可能退化。

 * E：对于一个长度为5的区间，用1操作，对于1，2，1，2位置做操作，就能令区间变成5 1 2 3 4，然后由于2n-1是奇数，所以每个数都能跳到自己前一个数的后面，然后2操作拿来调整1的位置即可。

 * F：考虑费用流每次增广的路径长度不减，上次路径为pre，这次路径为now，则会有(now-pre)*Flow的人会在等待now走完的时候在pre流掉，所以每次增广一条路径后，维护之前所有路径单位时间通过数量，那么每次能够涵盖的人就会减掉(now-pre)*Flow+a[T]这部分，剩下的人则要靠除之前所有路径单位时间通过数量来解决，注意还要加上当前路径长度。要特判k=0，否则就没了。

 * G：https://www.it610.com/article/5377359.htm

 * H：f[i][j][0/1/2]表示i这个点，x-y=j，联通块大小奇偶或者这个点不选，一棵子树做完之后，把不选的方案数*2，最后统计完答案再*3。

 * I：按位计算。

 * J：按1和0的个数分类讨论。

 * K：点分治模板题。

流水账

chenjb

这场的D本该过的，被hdu莫名其妙的输出小数位数搞了很神秘；yzc的构造只差一点点了，感觉如果D再顺利点应该ojbk，只是我帮不上什么忙比较遗憾，还是要努力参与进这种脑力风暴。

oipotato

subconscious

题解

  • A：模拟。
  • B：考虑相邻x之间有多少个y，问题变成Σ(x/i)==delta_y，枚举每一种取多少个，扫一遍即可。
  • C：强行状压dp，f[i][mask][j]表示到第i行，当前行状态为mask，总共有j个空格子的方案数。
  • D：往视角方向映射到平面上，变成二维，计算三角形内线段长度，注意双方都有可能退化。
  • E：对于一个长度为5的区间，用1操作，对于1，2，1，2位置做操作，就能令区间变成5 1 2 3 4，然后由于2n-1是奇数，所以每个数都能跳到自己前一个数的后面，然后2操作拿来调整1的位置即可。
  • F：考虑费用流每次增广的路径长度不减，上次路径为pre，这次路径为now，则会有(now-pre)*Flow的人会在等待now走完的时候在pre流掉，所以每次增广一条路径后，维护之前所有路径单位时间通过数量，那么每次能够涵盖的人就会减掉(now-pre)*Flow+a[T]这部分，剩下的人则要靠除之前所有路径单位时间通过数量来解决，注意还要加上当前路径长度。要特判k=0，否则就没了。
  • G：https://www.it610.com/article/5377359.htm
  • H：f[i][j][0/1/2]表示i这个点，x-y=j，联通块大小奇偶或者这个点不选，一棵子树做完之后，把不选的方案数*2，最后统计完答案再*3。
  • I：按位计算。
  • J：按1和0的个数分类讨论。
  • K：点分治模板题。
附加文件