算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
2026一月算法竞赛选题(三)
排序,交换环,数位dp,位贪心,最大团,曼哈顿距离,二分图, .....
[[ slider_text ]]
[[ item.c ]]
0
0
2026一月算法竞赛选题(三)
发布时间
2026-02-05
作者:
秋千月
来源:
算法小站
状态压缩dp
欧拉回路
## Codeforces Round 1077 ### C **[C. Restricted Sorting](https://codeforces.com/contest/2188/problem/C)** 给定序列`a`,找到最小的`K`,满足经过以下若干次交换,可以让`a`非严格单调递增 选择$$1 \leqslant i < j \leqslant j$$,其中要求$$|a_i - a_j| \geqslant K$$ **算法分析** 首先一定要有$$mx - mn \geqslant K$$,否则一定不能交换 二分一个`K`,那么$$mx, mn$$是可交换的 对于确定的$$a_i$$而言,$$\exists ?$$,满足$$|a_i - ?| \geqslant K$$ 1)对于$$? - a_i \geqslant K \Rightarrow a_i \leqslant (? - K)$$,只要$$\exists$$一个值就可以了 于是$$a_i \leqslant \max(? - K)$$,只有$$a_i > mx - K$$时候才不满足 否则一定有$$a_i \leqslant (mx - K)$$,也就是说,$$a_i$$可以**和`mx`交换** 2)另外一种情况$$a_i - ? \geqslant K$$也是类似的,只要$$a_i \geqslant (mn - K)$$ 就一定可以**和`mn`交换** 可交换的两个数,我们它们**在一个集合中**,于是我们就看看所有需要交换的位置是不是都在一个集合中即可 1)如果$$a_i, a_j$$是需要交换的,并且它们都可以和`mx`交换,那么用`mx`来作为**第三者**即可 ```bash mx, a[i], a[j],接下来 a[i], a[j] 分别和 mx 交换 a[i], mx, a[j] a[i], a[j], mx mx, a[j], a[i] ``` 2)对于`mn`的情况也是对称的 3)如果`a[i]`只能和$$mn$$交换,`a[j]`只能和$$mx$$交换呢?也是可以的,因为`mn, mx`是可交换的! ```bash a[i] mn a[j] mx mn a[i] mx a[j] --> 交换 mx,mn mx a[i] mn a[j] a[j] a[i] mn mx a[j] mn a[i] mx ``` ### D **[D. Shortest Statement Ever](https://codeforces.com/contest/2188/problem/D)** 给定两个数`x, y`,构造`p, q`,满足`p & q = 0`,并且$$|x-p| + |y - q|$$最小 **算法分析** 如果`x & y == 0`,那么直接让`p = x, q = y`,否则的话,需要对`x, y`**作出最小的调整** 选的`p, q`要尽量接近`x, y` > 贪心策略 从高位开始考虑,一开始`p = x, q = y`,**高位尽可能保持不动** 什么情况下高位可以保持不动呢?`( (p & q) >> i & 1 ) = 0`,即`(p, q) = {(1, 0), (0, 1), (0, 0)}` 都是可以的,都可以不去动这一位 当`( (p & q) >> i & 1 ) = 1`的情况,**这一位是一定要动**,并且可能会损失$$2^i$$的代价 > 往大了改 为什么是可能? 因为这一位一定要改出一个`0`,如果往大了改,$$p > x$$,那么要改成最接近的,$$> x$$的数 同时这一位又必须是`0`,所以此时`p += (1LL << i)`,这样改成`....1 00...0` 从`i...0`这些位都是`0` 当然也可能不改,不改的话,那么这个`1`会由低位的进位来消除,这种情况我们枚举低位的时候会考虑到 当然如果通过低位的进位来消除,损失的代价可能是$$2^j$$,更小 所以枚举每一个`p, q 都是 1 的位 i`,采取这种策略,`p = ??..?1 00....0`,从`i -> 0`这些位都是`0` 那既然**低`i`位**都是`0`,对于`q`而言,这些位放什么数也都没什么所谓了 最优解当然是和`y`保持一致 前缀呢?分两种情况(我们把`p, q`都为`1`的位,称为`p, q`**冲突**) 1)从高位到第`i+1`位,之前都没有过冲突,那么自然`p, q`和`x, y`保持一致即可 高位一致,低位又不去改它,自然此时`q = y`是最优的 2)如果之前有过冲突怎么办?我们是希望改`i`位,通过`+(1LL << i)`进位的方式 消除更高位的冲突,但不希望去破坏更高位,因为进位引入的`1`有可能使得前缀`p & q != 0`破坏了更高的位 怎么办呢?此时我们不可能修改`2`个位,$$2^i + 2^j, (j > i)$$的代价其实并不划算 因为我们可以构造`p = 011...1, q = 100...0`,此时修改`i`的代价$$\leqslant 2\cdot 2^i \leqslant 2^i + 2^j$$ 3)如果第`i`位发生冲突,之后通过更低的位`j`的进位来消除`i, j`位的冲突,会怎么样? 如果这种情况发生,那么`[i...j] = 11..1`,这些位都是`1`,进位如多米诺骨牌一样 如果第`i`位的冲突,被第`j, (j < i)`位消除了,并且不会破坏更高的位,那再好不过了 如果破坏了更高的位,那么`p, q`第`i+1`位都是`1`,此时我们除了需要$$2^j$$代价来消除冲突之外 还需要额外$$2^{i+1}$$的代价来修复高位的“破坏”,而$$2^{i+1} = 2^i + 2^i$$ 通过在`i`位操作`p = ....0 11...1, q = ....1 00...0`,损失的代价$$\leqslant 2 \cdot 2^i$$ **也是不劣的** **综上所述**,这样的操作,**只会在一个位去引入`1`**,即`+ (1LL << i)` 通过进位的方式,一次性消除更高位的冲突,`q = y`保持一致 > 往小了改,$$p < x$$最大的数,并且在第`i`位是`0` 那么形如`p = (高位和 x 一致) 0 111..1` 如果`x, y`在第`i`位发生冲突,我们从高位到低位找到第一个冲突的位 ```bash p = ...(和 x 的高位保持一致) 1 ....... q = ...(和 y 的高位保持一致) 1 ....... 可以这么修改 p = ...(和 x 的高位保持一致) 0 1 1 ... 1 q = ...(和 y 的高位保持一致) 1 0 0 ... 0 ``` 这样满足`(p & q) = 0`,并且损失$$\leqslant 2 \cdot 2^i$$,因为不涉及`+`的操作 所以高位并不会被破坏 另外,因为这个操作影响不到高位,所以不能指望通过低位的若干次操作合并来消除高位的冲突 只会一次性,改掉最高的,发生冲突的位,低位就都自动满足`p & q = 0`了 贪心地对$$p > x$$,`p`的第`i`位是`0`,并且`p 是 > x 的最小的满足条件的数` 以及$$p < x$$,`p`的第`i`位是`0`,并且`p 是 < x 的最小的满足条件的数` 对`ans`求一个`min`,对称地,对`q, y`的情况也做一遍即可 > 做法2,**数位 dp** ```bash // sp = 0,当前 p 还未填 // sp = 1,当前 p 已经填的高位 < x,之后不管怎么填都会 < x // sp = 2,当前 p 已经填的高位 > x,之后不管怎么填都会 > x auto dfs = [&](auto &dfs, int i, int sp, int sq) -> i64 { if (i < 0) return 0; auto &res = dp[i][sp][sq]; if (res < inf<i64>) return res; i64 wgt = 1LL << i; int bx = x >> i & 1, by = y >> i & 1; for (int mask = 0; mask <= 2; mask++) { auto bp = mask & 1, bq = mask >> 1 & 1; int nsp = sp, nsq = sq; if (sp == 0) nsp = (bp > bx) ? 2 : (bp < bx ? 1 : 0); if (sq == 0) nsq = (bq > by) ? 2 : (bq < by ? 1 : 0); i64 cost = 0; cost += 1LL * (nsp == 2 ? (bp - bx) : (bx - bp)) * wgt; cost += 1LL * (nsq == 2 ? (bq - by) : (by - bq)) * wgt; i64 dpv = dfs(dfs, i-1, nsp, nsq); if (chmin(res, dpv + cost)) { chose[i][sp][sq] = mask; to[i][sp][sq] = make_pair(nsp, nsq); } } return res; }; // 输出方案,(i, sp, sq) 表示当前状态 // chose(i, sp, sq) 表示当前这一位 p, q 应该分别填几 // to(i, sp, sq) = (nsp, nsq),下一位转移到什么状态 dfs(dfs, LOG, 0, 0); i64 ansp = 0, ansq = 0; int sp = 0, sq = 0; for (int i = LOG; i >= 0; i--) { auto mask = chose[i][sp][sq]; int bp = mask & 1, bq = mask >> 1 & 1; if (bp) ansp |= (1LL << i); if (bq) ansq |= (1LL << i); auto [nsp, nsq] = to[i][sp][sq]; sp = nsp, sq = nsq; } ``` ## Educational Codeforces Round 163 ### E **[E. Clique Partition](https://codeforces.com/problemset/problem/1948/E)** 给定`n, K`,`n`个点的图,顶点编号$$1 \sim n$$,初始时候没有边 给每个顶点分配一个整数`a[i]`,所有的`a[i]`构成$$1\sim n$$的排列 之后对于$$(i, j)$$,如果满足他们的曼哈顿距离(关于点$$(i, a_i)$$),$$|i - j| + |a_i - a_j| \leqslant K$$ 那么就在$$(i, j)$$连边,构造最大团(数量最小的团),每个顶点恰好属于一个团 **算法分析**  每$$k$$个分一个组,一共$$\lceil \dfrac{n}{k} \rceil$$个团 每一个组分别考虑,按上图所示的,`x`坐标两头配对构造 ## European Championship 2024 ### B **[B. Charming Meals](https://codeforces.com/contest/1949/problem/B)** 给定两个序列`a`和`b`,长度都是`n`,两两配对,要使得$$|a_i - b_i|$$最小值最大 **算法分析** 这是一个**结论题**,最优配对一定是`a, b`排序后,将`a`的一段前缀和**相同长度的`b`的后缀**配对 枚举配对前缀的长度即可 相同长度的前缀,后缀匹配,又可以和**循环移位**相对应,枚举`b`的循环移位就可以 ### I **[I. Disks](https://codeforces.com/contest/1949/problem/I)** 平面内有`n`个圆盘,每个圆盘的半径都是正整数,没有两个圆盘有重叠,但是圆盘之间可能相切 确定是否能够改变圆盘的半径,使得 1)原来相切的仍然相切 2)没有两个圆盘有重叠 3)所有半径的和严格减小 4)不能改变圆盘的中心 输出 yes 或者 no **算法分析** 每一组相切的圆构成连通分量,可以独立考虑,只要有一组能够满足“可减小半径”,答案就是`yes` 考虑一组连通分量,因为**不能改变圆盘的中心**,所以相切的两个圆,一个半径增加,另一个就要减小 并且$$(x_i - x_j)^2 + (y_i - y_j)^2 = (r_i + r_j)^2$$,$$(x, y)$$圆心是定值 因为要保持相切,$$r_i + \delta$$,那么就有$$r_j - \delta$$ 只要是相切,要想继续保持相切关系,每一组连通分量$$\delta$$就是**确定的** 那就看有多少个圆是$$+\delta$$,多少个圆是$$-\delta$$ 而相切的两个圆,必然是一个$$+\delta$$,一个$$-\delta$$,连边的话就构成了二分图 黑白二染色,如果`黑点的数量 != 白点的数量`,只要存在一个连通分量满足这个条件的话,答案就是`yes` ## Codeforces Round 937 (Div. 4) ### G **[G. Shuffling Songs](https://codeforces.com/contest/1950/problem/G)** 给定一个`n`首歌组成的播放列表,每一首歌给出$$(g_i, w_i)$$,表示`(流派,作者)` 现在需要删除一些歌曲,使得剩下的歌曲,存在一种排列 使得相邻两首歌,要么有相同的作者,要么属于相同的流派(或两者兼有) 问需要最少移除多少歌曲? **算法分析** > 错误的做法 拆点,流派和作者看作独立的点,那么对于歌曲$$i$$,$$(i, g_i), (i, w_i)$$连边 然后看一下这个图是否连通 这样做是不对的,因为**图连通不等于图中存在所有点组成的哈密顿路径(单链路径)** **反例如下** ```bash A (Pop,1) | B (Pop,2) —— D (Rock,2) —— C (Rock,3) | (作者都是2,互相连通) F (Jazz,2) | E (Jazz,4) (注:G 也在中间,和 B,D,F 连在一起,因为作者都是2) ``` > 尝试从哈密顿路径角度来考虑 哈密顿路径只能考虑**状态压缩**,记$$dp(mask, i)$$表示当前已经选的数的状态是`mask` 并且**以`i`结尾**(当然`i`必须是`mask`中为`1`的位) 枚举要加入哪个歌曲`j`(当然`j`必须是为`0`的位),有转移 ```bash if 歌曲 i 和歌曲 j 能匹配上 dp(mask | (1 << j), j) <--- dp(mask, i) + 1 ``` ## 2026牛客寒假算法基础集训营1 ### H **[Blackboard](https://ac.nowcoder.com/acm/contest/120561/H)** 给定长度为$$n$$的序列`a[1...n]`,其中由若干个`+`连接,即`a[1] + a[2] + ... + a[n]` 现在把一些`+`改成`|`,并且规定`|`的运算优先级更高,问有多少种改法 使得改了之后的结果和改之前相同 两种方案是不同的,当且仅当存在至少一个位置,使得在原来方案中,这个位置是`+` 而在新的方案中,这个位置是`|` **算法分析** 根据`a + b = (a | b) + (a & b)` 假设说对于位置$$i$$,如果$$i$$之前存在一个位置$$j$$,使得`a[i....j]`的位,**两两都是`0, 1`错开** 那么这部分的`(a & b)`就可以“擦去”,我们称可以将这些位置和$$i$$**合并** 很显然,对于特定的$$i$$,需要找到最左边的满足条件的`l` 这可以用双指针,维护一个全局的`cnt[0...31]`表示这每一位有`几个 1`,如果`max(cnt) > 1` 那么不合法,`l++` 这样我们可以知道$$j \in [l, i]$$,这些位置都可以和$$i$$合并 那么$$last = j - 1$$,存在转移 ```math \displaystyle dp(i) = \sum_{last \in [l-1, i-1]} dp(last) ``` 计算`dp`值的时候,维护前缀和`sum`,`dp[i] = sum[i-1] - sum[l-2]` 然后`sum[i] = sum[i-1] + dp[i]` ```bash dp[0] = 1, pre[0] = 1; int l = 1; vector<int> cnt(LOG+5, 0); auto add = [&](i64 x) -> void { for (int j = 0; j < LOG; j++) { if (x >> j & 1) cnt[j] += 1; } }; auto del = [&](i64 x) -> void { for (int j = 0; j < LOG; j++) { if (x >> j & 1) cnt[j] -= 1; } }; for (int i = 1; i <= n; i++) { add(a[i]); while (*max_element(cnt.begin(), cnt.end()) > 1) { del(a[l]), l++; } auto dpv = pre[i-1] - (l >= 2 ? pre[l-2] : 0); dp[i] = dpv; pre[i] = pre[i-1] + dp[i]; } cout << dp[n] << "\n"; ``` ## European Championship 2024 ### F **[F. Dating](https://codeforces.com/contest/1949/problem/F)** 软件有`n`个用户,编号是`1-n`,每个用户有一个偏好的活动列表,活动编号是`1-m` 如果两个用户都喜欢的活动个数$$\geqslant 1$$,并且两个用户都各自有至少一个自己喜欢而对方不喜欢的活动 那么这两个用户是匹配的,找到可能的匹配,或者报告不存在 **算法分析** 什么情况下认为是匹配,考虑**活动被覆盖了多少次** 如果存在$$\geqslant 1$$个活动被覆盖了`2`次,并且存在两个活动,被染成不同的颜色,那么这样陪配对就合法  只不过判断$$user_j \subseteq user_i$$的时候,不要用`std::include`,而是`for x in sma` **二分查找**`big`中是否含有`x` ### G **[G. Scooter](https://mirror.codeforces.com/contest/1949/problem/G)** 校园内有`n`栋建筑,编号从`1-n`。每栋建筑安排一堂数学课或一堂计算机课,或者没有安排任何课程(不能同时安排两门课) 此外,每栋建筑最多有一位教授,这位教授要么擅长数学,要么擅长计算机科学 选择车辆从任意顺序访问建筑,**每栋建筑只能访问一次**,要求行程结束后, 每栋安排了数学课的建筑必须有一位数学教授,每栋安排了计算机课的建筑必须有一位计算机教授 设计一条路线,使得所有课程都可以进行 车辆每次只能接受一名教授移动,并且不能将教授刚送走又接上 drive 每次只能去往不同的建筑 #### 简化版问题 **[简化版问题 C - Alternated](https://atcoder.jp/contests/abc421/tasks/abc421_c)** 给你一个长度为 2N 的字符串 S,S 中恰好包含了 N 个 A 和 N 个 B 求使 S 中没有相邻的相同字符所需的最少操作次数(可能为零),一个操作能交换 S 中相邻的两个字符 目标序列是确定的,要么是`ABAB...`,要么是`BABA...` 也就是说,`A`要么都在奇数位,要么都在偶数位,而一旦确定了`A`,`B`也就随之确定了 那么这样的问题,原序列`A`能去往的最优位置(交换代价最少)是确定的,比如目标序列`ABAB...` 第`1`个`A`去往`1` 第`2`个`A`去往`3` 第`3`个`A`去往`5` 以此类推,这样就能算出最优代价了 #### 供给-需求模型 假设说没有`-`会怎么样,发现如果`s[i] != t[i]`,是**无解的** 比如说要交换`C,M`,`到建筑 1 接送 C ---> 送到建筑 2,接下 M ---> 返回建筑物 1 送 M` 而这是无法完成的,因为题目规定一个建筑物只能访问一次(但路径可以折返交叉) 也就是说,**交换环,如果没有供应(入边)的话,是无解的** 所以可以对节点进行分类 ```bash 供给点: -M, -C 交换点: CM, MC 需求点: M-, C- ``` 针对这三类点,那么很显然应该从供给点取“教授”,**贪心地**,根据刚才的分析,如果所有供给点消失的话 交换点`(C, M), (M, C)`是无法被满足的 比如说从供给点`-C`取出`C`,接着应该**优先去往**交换点`CM`,如果所有交换点都被满足的话,才去到纯需求点`C-` 对于`M`也是类似的策略 #### 欧拉回路 但是这样做会`WA on testcases 34, invalid Pickup`,为什么? 因为这个问题中可能有**多余的供应**,比如说 ```bash demand: - C supply: C M ``` 最终的`(C, M)`的这一组 M 会被扔掉,晾在一旁不管它(不需要把教授接回家) > **一个点只能访问一次,想到了什么?欧拉回路!点的位置看成边的`id`,跑欧拉路径!**  将多余出来的形如`(C, M)`的边,将其供应端换成起点`-`(因为欧拉回路必须`indeg = outdeg`) 输出方案,建反图跑**欧拉回路**即可,可以用 Hierholzer 算法来输出方案
0
0
上一篇:2026一月算法竞赛选题(二)
已经是最后一篇啦
看完文章有啥想法
发布评论
15 人参与,0 条评论