Ric_shooter
Table_bottom

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

Remilia posted @ 2019年3月07日 11:00 in 涂字 , 60 阅读

ABCDEFGHIJK


复盘人:fz

开场散开看题,R爷说I是原题,很难,就先弃了.研究了一下C,E和J.R爷说J可能是贪心,试了一下,拍了之后被cha了.

发现I并不是原题,感觉可以直接选中位数,交了一发wa了,发现算法有问题,赶紧跑路.

发现了K可以直接判断,C可以直接网络流.都交给阿爷写.

K有几种特殊的case没讨论清楚,dirt了几发.C建边建错dirt了一发.

1:30 C AC(+1)

1:32 K AC(+2)

中途ymm和我讲了A和G的做法,感觉G不是很听得懂,上去写了一个A.

1:52 A AC(+0)

ymm上场写G,被精度问题卡了一会.

2:28 G AC(+3)

ymm和R爷讨论出了F,然后ans没从0开始枚举dirt了一发.

3:05 F AC(+1)

上去签了个H,因为没注意m特别大T了一发.

3:28 H AC(+1)

ymm搞出了I的做法,同时发现标程可能也到不了50步以内,R爷改了几发之后过了.

4:08 I AC(+1)

最后上机搞了D,写了个根号分块,最后10分钟过样例但一直T,最后弃疗了.


 
A:大力状压dp.
B:
C:由于一个点合法至少需要N/2条边,所有可能的boss不会太多,枚举boss直接网络流.
D:Sol(1):直接对每种颜色开一个平衡树,然后利用动态标号\(O(\log n)\)求出第一个大于x的位置.
   Sol(2):每次只会加在之前一段中或者是最末尾,用线段树维护每段的size,用vector维护每种颜色出现的段.找位置的时候在线段树上二分,然后去vector里找插入位置.复杂度\(O(N \log N)\).
E:
F:考虑所有的置换环,LCM不会超过N,故答案不会超过N.利用kmp预处理出所有环的合法答案,暴力枚举ans.
(upd by yjn)the proof: consider each trans: $2x\mapsto x,2x+1\mapsto x+n$. Eliminate 2 elements indexed 0 & 2n-1 cuz they're in two disjoint 1-len cycle. Each remaining element forms $f(x)\equiv \frac x 2\pmod {2n-1}$. Thus Each cycle is a coset w.r. $\langle n\rangle$ under the Ring $\mathbb{Z}/(2n-1)\mathbb {Z}$, whose length is a divisor of $\phi(2n-1)$.
G(by yjn):The final problem is to check if $\sum_{i}\lambda_i|x_1-a_i|=y_1$ holds. Precision of long double can't handle this. But it could be well-solved by choosing several prime $P$ and calculate the coordinate $\mod P$.
H:考虑放好序列,然后一个一个加入值,可以通过某种方式使得每种元素的出现次数都达到最大值.
I(by yjn): Let $A_0=A_1=1,A_i=2A_{i-1}(1<i<10)$ be the value of i-th element in a stack. Each time find a element maximize the minimum total value that would be erased this time. Obviously we can eliminate $1/4$ of the remaining value each time. So it can be done in $O(d+\log n)$ time. By making the bound tight, 54 steps are needed, and 54 steps are enough.
The standard code can be hacked.
J:考虑把a_i排成递增的,每次操作是询问前缀min,或者前缀加,或者后缀带权加,那么我们分块,然后每个区间里做一个凸包,每次重构或者单调移动指针即可.把块调小一点可以变快.\(O(N \sqrt{N})\)
K:分0,1,2,3个奇数次可改点判断.
 
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter