Ric_shooter
Table_bottom

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

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

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个奇数次可改点判断.
 
 
DPE Result Sylhet 说:
2022年8月30日 01:35

The Primary School Certificate Examination tests 2022 are successfully completed in November for all education boards across the country all divisions, and they have going to announce PSC Result 2022 Sylhet Board with full mark sheet under DPE along with Sylhet board for the academic terminal examination tests. DPE Result Sylhet Based on the DPE announcement there are 30 lacks of students are participated from all divisions across the country for this Primary Education Course (PEC) from all education boards included the Sylhet board, every year those Grade-5 Terminal annual final exams are conducted under the Directorate of Primary Education (DPE) and this year also conducted same without delay.


登录 *


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