2018-Reconquista-T15

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Winter 2017 - Xiaoxu Guo Contest 5'''

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001492 Opentrains]

== 流水账 ==


== 总结 ==


=== lsmll ===
刚开始运气很好拿了全场一血，不过后面第二题就卡了1.5h，导致lzw和jsb学长都在搞G，严重影响了进度。不过lzw学长之前在三队训练没有一二队多，所以代码能力比我和jsb稍差一点也情有可原，这也是训练的意义。后面F题没有出还是体现了我们实力上还有不足，要继续加油，每场比赛后认真补题、总结。

=== jsb ===
一场三道矩乘，果然是叉姐的题……

得出结论：矩乘里注意循环顺序，而且可以把“加完if取模”合并到乘法里一起取模……可以快不少……

最后的F题真是可惜。我和lzw学长感觉和标解很接近了，但是没有戳破那张纸，还是没能成功做出来……

感觉矩阵真TM神奇啊……

=== lzw ===
G题主要是我的锅，写出了奇怪的bug和巨大的常数，导致卡了1.5h，不过从中学到了矩阵乘法的常数优化技巧，也发现自己代码能力十分不够。F题确实比较巧妙，没有想到，不过也从中学习到了一些关于矩阵的技巧。虽然成绩不怎么样，本场训练的收获还是挺大的。

== 补题 ==
A []

B []

C [lsmll]

D [lzw,jsb]

F [lzw]

I []

J []


== Solution ==

=== D ===
考虑 m = lcm(1,2...n). 假设一个合法解x >= n * m, 那么x - m也合法（根据鸽笼原理至少存在一种货币取的总价值>=m, 假设是第k种, 去掉m / k个该种硬币总价值就变成x - m）. 同理如果一个合法解 x <= sum - n * m,根据鸽笼原理至少存在一种货币没取的总价值>=m，把它取过来可以构造出解x + m. 两头做多重背包dp(需要类似单调队列优化的做法)，中间是一些等差数列，等差数列的首项末项在两头。

=== F ===
把有人来的时间点作为关键点，并且人为插入一些关键点，使得相邻关键点距离<=D. 对于每个关键点，利用上一个点的信息计算出每个点的期望O(N^2^)。关键点之间的点，可以预处理转移矩阵A^0^,A^1^...A^D^, 利, 用上一个关键点的信息O(N)计算出第N个点的期望。  取D=200即可。 

http://www.cnblogs.com/jiangshibiao/p/7788110.html 2.28处

Contest Information

Petrozavodsk Winter 2017 - Xiaoxu Guo Contest 5

Opentrains

流水账

总结

lsmll

刚开始运气很好拿了全场一血，不过后面第二题就卡了1.5h，导致lzw和jsb学长都在搞G，严重影响了进度。不过lzw学长之前在三队训练没有一二队多，所以代码能力比我和jsb稍差一点也情有可原，这也是训练的意义。后面F题没有出还是体现了我们实力上还有不足，要继续加油，每场比赛后认真补题、总结。

jsb

一场三道矩乘，果然是叉姐的题……

得出结论：矩乘里注意循环顺序，而且可以把“加完if取模”合并到乘法里一起取模……可以快不少……

最后的F题真是可惜。我和lzw学长感觉和标解很接近了，但是没有戳破那张纸，还是没能成功做出来……

感觉矩阵真TM神奇啊……

lzw

G题主要是我的锅，写出了奇怪的bug和巨大的常数，导致卡了1.5h，不过从中学到了矩阵乘法的常数优化技巧，也发现自己代码能力十分不够。F题确实比较巧妙，没有想到，不过也从中学习到了一些关于矩阵的技巧。虽然成绩不怎么样，本场训练的收获还是挺大的。

补题

A []

B []

C [lsmll]

D [lzw,jsb]

F [lzw]

I []

J []

Solution

D

考虑 m = lcm(1,2...n). 假设一个合法解x >= n * m, 那么x - m也合法（根据鸽笼原理至少存在一种货币取的总价值>=m, 假设是第k种, 去掉m / k个该种硬币总价值就变成x - m）. 同理如果一个合法解 x <= sum - n * m,根据鸽笼原理至少存在一种货币没取的总价值>=m，把它取过来可以构造出解x + m. 两头做多重背包dp(需要类似单调队列优化的做法)，中间是一些等差数列，等差数列的首项末项在两头。

F

把有人来的时间点作为关键点，并且人为插入一些关键点，使得相邻关键点距离<=D. 对于每个关键点，利用上一个点的信息计算出每个点的期望O(N²)。关键点之间的点，可以预处理转移矩阵A⁰,A¹...A^D, 利, 用上一个关键点的信息O(N)计算出第N个点的期望。 取D=200即可。

http://www.cnblogs.com/jiangshibiao/p/7788110.html 2.28处