2016-E23-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||87||4:41:07||3470||B||g++0x||OK||N/A||
||86||4:36:22||3483||B||g++0x||Wrong answer||4||
||85||4:12:11||3995||B||g++0x||Time-limit exceeded||14||
||84||3:53:27||3618||B||g++0x||Wrong answer||9||
||83||3:32:40||3331||B||g++0x||Wrong answer||4||
||82||3:19:29||3229||B||g++0x||Wrong answer||4||
||81||2:36:11||1451||D||g++0x||OK||N/A||
||80||0:51:36||1644||H||g++0x||OK||N/A||

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001489

start at 16:30

== 流水账 ==

== 总结 ==

== 题解 ==

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
}}}

=== B. Point Pairs [JTJL & wxj] ===

结论：一个有偶数条边的连通无向图，必然能够分解为长为2的边不相交链的并。证明：首先对于有偶数条边的树，自底向上就能构造一个方案。对于一个连通无向图，根据其DFS树将边分为树上边和横叉边，如果将所有横叉边(u,v)中的v视为一个新结点，则可以将原图转化为一棵树，之后应用树上构造即可。

对于本题，将行列坐标视为点，点视为边，所得二分图上应当恰好有一个奇数条边的连通二分图，目标边均位于这一子图中。对这一二分图边双连通缩点之后，所有非关键边都合法，所有关键边需要检查两侧边数是否为偶数。

=== C. House Moving [sfiction] ===

结论：最后必然是两侧密布，且两端向中间不增。证明：考虑任意一个解，假设有不在左连续段也不在右连续段中的点，则可以将它往人数和更小的那一侧移动一个单位，这样解能够增加两侧人数差。调整完毕后即达到两侧密布的条件。假设左连续段不满足不增，其中有p[i]<p[i+1]。假设p[i]左侧和为L，p[i+1]右侧和（包括右连续段）为R，则交换后改变量为(L-R)(p[i]-p[i+1])。若L>R，则在此之前将左连续段尾部移往右连续段可以令解更优。因此必然有L<=R，解不会更劣。

{{{
#!html
首先从大到小排序，依次放置，每次只需考虑放在中间空白段的左右两端。DP状态中阶段 $i$ 是必要的。考虑尽可能减少状态数，首先已选的家庭间的距离和显然是可以也应该先计算的。未选家庭间的代价显然是无法计算的。对于已选家庭和未选家庭间的距离和，考虑和J题类似的思路。假设左侧家庭放置在 $[1,left]$，则计算距离和中左侧到 $left$ 这一段的和，右侧也是同理。这样对未选家庭来说，只需要知道左右侧各自的总人数。因为两侧总人数已知，因此只需记录单侧人数。状态 $dp(i,L)$ 表示考虑前 $i$ 个家庭，左侧总人数 $L$ 的最大距离和。转移中，假设当前家庭 $P_{i}$ 在左侧，则 $dp(i,L)=dp(i,L-P_{i})+P_{i}L+P_{i}(s_{i-1}-L)(n-i-1)+L(S-s_{i})$。式中各项分别表示之前阶段的和、当前家庭到左侧家庭的距离和、当前家庭到右侧家庭的距离和、左侧家庭到未选家庭的配对数。放在右侧也是同理。
}}}

=== D. Nice Set of Points [JTJL] ===

1e4和1e3可能是nlogn的关系，因此可以考虑单次合并O(n)的分治解法。假设两个nice点集分别位于垂直于x轴直线x=k的两侧，则只需将所有点投影到x=k上，则来自不同点集的两点可以通过x=k相互到达。为了减少点的消耗，可以令k等于左侧点集x最大值或右侧点集x最小值。这样至少能减少n-1个点。

=== E. Eel and Grid [sfiction] ===

{{{
#!html
<p>$d=\gcd(H,W)$，$ans=\sum_{k=0}^{d}[\gcd(H,k)=1,\gcd(W,d-k)=1]\binom{d}{k}$。</p>

<p>上式中 $d$ 表示路径方案的循环节，$k$ 表示前 $d$ 步中向下的步数，这一公式同时也给出了所有方案的构造方法。大致上满足这一条件的 $d$ 可以令路径在到达起点前不重复。$k$ 和 $d-k$ 与边长的互质关系则可以保证在两个方向上各循环节起始点的完整遍历。<del>然而并不会证明。</del></p>

<p>假设我们讨论 $(i,j)\rightarrow(i+1,j) (i,j)\rightarrow(i,j+1)$ 两个方向，如果 $(i,j)\rightarrow(i+1,j)$，那么 $(i+1,j-1)$ 就只能走 $(i+2,j-1)$。这个约束不断传递直到回到 $(i,j)$，由数论知识得经过 $\mathrm{lcm}(W,H)$ 个点。因此图上所有点根据 $(i+j)\mod d$ 被划分为 $d$ 个等价类。显然前 $d$ 步不会相互影响，且走完 $d$ 步后会决定所有等价类的方向。显然只需要每 $d$ 步起始点不重复，整条路径就不会重复。假设这 $d$ 步在两个方向上增量为 $(x_0,y_0)$，为了遍历所有点，必须令二元组的最小周期为 $HW/d$。可以证明当且仅当 $\gcd(H,x)=\gcd(W,d-x)=1$ 时满足要求。</p>
}}}

