2016-E38-team1

从 Trac 迁移的文章

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

原文章内容如下：

{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                     2017/03/11 15:55-20:55 · Siunaus · Akalm/JTJL/sfiction                                      │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K [0:04]│    1     O#      3                                                                                                     │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:07]│         1          2                        3                                        OO#                               │
│J [0:30]│     1   2 oOOo3  oOOoo. ooo#                                                                                           │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C [0:31]│                                 1                     2                         ooOooo  ooo!.oo#                       │
│D [0:10]│      1       oOOo#   2             3                                                                                   │
│H [0:19]│                           1                2                   3OooOoo.#                                               │
│I7[0:22]│                          1                                                                                 oOOOOoOOoo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [2:51]│          OoOOOOOooOOoo. oooo. .       .ooOOOooOOooooooooO.o. ..OOooOoo..        ooOooOOOoooo.oooo.  .      oOOOOoOOoo. │
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│B [0:00]│                                1                                             2                                         │
│E0[0:48]│                                        ooOOOooOOooooooooO.o. ...                                o.  .      .           │
│F1[0:00]│                                                                                                                       1│
│G7[0:00]│                                                1                                                                       │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Run ID||Time||Size||Problem||Language||Result||Failed test||
||97||4:56:13||1378||I||g++0x||OK||N/A||
||96||4:02:25||1301||C||g++0x||OK||N/A||
||95||3:52:55||1270||C||g++0x||Wrong answer||18||
||94||3:42:24||591||A||g++0x||OK||N/A||
||93||3:01:40||859||H||g++0x||OK||N/A||
||92||3:00:30||855||H||g++0x||Compilation error||N/A||
||91||1:12:31||1952||J||g++0x||OK||N/A||
||90||0:46:30||1156||D||g++0x||OK||N/A||
||89||0:28:22||305||K||g++0x||OK||N/A||

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

start at 15:55

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. Tetris Puzzle [JTJL] ===

黑白染色：
||X||X||O||X||X||X||O||X||X||X||O||
||X||O||X||X||X||O||X||X||X||O||X||
||O||X||X||X||O||X||X||X||O||X||X||
||X||X||X||O||X||X||X||O||X||X||X||
||X||X||O||X||X||X||O||X||X||X||O||
||X||O||X||X||X||O||X||X||X||O||X||
||O||X||X||X||O||X||X||X||O||X||X||
||X||X||X||O||X||X||X||O||X||X||X||
||X||X||O||X||X||X||O||X||X||X||O||
||X||O||X||X||X||O||X||X||X||O||X||
||O||X||X||X||O||X||X||X||O||X||X||
||X||X||X||O||X||X||X||O||X||X||X||

=== B. Shift and Paint [sfiction] ===

N=L时相当于求自身为循环最小表示的串的数量，根据周期性容斥即可。

N>L时，若L>=4，可以构造出3的轮换和L-2的轮换。于是L为偶数时，最终可以得到2轮换，即相邻交换。L为奇数时，可以得到3轮换。借助两个相同元素，3轮换可以构造出2轮换。因此答案直接用组合数计算。

=== C. Pianist [sfiction] ===

显然路径上相邻两点可以用于连续消除。如果没有经过所有七种点对，则必定只经过了一个A，枚举所有这些情况贪心判定即可。剩下的情况都可以归约为主路径A-A或者A-A-A，解二对角矩阵即可。O(n^3^)。

=== D. Driving [sfiction] ===

将重复经过的边视为新的边，则问题变为加尽可能少的边使得图存在欧拉回路。注意到如果小于i的边能够使第i条边的两个端点连通，则第i条边不可能被重复加入，因为小于i的边所构路径一定小于2^i^。因此问题转化为，给定一棵树和树上2k个特殊点（原图中度数为奇数的点），要求组成k个点对，使得点对之间距离和最小。树形DP即可。O(nα(n))。

=== F. Forbidden Puzzle [Akalm] ===
观察可以发现，合法的pattern，其相邻颜色不同的格子均为2。记连接同色格子的邻边为0，异色的为1，题目就变成求一个分配方案使得每个2*2正方形中心十字上四条边之和均恰好为2。

以所有2*2正方形作为网络流中的点，黑白染色并分别往源汇连边；黑点往相邻白个方向的黑点连边，跑最大流，看源到黑点和白点到汇的边是否都跑满即可。
=== H. Pyramid Decoration [Akalm, sfiction] ===

考虑将第1层的值展开到第3层，可以发现只有3个顶点的值有贡献，其他值都被抵消了。推广可知只需2^i^+j层相应的3个点就能求出第j层的值。考虑自底向上用倍增方法维护特殊点，每次求最大的满足2^i^<=L-1的i，那么有2^i^>L-2^i^。于是L层的点要么没有贡献，要么只对第L-2^i^层的1个点有贡献，因此特殊点的数量不会变多。注意跨2^i^层贡献为4^i^+a+b+c，i=0时需要特判。O(nlognlogL)。

=== I. 2D Pyramid [JTJL, Akalm, sfiction] ===

所求满足Young Tableau，可以用Hook length formula解决。通过预处理i和i^i^的前缀和，矩形可以在O(logn)时间内算出。两矩形相交的情况则可以通过容斥解决。O(n+qlogn)。

=== J. Foot Game [JTJL] ===

RMQ/Segment_Tree

=== K. Pyramid Game [Akalm] ===
记石子数之和为S，最小的那堆石子数目为A，从(0, 0)开始推导必胜态即可。
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│                                     2017/03/11 15:55-20:55 · Siunaus · Akalm/JTJL/sfiction                                      │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│K [0:04]│    1     O#      3                                                                                                     │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:07]│         1          2                        3                                        OO#                               ││J [0:30]│     1   2 oOOo3  oOOoo. ooo#                                                                                           │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C [0:31]│                                 1                     2                         ooOooo  ooo!.oo#                       ││D [0:10]│      1       oOOo#   2             3                                                                                   ││H [0:19]│                           1                2                   3OooOoo.#                                               ││I7[0:22]│                          1                                                                                 oOOOOoOOoo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [2:51]│          OoOOOOOooOOoo. oooo. .       .ooOOOooOOooooooooO.o. ..OOooOoo..        ooOooOOOoooo.oooo.  .      oOOOOoOOoo. │├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│B [0:00]│                                1                                             2                                         ││E0[0:48]│                                        ooOOOooOOooooooooO.o. ...                                o.  .      .           ││F1[0:00]│                                                                                                                       1││G7[0:00]│                                                1                                                                       │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
Run IDTimeSizeProblemLanguageResultFailed test
974:56:131378Ig++0xOKN/A
964:02:251301Cg++0xOKN/A
953:52:551270Cg++0xWrong answer18
943:42:24591Ag++0xOKN/A
933:01:40859Hg++0xOKN/A
923:00:30855Hg++0xCompilation errorN/A
911:12:311952Jg++0xOKN/A
900:46:301156Dg++0xOKN/A
890:28:22305Kg++0xOKN/A

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

start at 15:55

流水账

总结

题解

A. Tetris Puzzle [JTJL]

黑白染色：

XXOXXXOXXXO
XOXXXOXXXOX
OXXXOXXXOXX
XXXOXXXOXXX
XXOXXXOXXXO
XOXXXOXXXOX
OXXXOXXXOXX
XXXOXXXOXXX
XXOXXXOXXXO
XOXXXOXXXOX
OXXXOXXXOXX
XXXOXXXOXXX

B. Shift and Paint [sfiction]

N=L时相当于求自身为循环最小表示的串的数量，根据周期性容斥即可。

N>L时，若L>=4，可以构造出3的轮换和L-2的轮换。于是L为偶数时，最终可以得到2轮换，即相邻交换。L为奇数时，可以得到3轮换。借助两个相同元素，3轮换可以构造出2轮换。因此答案直接用组合数计算。

C. Pianist [sfiction]

显然路径上相邻两点可以用于连续消除。如果没有经过所有七种点对，则必定只经过了一个A，枚举所有这些情况贪心判定即可。剩下的情况都可以归约为主路径A-A或者A-A-A，解二对角矩阵即可。O(n3)。

D. Driving [sfiction]

将重复经过的边视为新的边，则问题变为加尽可能少的边使得图存在欧拉回路。注意到如果小于i的边能够使第i条边的两个端点连通，则第i条边不可能被重复加入，因为小于i的边所构路径一定小于2i。因此问题转化为，给定一棵树和树上2k个特殊点（原图中度数为奇数的点），要求组成k个点对，使得点对之间距离和最小。树形DP即可。O(nα(n))。

F. Forbidden Puzzle [Akalm]

观察可以发现，合法的pattern，其相邻颜色不同的格子均为2。记连接同色格子的邻边为0，异色的为1，题目就变成求一个分配方案使得每个2*2正方形中心十字上四条边之和均恰好为2。

以所有2*2正方形作为网络流中的点，黑白染色并分别往源汇连边；黑点往相邻白个方向的黑点连边，跑最大流，看源到黑点和白点到汇的边是否都跑满即可。

H. Pyramid Decoration [Akalm, sfiction]

考虑将第1层的值展开到第3层，可以发现只有3个顶点的值有贡献，其他值都被抵消了。推广可知只需2i+j层相应的3个点就能求出第j层的值。考虑自底向上用倍增方法维护特殊点，每次求最大的满足2i<=L-1的i，那么有2i>L-2i。于是L层的点要么没有贡献，要么只对第L-2i层的1个点有贡献，因此特殊点的数量不会变多。注意跨2i层贡献为4i+a+b+c，i=0时需要特判。O(nlognlogL)。

I. 2D Pyramid [JTJL, Akalm, sfiction]

所求满足Young Tableau，可以用Hook length formula解决。通过预处理i和ii的前缀和，矩形可以在O(logn)时间内算出。两矩形相交的情况则可以通过容斥解决。O(n+qlogn)。

J. Foot Game [JTJL]

RMQ/Segment_Tree

K. Pyramid Game [Akalm]

记石子数之和为S，最小的那堆石子数目为A，从(0, 0)开始推导必胜态即可。