2018-Reconquista-T16

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Winter 2017 - Jagiellonian U Contest'''

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

== 流水账 ==


== 总结 ==


=== lsmll ===
今天我锅比较大，刚开始A题的三分套三分没有仔细分析复杂度和误差，开了个比较离谱的上限结果TLE了多次，后来调参才过，当然后来了解到做法不是最好，有二分的做法，也许应该早一点造数据测而不是盲目调参。后来H也出了bug，树上距离算错了。可能是寒假写题不多状态还没完全恢复...?今天G题是我们和二队的区分点，和昨天一样基本思路对了，但是差一点，没有做出来比较可惜，要继续提高。另外我们没有读完所有题，比如E和J没读过。以后要改进说不定除了G题之外其他题更适合我们。

=== jsb ===

前期除了卡了一个A，感觉挺顺利的。

过了C后就有点尴尬了。我想出了K的做法，但是细节太多了，敲完板子后想放弃了。

这时候lsmll学长打算刚一刚D，于是我和lzw学长去努力攻克已经被屠版的G。

我们一开始方向有点问题，以为是找规律。后来发现循环矩阵可以用FFT倍增的时候时间已经不多了……最后没有成功rush出。

感觉一旦有点卡的话，节奏就容易爆炸。今天的G就卡得太久了，还好lsmll学长单开D过了。

=== lzw ===
H题算距离的地方误导了颜学长，算是一个锅。G题没rush出来还是姿势水平不够吧，我根本没有想到卷积。如果我们之前就知道循环矩阵这个神奇的性质，就不会卡的这么久了。最后半小时让jsb上机去写，这时候我们还没想清楚最后怎么算答案，时限有20s，想了想O（N^2^）也许可以莽过去，还是太naive了。 如果最后jsb上机写的时候，我在旁边把最后求答案的过程想清楚，也许最后就能顺利rush过去了，配合策略上可能还是略有不足。


== 补题 ==
E [lzw]
用一个set维护可行的一些区间，将区间表示成(t, pos)的形式，即从时间t开始在pos位置出现了一个点，可以通过这两个参数得出某个时间点该区间的左右端点。 删除的时候，假设删除区间是[L, R],先找到和[L, R]有交的那些区间，记录他们当中左端点最小是l，右端点最大是r，把这些区间删去，然后插入区间[l, L - 1], [R + 1, r]. 不必像题解中那样合并区间，因为即使让它们有交，它们还是满足单调性的，是可以维护的。

G [jsb] 题目要求a'[i] = 2 * a[(i + 1) % n] - a[i].变换t次的结果。 可以从多项式角度来考虑，等价于(a[0] + a[1]x + ...+ a[n - 1]x^n -1^)*(2x-1)  [mod x^n^]. FFT + 倍增即可。 也可以从矩阵角度考虑，转移矩阵是个循环矩阵，只要维护第一列即可，两个循环矩阵的乘积得到一个新的循环矩阵， 这个循环矩阵的第一列等于它们的第一列的卷积。

J [lsmll]

K [jsb] http://www.cnblogs.com/jiangshibiao/p/7788110.html 3.1处


== Solution ==

Contest Information

Petrozavodsk Winter 2017 - Jagiellonian U Contest

Opentrains

流水账

总结

lsmll

今天我锅比较大，刚开始A题的三分套三分没有仔细分析复杂度和误差，开了个比较离谱的上限结果TLE了多次，后来调参才过，当然后来了解到做法不是最好，有二分的做法，也许应该早一点造数据测而不是盲目调参。后来H也出了bug，树上距离算错了。可能是寒假写题不多状态还没完全恢复...?今天G题是我们和二队的区分点，和昨天一样基本思路对了，但是差一点，没有做出来比较可惜，要继续提高。另外我们没有读完所有题，比如E和J没读过。以后要改进说不定除了G题之外其他题更适合我们。

jsb

前期除了卡了一个A，感觉挺顺利的。

过了C后就有点尴尬了。我想出了K的做法，但是细节太多了，敲完板子后想放弃了。

这时候lsmll学长打算刚一刚D，于是我和lzw学长去努力攻克已经被屠版的G。

我们一开始方向有点问题，以为是找规律。后来发现循环矩阵可以用FFT倍增的时候时间已经不多了……最后没有成功rush出。

感觉一旦有点卡的话，节奏就容易爆炸。今天的G就卡得太久了，还好lsmll学长单开D过了。

lzw

H题算距离的地方误导了颜学长，算是一个锅。G题没rush出来还是姿势水平不够吧，我根本没有想到卷积。如果我们之前就知道循环矩阵这个神奇的性质，就不会卡的这么久了。最后半小时让jsb上机去写，这时候我们还没想清楚最后怎么算答案，时限有20s，想了想O（N²）也许可以莽过去，还是太naive了。 如果最后jsb上机写的时候，我在旁边把最后求答案的过程想清楚，也许最后就能顺利rush过去了，配合策略上可能还是略有不足。

补题

E [lzw]

用一个set维护可行的一些区间，将区间表示成(t, pos)的形式，即从时间t开始在pos位置出现了一个点，可以通过这两个参数得出某个时间点该区间的左右端点。 删除的时候，假设删除区间是[L, R],先找到和[L, R]有交的那些区间，记录他们当中左端点最小是l，右端点最大是r，把这些区间删去，然后插入区间[l, L - 1], [R + 1, r]. 不必像题解中那样合并区间，因为即使让它们有交，它们还是满足单调性的，是可以维护的。

G [jsb] 题目要求a'[i] = 2 * a[(i + 1) % n] - a[i].变换t次的结果。 可以从多项式角度来考虑，等价于(a[0] + a[1]x + ...+ a[n - 1]x^{n -1})*(2x-1) [mod xⁿ]. FFT + 倍增即可。 也可以从矩阵角度考虑，转移矩阵是个循环矩阵，只要维护第一列即可，两个循环矩阵的乘积得到一个新的循环矩阵， 这个循环矩阵的第一列等于它们的第一列的卷积。

J [lsmll]

K [jsb] http://www.cnblogs.com/jiangshibiao/p/7788110.html 3.1处

Solution