Deltix Round, Autumn 2021
source link: http://www.shuizilong.com/house/archives/deltix-round-autumn-2021/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
于是成功的在筹办新一轮 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。
感觉比赛时想偏了，用了某种求最大子矩阵的 排序+插入 合并区间的方法。。。
好像只要普通的分治就可以了。。。
不过似乎也可以不分治。
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK