CodeForces 中分段 随机挑战 Part1

$$\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](https://www.luogu.com.cn/problem/CF1225F) **题意** ： 给出一棵 $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$ 。达到下界。 [评测记录](http://codeforces.com/contest/1225/submission/137562135) ------------ - ## .#2 [CF508D Tanya and Password](https://www.luogu.com.cn/problem/CF508D) **题意** ： 有一个长度为 $n+2$ 的字符串 $S$ 。 给出每种长度为 $3$ 的字符串在 $S$ 中的出现次数，构造一种符合条件的 $S$ ，或指出无解。 $n\leq 2\times 10^5$ 。 ------------ 经典。对于给出的字符串 $xyz$ ，看做有向边 $xy\to yz$ 跑欧拉路径。 不写代码。 ------------ - ## .#3 [CF455D Serega and Fun](https://www.luogu.com.cn/problem/CF455D) **题意** ： 维护序列 $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)$。 不写代码。 ------------ - ## .#4 [CF449C Jzzhu and Apples](https://www.luogu.com.cn/problem/CF449C) **题意** ：将 $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$ ，其余都参与了匹配（可能由于奇数剩一个），达到上界。 - **总结** : 多试试看，不一定要等到安定点的征兆出现，一步迈过也是很可能的。 [评测记录](http://codeforces.com/contest/449/submission/137563042) ------------ - ## .#5 [CF1559D2 Mocha and Diana (Hard Version)](https://www.luogu.com.cn/problem/CF1559D2) **题意** ：给出两个 $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'$ 中所有联通块，一一对应连边。 不难验证正确性。 [评测记录](http://codeforces.com/contest/1559/submission/137563351) ------------ - ## .#6 [CF741C Arpa’s overnight party and Mehrdad’s silent entering](https://www.luogu.com.cn/problem/CF741C) **题意** ： 有 $n$ 对情侣围成一圈坐在桌子边上，食物有两种，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的。 构造一种可行分配方式。 $n\leq 10^5$。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2600$ - **思维 Fineness** : $(6)$ 建模（特征） - $\ \ \ \,\, $ **实现 Mass** : $(3)$ 轻 - $\ $ **质量 Quality** : $(5)$ 启发式 ------------ - **口胡情况** ： 15min 毫无头绪。图论建模无法处理三个人之间的影响。$\color{red}\bf\Delta$ 强制 $2i,2i+1$ 不能食用相同食物，限制比原问题更强。 可以发现问题变为了二分图染色，且由于必然交替走桌子边和情侣边，没有奇环，必定有解。 - **总结** ： 构造题可以适当地强化性质（简化决策空间），总之，想不懂就试试看。 [评测记录](http://codeforces.com/contest/741/submission/137563527) ------------ - ## .#7 [CF986C AND Graph](https://www.luogu.com.cn/problem/CF986C) **题意** ： 给出含 $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)$。 - **总结** ：降智。“联通块数目”比“生成树”要弱，具体弱在哪里，可以去观察经典的算法。 [评测记录](http://codeforces.com/contest/986/submission/137563782) ------------ - ## .#8 [CF1368E Ski Accidents](https://www.luogu.com.cn/problem/CF1368E) **题意** ： 有一个由 $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|)$ 。 [评测记录](http://codeforces.com/contest/1368/submission/137565598) ------------ - ## .#9 [CF1458C Latin Square](https://www.luogu.com.cn/problem/CF1458C) **题意** ： 维护一个 $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)$ 。 [评测记录](http://codeforces.com/contest/1458/submission/137566002) ------------ - ## .#10 [CF547D Mike and Fish](https://www.luogu.com.cn/problem/CF547D) **题意** ： 给定 $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$ 。 - 为什么是二分图 : 路径总是横纵交替，不可能存在奇环。 [评测记录](http://codeforces.com/contest/547/submission/137576762) （欧拉回路） ------------ - ## .#11 [CF1305F Kuroni and the Punishment](https://www.luogu.com.cn/problem/CF1305F) **题意** ：给定 $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)$ 。 [评测记录](http://codeforces.com/contest/1305/submission/137577959) ------------ - ## .#12 [CF1481E Sorting Books](https://www.luogu.com.cn/problem/CF1481E) **题意** ：你现在要整理书架上的 $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]$ 中能保留的不交区间权值的最大值，容易转移。 然后枚举最后一段颜色的保留情况。 [评测记录](http://codeforces.com/contest/1481/submission/137380041) ------------ - ## .#13 [CF1344C Quantifier Question](https://www.luogu.com.cn/problem/CF1344C) **评价** ： - $\ $ **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$ 是合法的。 [评测记录](http://codeforces.com/contest/1344/submission/137579269) ------------ - ## .#14 [CF1325E Ehab's REAL Number Theory Problem](https://www.luogu.com.cn/problem/solution/CF1325E) **题意** ：给一些数，每个的因数个数不超过 $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)$ 。 [评测记录](http://codeforces.com/contest/1325/submission/137581072) ------------ - ## .#15 [CF383E Vowels](https://www.luogu.com.cn/problem/CF383E) **题意** ：给出 $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$ 的补集的子集，高维前缀和即可。 [评测记录](http://codeforces.com/contest/383/submission/137582860) ------------ - ## .#16 [CF348C Subset Sums](https://www.luogu.com.cn/problem/CF348C) **题意** ：给出序列 $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 ，查询直接查表。 [评测记录](http://codeforces.com/contest/348/submission/137584400) ------------