=== G. Rectangle-free Grid [JTJL] ===

根据数量级考虑构造有n^1.5^个O的矩阵。类似题目质数的构造较为简单，因此先构造出(13^2^)^2^的矩阵，然后取150*150的子矩阵作为答案。三元组(i,j,k)对应(Pi+j,(Pk+i+jk)%P)处的一个O。关于构造思路，用Pi+j编码横坐标，将每列划分为P得到Pk的增量都很自然。之后的偏移量的式子利用了质数的性质。

=== H. Cups and Beans [sfiction] ===

将一颗位于第 i 个杯子的豆子看作 Nim 游戏中一个大小为 i 的石子堆，问题转化为取法有限制的单 Nim 游戏 SG 值求解。查询为“区间中最小未出现非负整数”。考虑区间中不同数个数的线段树维护方法，令每个 SG 值仅出现在最右位置。再利用 SG 值求解过程中的连续性，只需查询区间补集的最小值即可。

=== I. Edge Coloring [akalm] ===

将过程反向，就变成了每条边只有第一次必须遵循步数奇偶性问能否遍历所有边的问题。注意到原路返回不改变奇偶性，所以枚举起点进行floodfill即可。


=== J. Travel in Sugar Country [sfiction] ===

类似的序列上访问顺序无限制问题都可以用同种方法解决，前提是整体信息能够拆分到点，例如本题长度可以分解为每一单位段的长度和经过次数的乘积之和。dp(i,s,t,j)表示处理了前i个点，是否包含起点，是否包含终点，当前有j个不相交链。每条不相交链均表示整体中的一个连续段，因为这2j个点必须与i+1..n的点相连，因此i-(i+1)这段距离需要经过2*j次。转移分为不选择、选为起点、选为终点和选为普通点。选为起点则有作为新链、作为已有链的头两种转移。选为终点有作为新链、作为已有链的尾两种转移。选为普通点有作为新链、作为已有链的头、作为已有链的尾、连接两个链四种转移。涉及整体起点终点的操作由很多细节，如以起点为首的链无法再加点、起点终点无需向后延伸等。

Run ID	Time	Size	Problem	Language	Result	Failed test
87	4:41:07	3470	B	g++0x	OK	N/A
86	4:36:22	3483	B	g++0x	Wrong answer	4
85	4:12:11	3995	B	g++0x	Time-limit exceeded	14
84	3:53:27	3618	B	g++0x	Wrong answer	9
83	3:32:40	3331	B	g++0x	Wrong answer	4
82	3:19:29	3229	B	g++0x	Wrong answer	4
81	2:36:11	1451	D	g++0x	OK	N/A
80	0:51:36	1644	H	g++0x	OK	N/A

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001489

start at 16:30

流水账

总结

题解

B. Point Pairs [JTJL & wxj]

结论：一个有偶数条边的连通无向图，必然能够分解为长为2的边不相交链的并。证明：首先对于有偶数条边的树，自底向上就能构造一个方案。对于一个连通无向图，根据其DFS树将边分为树上边和横叉边，如果将所有横叉边(u,v)中的v视为一个新结点，则可以将原图转化为一棵树，之后应用树上构造即可。

对于本题，将行列坐标视为点，点视为边，所得二分图上应当恰好有一个奇数条边的连通二分图，目标边均位于这一子图中。对这一二分图边双连通缩点之后，所有非关键边都合法，所有关键边需要检查两侧边数是否为偶数。

C. House Moving [sfiction]

结论：最后必然是两侧密布，且两端向中间不增。证明：考虑任意一个解，假设有不在左连续段也不在右连续段中的点，则可以将它往人数和更小的那一侧移动一个单位，这样解能够增加两侧人数差。调整完毕后即达到两侧密布的条件。假设左连续段不满足不增，其中有p[i]R，则在此之前将左连续段尾部移往右连续段可以令解更优。因此必然有L<=R，解不会更劣。

