某岛

… : "…アッカリ~ン . .. . " .. .
November 29, 2021

Deltix Round, Autumn 2021

于是成功的在筹办新一轮 CF Round 之前打回黄名了。。。(求轻喷。。。
这场题目中规中矩,想上分还是挺容易的。。。

https://codeforces.com/contest/1609

Problem A. Divide and Multiply

把所有 2 因子收集起来,剩下的数里挑一个最大的乘以这些 2 因子,再加上余下的数即可。

Problem B/E. William the Vigilant/William The Oblivious

这两个放在一起说,给定一个 abc 字符串,
每次修改一个字符,问至少需要几次修改操作,可以使得该串中不存在 “abc” 模式的 子串/子序列。

子串的情况讨论讨论即可。
子序列的情况先解决静态的问题,然后用线段树维护即可。

Problem C. Complex Market Analysis

先筛法做素数判定,然后按照模数分段线性扫描,每次找到素数的时候看两边各有多少个 1。
假设左边和右边分别有 p 个 1 和 q 个 1,那么对答案的贡献就是 (p+1)*(q+1)-1。

Problem D. Social Network

读题鸭梨巨大。。

第一遍读完感觉是每次加一条边,看传递闭包里的最大度数,这个只要 DSU 维护连通分量的大小即可。
写完发现样例不对,再读一遍,发现给的边是要求在传递闭包中成立,在满足前 i 组成立的情况下,至多加 i 条边,原图中最大的连通分量大小。
只要稍微改改,开个 map 维护每个连通分量的大小,然后每次出现冗余条件是,就可以多取一个连通分量,每次取最大的几个即可。

Problem F. Interesting Sections

给定一个数列,问有多少组区间 ,使得区间中,最小数和最大数的二进制有相等数目的 1。

感觉比赛时想偏了,用了某种求最大子矩阵的 排序+插入 合并区间的方法。。。
好像只要普通的分治就可以了。。。
不过似乎也可以不分治。