SCOI 2019 被虐记

Day 0

考笔试,内容是 NOI 笔试题库。

92 题,问 Pascal IDE 发现有两个选项是 Lazarus?

96 题,问 NOI 届数选项只有 35 没有 36?

不过反正阿克了。

Day 1

进场开题,发现全都不会。

开 T1,推了推发现操作是两段交替的,所以对一个东西取模就行了。数有点大,压了几个 int。

开 T2,编了几下编了一个边分治+主席树,莽了半天调出来了。

然后 T3 想 DP 想了半天写了一个暴力。

估分 ,实际

出分发现 jmr 了,一群人 了,我被虐了。

Day 1.5

面试,是 8 个人一组,小组讨论一个问题。我组抽到了七中实验食堂问题的处理,我胡编乱造了几句。听说有的组抽到了国民党失败的原因……

得分诡异,,很中等。感觉大多数人的分是随的。

Day 2

进场开题,发现 T1 是送分。

开 T1,一开始还以为要套一个线段树凸包,后来发现全是全局询问,于是几下就写完了。

开 T3,一眼有个 ,算了算以为过不了,编了编发现可以只维护进位(正解警告),会了 ,写了写就过了大样例。

开 T2,不会,写了个暴力。看了看 G 只有一个的部分分,写了个 dfs。看了看一条链的部分分,弄了一个点减边上去(正解警告)。最后还是没想出正解。

出来发现 T2 点减边放到树上就没了。

估分 ,实际

jmr 居然也没做 T2 得了 ,有一群人 ,我被虐了。

dxy 也 ,绝地翻盘了。

After

可能就第二了。队长是 jmr,后面两名是 J 和 dxy。应该四个 A 队了。

然后 myjs 可能也进队了。

dj 和蛇刀被 卡了,dj 有约了。蛇刀应该可以要个 D。

yyf,lb 和 space 应该也是被 卡了。

听说四中团灭了?

 

Sol

D1T1:令两段是 A 和 B,发现操作序列是 ABABABAB... 循环的,因为答案小于 ,所以只要对 的循环节长度取模就行了。后面递归暴力。

D1T2:暴力是边分治主席树,每次边分的时候询问查一边的关键点个数,分治到其中一边。

这样复杂度是

但是首先询问可以只问当前边分的这一部分的关键点个数,因为被鸽掉的部分之前查询过,可以暴力记下来。

如果暴力修改当前边分的部分的点,一个位置最多改 次,均摊下来是 的。

但是此处询问要区间查。可以发现询问的总次数也是 级的,那么可以考虑对询问的端点和修改一起离散化,然后每次询问之前暴力前缀和。

这个离散化不能排序,所以可以把点修改和询问端点先排好序,然后分治的时候直接归并一样分开就行了,这样就能做到时间

UPD. 差点被 hack 了。

这个暴力记下来的此前的查询不能全查,这样每层问 次,一共 层,复杂度就伪了。

首先可以发现同一个分治子树时,所有询问此前查询过的子树集合是相同的。

这里可以考虑查的时候看分治子树左边还是右边记下来的此前的查询少,这里显然每次分治都可以只 for 一个询问, 的复杂度。

然后假设说左边记了 个,右边记了 个,,那么这次查询就查左边,就 次。分治下去的时候就会有至少 个此前的查询被合并了,那复杂度可能就真一点了。

这里还得用常数复杂度实现删除这 个查询,所以要链表/Hash Table?

(以上内容纯属口胡,有疑问或者更简单的做法可以来 Hack

D1T3:发现问题是一个狄利克雷卷积,于是答案是一个积性函数,暴力去算质数位置的答案就行了。用 min_25 筛可以做到更快。

D2T1:问题转化为询问区间叉积绝对值的最大值,求前缀和后只需要求单个叉积最小值和最大值,凸包上二分。因为取绝对值所以不用管左右顺序。

D2T2:枚举满足性质的 G 连通块,因为是连通块所以恰好是点减边。暴力枚举 G 点和 G-G 边然后 dfs 求方案数乘起来即可。

D2T3:暴力线性基的过程,就是在一个元素和前面的一个子集异或和为 的时候,把这个元素丢弃掉,最后答案是 的线性基大小次方。那么看这个子集有什么性质,首先要满足的是异或和为 ,然后个数为偶数。这两个可以很轻松地线性基。接下来考虑进位,一定是同一个位在 的时候进位的个数恰好是偶数个。转化一下就是每一个加上 的数可能进位的后缀,都必须恰好出现偶数个。把每个数按这些造成影响的后缀分成不同的组,那么组与组之间的这些后缀是相互消不掉的,那么剩下的和“THUSC2017 杜老师”差不多,组内先把这一部分消掉,剩下的再拿出来一起跑线性基就行了。