XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Urals

---

复盘：yjn

0:21:31 B(+1)

1:11:12 C(+1)

先过了两个前期题。这部分大问题没有，过题时间稍慢了一点不过差不多。

期间我把大部分题都看了一遍。先看了G，就是个分段积分。拿单调队列维护一下就好了。对于直线段的情况，积分式子比较狗屎，但注意到这时其实等价于算一个三角形的面积。感觉不算难写。然后看了D，没仔细想，至少多项式求逆一个log可做。和gt说了一下让他想想能不能dp。E就是个讨论，把所有情况画了一下和R爷说了下。F粗看一眼期望3n步的做法很显然，没看清数据范围以为能过。

这段时间gt单干了一个K。而我把这些题都和R爷说了下。R爷推了下D说不用多项式不那么好做。我在看别的题就先没管。

2:03:24 K(+2)

gt过了以后，R爷上机写A。

我看了下J，和gt说了下线段树的做法。gt就拿去想细节了。

2:20:24 A(+2)

这时候发现了F的问题。于是换gt先来写J。

我fix了一会儿F没有fix出来。先和R爷把E的情况讨论清楚了。

gt在边写边想空机了比较久，就先让R爷上了E。

E写的速度还正常。但是re了以后调了很久。

R爷在调的时候我在帮gt眼看J。

最后R爷过了E，gt没过J

4:53:17 E(+2)

---

A：线段树维护凸壳优化dp。

B:

C:

D：$(1+x+...+x^9)^n(1+x^{-1}+...+x^{-9})^n=(1+x+...+x^9)^{2n}x^{-9n}$。

E:

F（by yjn）:这个F标算是个假的吧……标算的做法是先把所有的$p(i)+1$给乘起来（即$Q(i,cur,cur)$），这样最后就得到了$0$的位置。然后从其余的位置里随机挑两个$x,y$，问$Q(x,y,zero)$，这样如果得到$z$，若$z\neq x$，那么$y\neq 1$，反之亦然。这样最后剩下的就是$1$。然后$Q(one,pos[x],one)$就得到了$pos[x+1]$。比我的做法好点吧，是最坏$3n$的。不过这个期望显然比$2.5n$要大，试了$3$个随机种子，只有和标程一样的时候才过了啊。。。

G:

H:

I:

J:

K:

---

总结：

(by yjn)：

这场问题主要出在J，gt没有对写题时间估计好，中间按自己的想法换做法了也没和队友说。然后E在调的时候已经是最后期了，理论上应该有人帮看。但当时我在帮忙看J，也没有办法。