2016-E41-team1

从 Trac 迁移的文章

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

原文章内容如下：

{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                     2017/03/21 18:06-23:06 · Siunaus · Akalm/JTJL/sfiction                                      │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│H [0:18]│          1             2OOOoooo#    3                                                                                  │
│K [0:35]│            1                   2       oOoo... .3 o.  o!   .o.ooo.            ooooO!..o#                               │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:48]│                    1                               oO2o.o.oo   3 oooooo.oooo!o!#                                       │
│G [0:29]│       1   .Ooooo!.o.  . . 2      .Oo.. .  .o oo#           3                                                           │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:20]│           .Oooooo.o.  . OOOooooo oOo.. oOoOo.ooo. ooOOOoo.ooo.oooOooooo.ooooooooooOo.oOooOOoOOOoOOOooOoOOoooOoOooo....o│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│B2[0:00]│                                                                      1                                                 │
│C0[0:00]│                                                                                                                        │
│D1[0:00]│                                                                       1                                                │
│E0[0:00]│                                                                                                                        │
│F3[0:44]│                                                1                                        oOOo   .OOOooO!    .OoOooo.!..o│
│I5[0:00]│                                                        1                                                               │
│J [0:25]│                   1                                            2                   ..oo .  .OOOo      .OOooo !     !   │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}

||#||When||Problem||Lang||Verdict||Time||Memory||
||218||5:06:32||1747||F||g++0x-32||Time-limit exceeded||12||
||217||4:50:56||2272||J||g++0x||Wrong answer||3||
||216||4:50:32||1612||F||g++0x||Time-limit exceeded||10||
||215||4:37:21||1704||J||g++0x||Wrong answer||5||
||214||4:19:27||1205||F||g++0x||Time-limit exceeded||10||
||213||3:42:18||787||K||g++0x||OK||N/A||
||212||3:30:27||809||K||g++0x||Wrong answer||3||
||211||3:21:41||1555||A||g++0x||OK||N/A||
||210||3:18:23||1603||A||g++0x||Wrong answer||4||
||209||3:14:38||1597||A||g++0x||Wrong answer||1||
||208||2:21:42||872||K||g++0x||Wrong answer||3||
||207||2:00:47||653||G||g++0x||OK||N/A||
||206||1:22:40||1513||H||g++0x||OK||N/A||
||205||0:43:33||619||G||g++0x||Wrong answer||11||

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

start at 18:06

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. Aho [sfiction] ===

直接做KMP的匹配部分即可，需要用到fail的时候再计算fail，步数用尽或者需要用到T[i+1]的时候才转入下一轮。如果当前轮步数没有用尽，可以再用来计算fail。综上需要支持fail部分计算的状态机，比较扭曲。O(n)。注意是否存在结束在i的匹配很早就能确定。

=== G. Galois [JTJL, sfiction] ===

将P视为轮换的组合。方案分为两种，一种是在Q内构造对应轮换的幂次，对长为l的轮换共l种。另外一种是交换相同长度轮换之间的位置，若有k个，则共k!种方案。注意l为偶数时轮换会导致奇偶性变化，k>1的全排列中奇偶数量均分。因此\prod{l}*\prod{k!}为奇数时直接输出答案，否则需要除以2。O(n)。
=== H. Harary [JTJL, Akalm] ===

先推拓扑排序方案为1的方案数；由于2，3都是质数，在1的基础上卷积一下即可。

=== I. Ito [JTJL, Akalm] ===

记x_i = (a_i) / (c_i), y_i = (a_i + b_i) / (2 * c_i), u_i为花在每个物品上的金钱，题目就能写成一个线性规划的形式。

观察发现回答询问 (s_j, l_j) 相当于在点集 S = {(x_i, y_i)} \cup (1, 1) 构成的凸包上，找横坐标至少为l_j/s_j的点中纵坐标的最大值。求出凸链后二分。

=== J. Jordan [JTJL, Akalm] ===