首先从大到小排序，依次放置，每次只需考虑放在中间空白段的左右两端。DP状态中阶段 $i$ 是必要的。考虑尽可能减少状态数，首先已选的家庭间的距离和显然是可以也应该先计算的。未选家庭间的代价显然是无法计算的。对于已选家庭和未选家庭间的距离和，考虑和J题类似的思路。假设左侧家庭放置在 $[1,left]$，则计算距离和中左侧到 $left$ 这一段的和，右侧也是同理。这样对未选家庭来说，只需要知道左右侧各自的总人数。因为两侧总人数已知，因此只需记录单侧人数。状态 $dp(i,L)$ 表示考虑前 $i$ 个家庭，左侧总人数 $L$ 的最大距离和。转移中，假设当前家庭 $P_{i}$ 在左侧，则 $dp(i,L)=dp(i,L-P_{i})+P_{i}L+P_{i}(s_{i-1}-L)(n-i-1)+L(S-s_{i})$。式中各项分别表示之前阶段的和、当前家庭到左侧家庭的距离和、当前家庭到右侧家庭的距离和、左侧家庭到未选家庭的配对数。放在右侧也是同理。

D. Nice Set of Points [JTJL]

1e4和1e3可能是nlogn的关系，因此可以考虑单次合并O(n)的分治解法。假设两个nice点集分别位于垂直于x轴直线x=k的两侧，则只需将所有点投影到x=k上，则来自不同点集的两点可以通过x=k相互到达。为了减少点的消耗，可以令k等于左侧点集x最大值或右侧点集x最小值。这样至少能减少n-1个点。

E. Eel and Grid [sfiction]

$d=\gcd(H,W)$，$ans=\sum_{k=0}^{d}[\gcd(H,k)=1,\gcd(W,d-k)=1]\binom{d}{k}$。

上式中 $d$ 表示路径方案的循环节，$k$ 表示前 $d$ 步中向下的步数，这一公式同时也给出了所有方案的构造方法。大致上满足这一条件的 $d$ 可以令路径在到达起点前不重复。$k$ 和 $d-k$ 与边长的互质关系则可以保证在两个方向上各循环节起始点的完整遍历。然而并不会证明。

假设我们讨论 $(i,j)\rightarrow(i+1,j) (i,j)\rightarrow(i,j+1)$ 两个方向，如果 $(i,j)\rightarrow(i+1,j)$，那么 $(i+1,j-1)$ 就只能走 $(i+2,j-1)$。这个约束不断传递直到回到 $(i,j)$，由数论知识得经过 $\mathrm{lcm}(W,H)$ 个点。因此图上所有点根据 $(i+j)\mod d$ 被划分为 $d$ 个等价类。显然前 $d$ 步不会相互影响，且走完 $d$ 步后会决定所有等价类的方向。显然只需要每 $d$ 步起始点不重复，整条路径就不会重复。假设这 $d$ 步在两个方向上增量为 $(x_0,y_0)$，为了遍历所有点，必须令二元组的最小周期为 $HW/d$。可以证明当且仅当 $\gcd(H,x)=\gcd(W,d-x)=1$ 时满足要求。

G. Rectangle-free Grid [JTJL]

根据数量级考虑构造有n^1.5个O的矩阵。类似题目质数的构造较为简单，因此先构造出(13²)²的矩阵，然后取150*150的子矩阵作为答案。三元组(i,j,k)对应(Pi+j,(Pk+i+jk)%P)处的一个O。关于构造思路，用Pi+j编码横坐标，将每列划分为P得到Pk的增量都很自然。之后的偏移量的式子利用了质数的性质。

H. Cups and Beans [sfiction]

将一颗位于第 i 个杯子的豆子看作 Nim 游戏中一个大小为 i 的石子堆，问题转化为取法有限制的单 Nim 游戏 SG 值求解。查询为“区间中最小未出现非负整数”。考虑区间中不同数个数的线段树维护方法，令每个 SG 值仅出现在最右位置。再利用 SG 值求解过程中的连续性，只需查询区间补集的最小值即可。

I. Edge Coloring [akalm]

将过程反向，就变成了每条边只有第一次必须遵循步数奇偶性问能否遍历所有边的问题。注意到原路返回不改变奇偶性，所以枚举起点进行floodfill即可。

J. Travel in Sugar Country [sfiction]

类似的序列上访问顺序无限制问题都可以用同种方法解决，前提是整体信息能够拆分到点，例如本题长度可以分解为每一单位段的长度和经过次数的乘积之和。dp(i,s,t,j)表示处理了前i个点，是否包含起点，是否包含终点，当前有j个不相交链。每条不相交链均表示整体中的一个连续段，因为这2j个点必须与i+1..n的点相连，因此i-(i+1)这段距离需要经过2*j次。转移分为不选择、选为起点、选为终点和选为普通点。选为起点则有作为新链、作为已有链的头两种转移。选为终点有作为新链、作为已有链的尾两种转移。选为普通点有作为新链、作为已有链的头、作为已有链的尾、连接两个链四种转移。涉及整体起点终点的操作由很多细节，如以起点为首的链无法再加点、起点终点无需向后延伸等。