CodeForces 中分段 随机挑战 Part1

· · 个人记录

\large \bf\text{Task Clear}

评分机制

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

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

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

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

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

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

评测记录

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

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

------------ 经典。对于给出的字符串 $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

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

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

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

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

不写代码。

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

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

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

评测记录

题意 ：给出两个 n 个点的森林，标号对应。

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

最大化 |E| ，给出构造。

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

记 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 对情侣围成一圈坐在桌子边上，食物有两种，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的。

构造一种可行分配方式。

------------ **评价** ： - $\ $ **CF Difficulty** : $2600

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

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

评测记录

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

值域 2^n ，n\leq 22。

评价 ：

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

建立辅助图 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 。

评价 ：

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

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

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

注意到 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 。

评价 ：

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

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

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

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

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

评测记录

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

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

评价 ：

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

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

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

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

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

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

评测记录 （欧拉回路）

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

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

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

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

评测记录

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

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

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

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

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

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

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

评测记录

评价 ：

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

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

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

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

评测记录

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2600

显然每个数的质因子数目 \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 个单词中正确单词的数量平方的异或和。

------------ **评价** ： - $\ $ **CF Difficulty** : $2700

（不过在当时可能得分会好看一些）

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

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

评测记录

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

------------ **评价** ： - $\ $ **CF Difficulty** : $2500

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

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

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

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

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

评测记录