题目中给定的区间改写成前缀和相减的形式就是一个差分约束系统，由于左开右闭所以要拆点。注意处理好s[x]-s[y]=0那些边的建立。

=== K. Kolmogorov [JTJL, Akalm] ===

从终点往前计算每个点的到终点的期望。
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│                                     2017/03/21 18:06-23:06 · Siunaus · Akalm/JTJL/sfiction                                      │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│H [0:18]│          1             2OOOoooo#    3                                                                                  ││K [0:35]│            1                   2       oOoo... .3 o.  o!   .o.ooo.            ooooO!..o#                               │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:48]│                    1                               oO2o.o.oo   3 oooooo.oooo!o!#                                       ││G [0:29]│       1   .Ooooo!.o.  . . 2      .Oo.. .  .o oo#           3                                                           │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:20]│           .Oooooo.o.  . OOOooooo oOo.. oOoOo.ooo. ooOOOoo.ooo.oooOooooo.ooooooooooOo.oOooOOoOOOoOOOooOoOOoooOoOooo....o│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│B2[0:00]│                                                                      1                                                 ││C0[0:00]│                                                                                                                        ││D1[0:00]│                                                                       1                                                ││E0[0:00]│                                                                                                                        ││F3[0:44]│                                                1                                        oOOo   .OOOooO!    .OoOooo.!..o││I5[0:00]│                                                        1                                                               ││J [0:25]│                   1                                            2                   ..oo .  .OOOo      .OOooo !     !   │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
#WhenProblemLangVerdictTimeMemory
2185:06:321747Fg++0x-32Time-limit exceeded12
2174:50:562272Jg++0xWrong answer3
2164:50:321612Fg++0xTime-limit exceeded10
2154:37:211704Jg++0xWrong answer5
2144:19:271205Fg++0xTime-limit exceeded10
2133:42:18787Kg++0xOKN/A
2123:30:27809Kg++0xWrong answer3
2113:21:411555Ag++0xOKN/A
2103:18:231603Ag++0xWrong answer4
2093:14:381597Ag++0xWrong answer1
2082:21:42872Kg++0xWrong answer3
2072:00:47653Gg++0xOKN/A
2061:22:401513Hg++0xOKN/A
2050:43:33619Gg++0xWrong answer11

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

start at 18:06

流水账

总结

题解

A. Aho [sfiction]

直接做KMP的匹配部分即可，需要用到fail的时候再计算fail，步数用尽或者需要用到T[i+1]的时候才转入下一轮。如果当前轮步数没有用尽，可以再用来计算fail。综上需要支持fail部分计算的状态机，比较扭曲。O(n)。注意是否存在结束在i的匹配很早就能确定。

G. Galois [JTJL, sfiction]

将P视为轮换的组合。方案分为两种，一种是在Q内构造对应轮换的幂次，对长为l的轮换共l种。另外一种是交换相同长度轮换之间的位置，若有k个，则共k!种方案。注意l为偶数时轮换会导致奇偶性变化，k>1的全排列中奇偶数量均分。因此\prod{l}*\prod{k!}为奇数时直接输出答案，否则需要除以2。O(n)。

H. Harary [JTJL, Akalm]

先推拓扑排序方案为1的方案数；由于2，3都是质数，在1的基础上卷积一下即可。

I. Ito [JTJL, Akalm]

记x_i = (a_i) / (c_i), y_i = (a_i + b_i) / (2 * c_i), u_i为花在每个物品上的金钱，题目就能写成一个线性规划的形式。

观察发现回答询问 (s_j, l_j) 相当于在点集 S = {(x_i, y_i)} \cup (1, 1) 构成的凸包上，找横坐标至少为l_j/s_j的点中纵坐标的最大值。求出凸链后二分。

J. Jordan [JTJL, Akalm]

题目中给定的区间改写成前缀和相减的形式就是一个差分约束系统，由于左开右闭所以要拆点。注意处理好s[x]-s[y]=0那些边的建立。

K. Kolmogorov [JTJL, Akalm]

从终点往前计算每个点的到终点的期望。