2025年一月算法比赛（二）

[[ slider_text ]]

[[ item.c ]]

2025年一月算法比赛（二）

发布时间 2025-02-12 作者：zhangminchen 来源：算法小站

数位dp 交互题

## Codeforces Round 861 (Div. 2)
### E1
**[E1. Minibuses on Venus (easy version)](https://codeforces.com/contest/1808/problem/E1)**
**问题描述**
给你$$n, k$$，问存在多少个方案，满足$$n$$位数，数位和是$$S$$，同时存在一个位，位的数是$$x$$
满足$$(S - x) \bmod k = x$$，求方案数

**算法分析**
![](/media/content_img/CF861E1-1.png)
![](/media/content_img/CF861E1-2.png)

## Codeforces Round 853 (Div. 2)
### D
**[D. Serval and Shift-Shift-Shift](https://codeforces.com/contest/1789/problem/D)**
**问题描述**
两个数$$a, b$$，要将$$a$$改成$$b$$，可以进行以下操作若干次
选一个$$k \in [1, n]$$，并且把$$a$$改成以下两种中的任意一种
```math
a \oplus (a \ll k) \\
a \oplus (a \gg k)
```
现在需要你不超过$$n$$个操作，来把$$a \to b$$，请给出方案，或者判定不可能
不需要最小化操作次数，只需要输出方案，第一行输出操作次数，接着输出$$k$$，如果$$k > 0$$左移$$k$$位
否则表示右移$$k$$位，输出方案

**算法分析**
![](/media/content_img/CF853D1.png)
![](/media/content_img/CF853D2.png)
![](/media/content_img/CF853D3.png)
![](/media/content_img/CF853D4.png)

## Codeforces Round 922 (Div. 2)
### E
**[E. ace5 and Task Order](https://codeforces.com/problemset/problem/1918/E)**
给你$$n$$个任务，难度是$$1\to n$$表示，现在重新安排这些任务，构成$$1 \sim n$$的排列
这是一个交互题，要你猜这个排列是什么，如下交互

一开始出题人选择一个$$x \in [1, n]$$，接着 ace5 询问`? i`，问题的答案是
```bash
>,  如果 a[i] > x，之后 x += 1
<，如果 a[i] < x，之后 x -= 1
=，如果 a[i] = x，之后 x 不变
```
不超过$$40n$$次的询问，`! a_1 a_2 ... a_n`输出答案

**算法分析**

> 不难发现，如果给定一个$$k$$，可以在$$O(n)$$复杂度内，暴力确定$$a_k$$，此时$$x = a_k$$

如果完全暴力来做，那么每个元素问$$O(n)$$次，需要询问$$O(n^2)$$，是不可以的
这个时候，我们考虑**分治**，即对于每个元素，确定它的值，询问次数仍然是$$O(n)$$的
但我们只需要对$$O(\log n)$$段展开这样的询问即可

> 如果我们确定了$$x = a_k$$，我们还能确定什么？

我们能够确定每个下标，哪些元素$$< x$$，哪些元素$$> x$$，这像什么？**快排！**
于是我们可以考虑用快排的思想来求解

还有一个小问题，确定了$$x = a_k$$之后，再次询问其他元素$$(x, a_j)$$，会导致$$x$$值变化
怎么让$$x$$值不变呢？对$$(x, a_k)$$再询问一次就可以了
如果$$a_j < x$$，那么$$x = x - 1$$，之后$$a_j < x < a_k$$，`(? k)`再次询问，就可以改回来

> 借鉴快排的思想

对于$$x = a_k$$，$$k$$选择**随机化主元**，然后分成左右两段，分治求解

![](/media/content_img/CF922E.png)

上一篇：字符串算法（三）：Border 树下一篇：2025年2月写的一些codeforces题

看完文章有啥想法