2019-team666-0038

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:7/12 712  dirt:53% 
rank:70/204
[[Image(Submissions.jpg,800px)]]
[[Image(Standings.jpg,800px)]]

== 流水账 ==
开场tjc秒了L，'''L1y4'''. yyc说A可以三分，喊hyw上机写，交了一次T了，改了一次精度交又T了。这时换人上机写I，'''I2y36'''. hyw读到了E，想了一个做法和tjc讨论了一下，tjc觉得复杂度不对，于是放到后期。然后yyc和tjc分别搞了B和C，'''B1y62''','''C1y72'''。中间hyw看榜读了个F，发现也是三分，这时tjc给了A的一个二分的做法，并且让hyw先写A，写完Wa了。这时tjc被yyc拉去讨论H，于是hyw秒了F，'''F1y93'''。tjc和hyw琢磨A，调了很长时间精度最后艰难地卡过去了，'''A8y127'''。这时yyc想出了H，上机后'''H1y156'''。hyw和tjc讨论了一下D，两人觉得这题倒着记搜细节相当多，因此决定先去想J、K两个字符串题。剩下两个多小时，三人思考G但都不会，3小时多一点的时候tjc和yyc讨论出了K，yyc上机写K始终过不去. hyw说J可以哈希，tjc想到可以转化成二分图四元环，有一个n根号n的做法，虽然觉得跑不满但是感觉时限跑不过就没写，（然而这就是正解了）。封榜前hyw想出E时间可以离散化，之前做法复杂度是对的，tjc认可后，yyc打印K，hyw写E。E写到最后wa了没有调完。
== 总结 ==
=== yyc ===
=== tjc  ===
=== hyw  ===
好气啊，今天这场没过的5个题里面除了G以外我们都给出正解了……码农场+时限估计有偏差顶不住啊，还是要提高代码能力啊……
这场D感觉可能比E好写，当时机位空出来的时候要是冷静去推一推D可能还是有机会的，但是当时榜上过的人不多就没搞，这算是一个遗憾。
2020/1/23UPD: G是FFT套路题
=== 题解 ===
A：（三分听说能卡过）可以证明sinθ正比于x，其中θ为每一段路程和x轴的夹角，x为y轴方向走的距离，于是二分这个比例系数，算出三段路y轴上走的距离，和h比较。
B：@???（忘了）
C: @???（忘了）
D: 反向记搜
E：按时间排序区间合并，暴力维护当前不可达的区间，每次加一个区间就二分两端点，暴力删中间的区间；由于每个区间每过1秒左端点和右端点就会收缩1，再用一个优先队列维护每个区间消失的时间。由于只删区间所以复杂度不会超过总区间数，复杂度是对的。
F：三分
G：FFT。题意是给出一列数A[i]，每秒后A[i]'=2A[i+1]-A[i]（同时变化），问t秒后的数组A。显然有ans[k]=\sum_{i=0}^{n-1} a_{i+k} c_i，其中c_i表示(2x-1)^t的所有模n余i次项的系数之和。就是个卷积，FFT即可。c_i的意义可以联系特征方程，详见[http://clatisus.com/Petrozavodsk%20Winter-2017.%20Jagiellonian%20U%20Contest?printable Nonsense Time]
H：@yyc
I：@???
J：前缀和后缀分别哈希然后前缀往对应的后缀连边，转化为二分图找四元环。有n根号n的做法@tjc
K：@tjc @yyc
L：签到

[/wiki/2019-team666 返回]

概述

solved:7/12 712 dirt:53%

rank:70/204

流水账

开场tjc秒了L，L1y4. yyc说A可以三分，喊hyw上机写，交了一次T了，改了一次精度交又T了。这时换人上机写I，I2y36. hyw读到了E，想了一个做法和tjc讨论了一下，tjc觉得复杂度不对，于是放到后期。然后yyc和tjc分别搞了B和C，B1y62,C1y72。中间hyw看榜读了个F，发现也是三分，这时tjc给了A的一个二分的做法，并且让hyw先写A，写完Wa了。这时tjc被yyc拉去讨论H，于是hyw秒了F，F1y93。tjc和hyw琢磨A，调了很长时间精度最后艰难地卡过去了，A8y127。这时yyc想出了H，上机后H1y156。hyw和tjc讨论了一下D，两人觉得这题倒着记搜细节相当多，因此决定先去想J、K两个字符串题。剩下两个多小时，三人思考G但都不会，3小时多一点的时候tjc和yyc讨论出了K，yyc上机写K始终过不去. hyw说J可以哈希，tjc想到可以转化成二分图四元环，有一个n根号n的做法，虽然觉得跑不满但是感觉时限跑不过就没写，（然而这就是正解了）。封榜前hyw想出E时间可以离散化，之前做法复杂度是对的，tjc认可后，yyc打印K，hyw写E。E写到最后wa了没有调完。

总结

yyc

tjc

hyw

好气啊，今天这场没过的5个题里面除了G以外我们都给出正解了……码农场+时限估计有偏差顶不住啊，还是要提高代码能力啊……

这场D感觉可能比E好写，当时机位空出来的时候要是冷静去推一推D可能还是有机会的，但是当时榜上过的人不多就没搞，这算是一个遗憾。

2020/1/23UPD: G是FFT套路题

题解

A：（三分听说能卡过）可以证明sinθ正比于x，其中θ为每一段路程和x轴的夹角，x为y轴方向走的距离，于是二分这个比例系数，算出三段路y轴上走的距离，和h比较。

B：@???（忘了）

C: @???（忘了）

D: 反向记搜

E：按时间排序区间合并，暴力维护当前不可达的区间，每次加一个区间就二分两端点，暴力删中间的区间；由于每个区间每过1秒左端点和右端点就会收缩1，再用一个优先队列维护每个区间消失的时间。由于只删区间所以复杂度不会超过总区间数，复杂度是对的。

F：三分

G：FFT。题意是给出一列数A[i]，每秒后A[i]'=2A[i+1]-A[i]（同时变化），问t秒后的数组A。显然有ans[k]=\sum_{i=0}{n-1} a_{i+k} c_i，其中c_i表示(2x-1)t的所有模n余i次项的系数之和。就是个卷积，FFT即可。c_i的意义可以联系特征方程，详见Nonsense Time

H：@yyc

I：@???

J：前缀和后缀分别哈希然后前缀往对应的后缀连边，转化为二分图找四元环。有n根号n的做法@tjc

K：@tjc @yyc

L：签到

附加文件