command_block 的博客

command_block 的博客

CodeForces 中分段 随机挑战 Part1

posted on 2021-11-29 16:38:42 | under 记录 |

$$\large \bf\text{Task Clear}$$

  • 第一印象,感觉 CF 的题目都不是很有趣,但比较真实。

    如果说 AT 是浪漫主义,那么 CF 就是现实主义吧。但是最近 AT 也越来越怪了(

  • 做了一些题,CF 的题目比较单薄,等水平通过率方差较大,区分度较低。

    一者刷题成本低(只要你善于抛弃),二者可以锻炼反复冲击解法的能力,强化稳定性,好!

  • 好多憨憨数据结构题,麻了……

评分机制

由 $1\sim 10$ 的数字与一个概括词组成。

  • 思维 Fineness :

    • $1\sim 2$ 几乎不用动脑子

    • $3\sim 4$ 有套路可以依靠 / 性质能显式的观察

    • $5$ 可以被称之为“思维题”的下界

    • $6\sim 7$ 以思维为核心的题目的难度

    • $8\sim 10$ How ____'s mind work?

  • 实现 Mass :

    • $1\sim 2$ 写代码就和吃饼干一样简单

    • $3\sim 4$ 熟练的选手可以快速解决战斗

    • $5\sim 6$ 中等身材

    • $7\sim 8$ 可以承受的胖

    • $9\sim 10$ 难以承受的胖

  • 质量 Quality :

    • $1\sim 2$ 出题人不会出题赶紧找个厂子上班

    • $3\sim 4$ 还算有点东西,但同时也有着明显的缺陷

    • $5$ 作为比赛题目的及格线

    • $6\sim 7$ 在同类中没有关键缺陷,良品

    • $8\sim 10$ 罕见的好题

  • .#1 CF1225F Tree Factory

题意 : 给出一棵 $n$ 个节点的有根树 $T$,点编号为 $0\sim n-1$ ,。记 $f_u$ 为 $u$ 的父节点,满足 $f_u<u$ 。

初始时你可以选择任意一种链 $L$ (标号任意),每次操作你可以令 $f_u\leftarrow f_{f_u}$ 。

需要将链改造为 $T$ ,构造一种操作数目最少的方案。

$n\leq 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(6)$ 观察
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 轻
  • $\ $ 质量 Quality : $(6.5)$

  • 口胡情况 : 看错题……以为要标号对应,结果是可以自己指定链的标号。

    (真实情况是,当年打这场的时候没做出来)

首先将整个操作过程时间倒流,可以看做每次将某点指向兄弟,需要将树变为链。

  • 操作数下界 :记原树长链长度为 $d$ (点数),每次操作最多使得树的长链长度增加 $1$ ,需要增加到 $n$ ,故操作数至少为 $n-d$ 。

每次找出最深的节点 $x$,向祖先找出第一个分叉 $x\to....\to a\to u\leftarrow b$ ,将 $a$ 连向 $b$ 可以使得 $x$ 的深度增加 $1$ 。达到下界。

评测记录


题意 : 有一个长度为 $n+2$ 的字符串 $S$ 。

给出每种长度为 $3$ 的字符串在 $S$ 中的出现次数,构造一种符合条件的 $S$ ,或指出无解。

$n\leq 2\times 10^5$ 。


经典。对于给出的字符串 $xyz$ ,看做有向边 $xy\to yz$ 跑欧拉路径。

不写代码。


题意 : 维护序列 $A$ ,支持下列操作 :

  • 将 $A[l,r]$ 循环右移一位。

  • 查询 $A[l,r]$ 内 $k$ 的出现次数。

    $n,q\leq 10^5$。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(3)$ 套路
  • $\ \ \ \,\, $ 实现 Mass : $(6)$ 制式
  • $\ $ 质量 Quality : $(5)$ (考虑到各种奇怪做法都能过)

  • 口胡情况 : 5min。$\color{green}\bf\Delta$

静态问题中,每个颜色维护个 vector 然后二分即可。

每次循环右移操作只会影响 $A[r]$ 的相对顺序。

用一棵平衡树维护相对顺序编号, $n$ 个平衡树维护每种颜色。

复杂度 $O(n+q\log n)$。

不写代码。


题意 :将 $1\sim n$ 分成尽可能多的对子,使得每一对的 $\gcd>1$ ,且对子的数目尽量多。构造方案。

$n\leq 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(6)$ 观察与尝试
  • $\ \ \ \,\, $ 实现 Mass : $(2)$ 简
  • $\ $ 质量 Quality : $(5)$ 启发式

  • 口胡情况 : 10min。估计了上界,此外没啥头绪。$\color{blue}\bf\Delta$

从大到小枚举质数 $p$ ,找出目前所有未匹配的 $p$ 的倍数,两两匹配(若有奇数可能会剩下一个,保留 $2p$)

可以发现,除了 $2p>n$ 的质数 $p$ 与 $1$ ,其余都参与了匹配(可能由于奇数剩一个),达到上界。

  • 总结 : 多试试看,不一定要等到安定点的征兆出现,一步迈过也是很可能的。

评测记录


题意 :给出两个 $n$ 个点的森林,标号对应。

指定一个边集 $E$ ,满足在 $F_1,F_2$ 中都加入 $E$ 后仍然都是森林。

最大化 $|E|$ ,给出构造。

$n\leq 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(6.5)$ 归纳与构造、观察
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 轻
  • $\ $ 质量 Quality : $(7.5)$ 自然

  • 口胡情况 : 10min 证明结论。20min 构造。$\color{green}\bf\Delta$

记 $m_1,m_2$ 分别为两个森林的边数。观察样例可猜想,最终 $|E|=\min(n-1-m_1,n-1-m_2)$ 。

考虑归纳证明之。不妨设 $m_1>m_2$ 当 $m_1=n-1$ 时 $|E|$ 显然为 $0$ 。

否则,若能成功找出一条边,则转化为 $m_1,m_2$ 均加一的子问题。

随意找点 $u$ ,查看 $F_1$ 中的对应联通块 $A$ 与 $F_2$ 中的对应联通块 $B$ 。

若 $A\supseteq B$ ,由于 $m_1<n-1$ ,故 $A\neq U$ (全集) ,因此可以找出任意一个 $c\in\overline A$ 并连接 $c,u$ 。

若 $B\supseteq A$ ,则任选 $c\in \overline B$ 并连接 $c,u$ 。

对于其他情况,取 $c\in A,c\notin B,v\in B,v\notin A$ 并连接 $c,v$ 。

这玩意引出了一种构造,但复杂度很垃圾……

对于 $1$ ,枚举 $v=2\sim n$ 尝试连边 $(1,v)$ 。完成后,记 $1$ 在 $F_1$ 中的对应联通块 $A$ 与 $F_2$ 中的对应联通块 $B$ ,必然有 $A\cup B=U$ 。

若 $A,B\neq U$ ,记 $A'=U-B,B'=U-A$ ,找出 $A',B'$ 中所有联通块,一一对应连边。

不难验证正确性。

评测记录


题意 : 有 $n$ 对情侣围成一圈坐在桌子边上,食物有两种,要求情侣不能吃同一种食物,并且桌子上相邻的三个人的食物必须有两个人是不同的。

构造一种可行分配方式。

$n\leq 10^5$。


评价

  • $\ $ CF Difficulty : $2600$
  • 思维 Fineness : $(6)$ 建模(特征)
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 轻
  • $\ $ 质量 Quality : $(5)$ 启发式

  • 口胡情况 : 15min 毫无头绪。图论建模无法处理三个人之间的影响。$\color{red}\bf\Delta$

强制 $2i,2i+1$ 不能食用相同食物,限制比原问题更强。

可以发现问题变为了二分图染色,且由于必然交替走桌子边和情侣边,没有奇环,必定有解。

  • 总结 : 构造题可以适当地强化性质(简化决策空间),总之,想不懂就试试看。

评测记录


题意 : 给出含 $m$ 个自然数的集合 $S$ 。若两个数 and 起来为 $0$ 则连边,求图中联通块数目。

值域 $2^n$ ,$n\leq 22$。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(5)$ 模拟经典算法
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 轻
  • $\ $ 质量 Quality : $(6)$

  • 口胡情况 : 25min 搞出个 $O\Big(\binom{n}{n/3,n/3,n/3}\Big)$ 奇怪做法,然而并不能过,似乎可以扩展。$\color{red}\bf\Delta$

考虑求联通块数目的方法:从每个点出发搜索,并打标记,看出发了几次。

建立辅助图 $G$ ,其中 $x'\in G$ 连向数字 $x$ (若存在),并连向所有 $x'$ 去掉一位的 $y'$ 。

这样, $x'$ 就能到达所有 $x$ 的子集。

将数字 $x$ 与 $(\neg x)'$ 连边。

然后大力搜索就是。复杂度 $O(n2^n)$。

  • 总结 :降智。“联通块数目”比“生成树”要弱,具体弱在哪里,可以去观察经典的算法。

评测记录


题意 : 有一个由 $n$ 个点 $m$ 条边组成的 DAG ,每个点出度至多为 $2$。

您需要标记一些点(不超过 $\lfloor \frac{4}{7}n\rfloor$ 个)。标记一个点 $u$ 将会删除所有与 $u$ 连接的边。

构造一种标记点的方案,使得删边后的图中每一条路径至多有一条边。

多组数据,$\sum n\leq 2\times 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$ (怎么才这么点?)
  • 思维 Fineness : $(6.5)$ 观察+验证
  • $\ \ \ \,\, $ 实现 Mass : $(4)$ 轻+细节
  • $\ $ 质量 Quality : $(6)$ 启发式

  • 口胡情况 : 很有自知之明,看到 $4/7$ 就直接开题解了。$\color{red}\bf\Delta$

对于合法方案 $S$ ,记剩余的(长为一的)路径中源点集合为 $A$ ,终点集合为 $B$ 。若一个点没有边相连,则加入 $A$ 。

考虑 $A,B,S$ 在原图中表现的性质,以下是一组充分条件:

  • $A$ 的入边全都来自 $S$ ;出边全部指向 $B$ 或 $S$
  • $B$ 的入边中存在一个来自 $A$ 的,其余都来自 $S$;出边全都指向 $S$ 。

拓扑排序的同时维护集合 $A,B,S$ ,添加点 $u$ 时:

  • 若 $u$ 点入度为 $0$ ,加入 $A$
  • 若 $u$ 点的入度都来自 $S$ ,加入 $A$
  • 若 $u$ 点的入度存在一个来自 $A$ ,其余都来自 $S$ ,加入 $B$
  • 其余情况加入 $S$ ,可以发现此时至少存在一个入度来自 $B$

注意到 $B$ 的每个点都有一个入度来自 $A$ ,根据图的性质有 $|B|\leq 2|A|$ ,类似地有 $|C|\leq 2|B|$ ,可以说明 $|S|\leq \frac{4}{7}(|A|+|B|+|S|)$ 。

评测记录


题意 : 维护一个 $n\times n$ 的矩阵 $A$,满足每行每列都是排列。

执行 $m$ 次如下操作。

  • 将矩阵 上/下/左/右 循环位移一次。
  • 将矩阵的每个 行/列 的排列求逆。

多组数据,$\sum n\leq 1000,\sum m\leq10^5$ 。


评价

  • $\ $ CF Difficulty : $2700$
  • 思维 Fineness : $(6.5)$ 刻画
  • $\ \ \ \,\, $ 实现 Mass : $(3.5)$ 轻
  • $\ $ 质量 Quality : $(8)$

  • 口胡情况 : 想懂了一维的情况。$\color{blue}\bf\Delta$

为了方便将标号与值都减一,变为 $0\sim n-1$ 。

将 $A_{i,j}$ 看做三元组 $(i,j,A_{i,j})$ 。

对于三元组 $(a,b,c)$ :

  • 循环位移可以看做将 $a,b$ 加减 $1$ ,模 $n$ 。

  • 行求逆是交换 $a,c$ ,列求逆是交换 $b,c$ 。

维护三元置换与每个位置的 $\Delta$ 即可描述操作的影响,然后 $n^2$ 个三元组分别通过。

复杂度 $O(n^2+m)$ 。

评测记录


题意 : 给定 $n$ 个整点,你要给每个点染成红色或蓝色,要求同一水平线或垂直线上两种颜色的数量最多相差 $1$。

构造一种方案。多组数据, $\sum n\leq 2\times 10^5$ 。


评价

  • $\ $ CF Difficulty : $2600$
  • 思维 Fineness : $(5.5)$ 模型
  • $\ \ \ \,\, $ 实现 Mass : $(4)$ 轻细节
  • $\ $ 质量 Quality : $(7)$

经典题,这里直接记两种做法好了。

将点 $(x,y)$ 看成 $x\rightarrow y$ 。 我们需要为每一条边定向, 使得每一个点的入度与出度的差不超过 $1$ 。

  • 欧拉回路

可以转化成欧拉回路,对于偶度点入度等于出度, 而奇度点的点入出度恰好差 $1$ 。

我们将奇度点连一条边到一个虚拟点,对新图跑欧拉回路对边定向即可。

  • 二分图染色

对于 $x$ 或 $y$ 相同的点,将其尽量两两配对并连边,直到每个 $x$ 或 $y$ 至多对应一个点。

得到的图是二分图,任意一种二分图染色即为答案。

  • 方案的正确性 : 每条直线的每个对子贡献都是 $0$ ,可能的剩余点贡献是 $\pm 1$ 。

  • 为什么是二分图 : 路径总是横纵交替,不可能存在奇环。

评测记录 (欧拉回路)


题意 :给定 $n$ 个正数。每次可以选择将一个数 $\pm 1$ 。求至少多少次操作使得整个序列都是正数且全部元素的 $\gcd>1$。

$n\leq 2\times 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(6)$ 蒙皮的套路
  • $\ \ \ \,\, $ 实现 Mass : $(3.5)$ 轻
  • $\ $ 质量 Quality : $(6)$ 有点无趣

鉴于之前见过这题,直接给做法好了。

  • 将所有奇数 $+1$ 是合法方案 : $ans\leq n$

  • 至少有一半的数最终不变, $+1$ ,或 $-1$

    若不止,则 $ans$ 超过上界。

随机找出某个数,枚举 $+1,0,-1$ ,分解质因子后容易得到其余数的最优策略。

复杂度为 $O\Big(\sqrt{A}+\big(\sqrt{A}/\log A+nw(A)\big)\log \epsilon\Big)$ 。

评测记录


题意 :你现在要整理书架上的 $n$ 本书,每本书有一个颜色 $a_i$ ,当每种颜色的书都摆在一起时书架上便整齐了,你每次可以将一本书放到序列最右端,问使书架上整齐的最小操作数。

$n\leq 5\times 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(5.5)$ 观察
  • $\ \ \ \,\, $ 实现 Mass : $(3.5)$ 轻
  • $\ $ 质量 Quality : $(6.5)$

  • 口胡情况 : 15min 想了两个假做法,很接近正解了。 $\color{blue}\bf\Delta$

显然同一本书至多移动一次,将问题转化为至多不移动的书的数目。

考虑一种保留的方案是否合法,必要条件是:各颜色区间不交。

对于非最后一个颜色,要保证一旦保留就要保留全部。

对最后一段颜色,可以只保留一个后缀。(合法方案:先移这种颜色,再移其他颜色。其余保留方案都不是最优的)

记颜色 $c$ 的区间为 $[l_c,r_c]$ ,权值为 $c$ 的出现次数。记 $f_i$ 为 $[1,i]$ 中能保留的不交区间权值的最大值,容易转移。

然后枚举最后一段颜色的保留情况。

评测记录


评价

  • $\ $ CF Difficulty : $2600$
  • 思维 Fineness : $(5.5)$ 观察
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 轻
  • $\ $ 质量 Quality : $(6.5)$ 自然

  • 口胡情况 :看错题一次,看对题很快就想出来了。$\color{green}\bf\Delta$

对 $x_i>x_j$ ,连边 $i\rightarrow j$ ,显然成环无解。

考虑我们放 $\forall$ 的位置,若有两个称祖孙关系则不合法。

单独考虑每个位置放 $\forall$ 是否合法,充要条件是祖孙内没有更早放置的点。正反 DP 一次即可判定。

不难发现把所有满足条件的都置为 $\forall$ 是合法的。

评测记录


题意 :给一些数,每个的因数个数不超过 $7$ ,求最少选出多少个,使得乘积为完全平方。给出最小个数,或指出无解。

$n\leq 10^5,A\leq 10^6$ 。


评价

  • $\ $ CF Difficulty : $2600$
  • 思维 Fineness : $(5.5)$ 建模,观察
  • $\ \ \ \,\, $ 实现 Mass : $(4.5)$ 轻+细节
  • $\ $ 质量 Quality : $(6)$

  • 口胡情况 : 看出了最小环。 $\color{blue}\bf\Delta$

显然每个数的质因子数目 $\leq 2$ 。

先考虑每个数都有两个次数为奇的素因子 $p_1,p_2$ ,可以看做无向边 $p_1\leftrightarrow p_2$ ,答案和环一一对应。

考虑只有一个次数为奇的素因子 $p$ 的情况,可以新建一个虚点 $S$ ,连边 $S\leftrightarrow p$ ,这样答案和环仍然一一对应。

求出最小环即可。注意到边中要么一端是 $S$ ,要么一段 $\leq \sqrt{A}$ ,环上至少有一个 $S$ 或 $\leq \sqrt{A}$ 的点,枚举这个点跑 BFS 即可。

(最小环一定是某个 BFS 树的树环)

复杂度 $O(A\sqrt{A}/\log^2A)$ 。

评测记录


题意 :给出 $n$ 个长度为 $3$ 的由 a ~ x 组成的单词,一个单词是正确的当且仅当其包含至少一个元音字母。

这里的元音字母是给定的 a ~ x 的一个子集。

对于所有元音字母集合,求这 $n$ 个单词中正确单词的数量平方的异或和。

$n\leq 10^4$ 。


评价

  • $\ $ CF Difficulty : $2700$
  • 思维 Fineness : $(2.5)$ 板
  • $\ \ \ \,\, $ 实现 Mass : $(3)$ 板
  • $\ $ 质量 Quality : $(3)$

(不过在当时可能得分会好看一些)


  • 口胡情况 : 一眼秒了。$\color{green}\bf\Delta$

很容易转化成:给出 $24$ 位二进制数 $n$ 个,枚举 $s=0\sim 2^{24}-1$ ,分别求出与 $s$ 有交的数的数目。

转化成与 $s$ 无交的数的数目,即 $s$ 的补集的子集,高维前缀和即可。

评测记录


题意 :给出序列 $A_{1\sim n}$ 与 $m$ 个下标集合 $S_{1\sim m}$ ,有如下 $q$ 次操作 :

  • 对于 $v\in S_i$ ,令 $f_v$ 加 $w$ 。

  • 求 $\sum_{v\in S_i}f_v$ 。

    $n,\sum|S|\leq 10^5$ 。


评价

  • $\ $ CF Difficulty : $2500$
  • 思维 Fineness : $(3.5)$ 套路
  • $\ \ \ \,\, $ 实现 Mass : $(5)$ 明
  • $\ $ 质量 Quality : $(6.5)$

  • 口胡情况 : 一眼秒了。$\color{green}\bf\Delta$

根号分治,将 $S$ 分为大集合和小集合。

预处理出 大集合与大集合,大集合与小集合 的交集大小,时空复杂度 $O(n\sqrt{n})$ 。

对于小集合,加法暴力做,然后计算对每个大集合询问的贡献。

询问时,暴力求和,再计算大集合修改的贡献。

大集合修改直接打 tag ,查询直接查表。

评测记录