Ozon Tech Challenge 2020

Ozon Tech Challenge 2020 div1+div2

rating:2182->2097

展开复盘

00:04:28 A Accepted [main tests] 写了会B,发现有点混乱,写到一半决定先放着
00:29:29 C Wrong answer on pretest 1 [pretests]
00:32:22 C Time limit exceeded on pretest 6 [pretests] 开始懵逼
00:44:57 C Time limit exceeded on pretest 6 [pretests] 只好回去写B
00:56:05 B Wrong answer on pretest 1 [pretests]
00:57:58 B Accepted [main tests]
00:58:18 C Time limit exceeded on pretest 6 [pretests]
01:05:06 C Time limit exceeded on pretest 6 [pretests] 自闭了,完全不懂为啥tle
01:15:34 D Memory limit exceeded on pretest 2 [pretests] 因为极度低落无法冷静开始瞎jb改瞎jb交
01:19:18 D Memory limit exceeded on pretest 1 [pretests]
01:23:25 D Memory limit exceeded on pretest 2 [pretests]
01:24:38 D Wrong answer on pretest 2 [pretests]
01:25:18 D Wrong answer on pretest 1 [pretests]
01:28:12 D Wrong answer on pretest 6 [pretests]
01:34:01 D Accepted [main tests]
01:40:05 C Time limit exceeded on pretest 6 [pretests]
02:04:06 C Accepted [main tests] 忽然意识到完全忘记可以自己造极限数据了,然后才发现nm真的慢,才换成$m^2$

现在看来,跳B做C直接导致做C的时候严重降智,对cf评测机盲目自信只能算部分原因。跳题对我这种很受状态影响的人太得不偿失了

CF1305A Kuroni and the Gifts

code

CF1305B Kuroni and Simple Strings

请先思考后再展开

显然就是让最后序列不存在子序列(),那么我们枚举最后答案是从哪里分开的,左边只能有右括号,右边只能有左括号

如果左边左括号不等于右边右括号,那么一定不是最优的分割点,稍微画画+讨论就知道了

别问我为什么花了这么久,我回答不上来

CF1305C Kuroni and Impossible Calculation

dreamoon的吧……

CF1305D Kuroni and the Celebration

请先思考后再展开

可以从链和菊花两种特殊情况找到灵感

每次取相邻两点问,这样每次就能删掉两个点;如果相邻只剩一个点就直接跳过去,这样每次也能删掉两个点

复杂度线性,code

当时求稳还贴了个求重心,挂了很多次是脑子不清醒,大家不用去看了

CF1305E Kuroni and the Score Distribution

请先思考后再展开

发现上界是$g_k=\sum_{i=1}^{k} \lfloor i/2 \rfloor$,而$a_i=i$可以达到这个上界;而且其实只要能找到一个长度不超过n的就行了,后面的只需要填$1e8+MXNUM*i$之类的东西


$$
找到g_k<m \le g_{k+1},T=m-g_k \le k/2 \\
(a_{k+1}-k)+k=a_{k+1}…(a_{k+1}-k+T-1)+(k-T+1)=a_{k+1}这样的T对 \\
推下不等式,发现a_{k+1} \in [2k-2T,2k-2T+2),另外有k<a_{k+1},因此a_{k+1}=2k-2T+1 \\
$$

code

CF1305F Kuroni and the Punishment

请先思考后再展开

因为可以把所有人变成偶数,答案不超过n。直接随机一个不变的人的话,并用其不同质因子(不超过12个)去check,正确率最坏是$(n-1)/n$,本题n较大需要很多次随机


在最优方案中移动超过1的人不会超过n/2个,因此随机一个变化量小于1的人,正确率不超过$1/2$,这样只要log次就能达到很小的错误率了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1586e9f6.html
转载请注明出处,谢谢!