【题解】CF1609 Deltix Round, Autumn 2021 (Div. 1 + Div. 2)

三棵线段树。

A

将每个数表示成 \(2^k\times c\),其中 \(c\) 是奇数,显然最后一顶找到一个最大的 \(c\) 将所有的 \(2^k\) 都乘过去即可。

代码:Submission #137565948 - Codeforces

B

一次操作最多消除一个 abc 也一定消除一个 abc,维护 abc 出现次数即可。

代码:Submission #137566109 - Codeforces

C

考虑一个点往后跳,仅跳 \(1\) 和质数跳到的第一个质数所处的位置,然后再看这个位置往后跳能跳多少个 \(1\) 就行。这两个东西倒着推很好求。

代码:Submission #137567001 - Codeforces

D

一个连通块可以连成一个菊花,合并两个连通块需要一条额外边。记录额外边的个数,并且维护连通块大小,每次选最大的若干个连通块合并即可。

代码:Submission #137567369 - Codeforces

E

考虑 dp:令 \(f_{i,0/1/2}\) 表示到 \(i\) 接了长度为 \(0/1/2\) 的子序列最小花费代价。转移显然,用线段树维护即可。

代码:Submission #137568052 - Codeforces

F

考虑建立小根笛卡尔树和大根笛卡尔树。当左端点取到 \(l\) 时,很容易求得如果此时要求答案区间最小值为 \(x\) 的话,右端点应当取到的区间。最大值同理。

将所有数按照 \(\mathrm{popcount}\) 分组,每一组分别计算答案。如果一个可能的右端点被最大值右端点合法区间覆盖过,并且被最小值右端点合法区间覆盖过,那么可取。因为最大值右端点合法区间互不相交(最小值合法区间同理),用线段树维护覆盖次数,当覆盖次数为 \(2\) 则意味着合法。时间复杂度 \(O(n\log n)\) 。

代码:Submission #137566518 - Codeforces

G

注意到最终序列长度为 \(n+m-1\) 。将两个序列差分,除了 \(a_1,b_1\) 必须在开头外,剩下的一定是从小到大排序更优。因为题目保证 \(a,b\) 差分后除去开头满足单调不减,所以用线段树维护 \(b\),每次询问考虑插入 \(a\) 的每一个位置计算贡献即可。时间复杂度 \(O(qn\log m)\) 。

代码:Submission #137569481 - Codeforces

H

不会。

上一篇:时间戳转化为yy-mm-dd等


下一篇:NOIP 前做题