Codeforces Round 1042 (Div. 3)
比赛概览
比赛信息
• 比赛链接：Codeforces Round 1042 (Div. 3)
• 时间：Aug/10/2025 22:35UTC+8
• 排名：812
• 解题数：5/8
• Rating变化：+42 (1581 → 1623)
A. Lever
link：A. Lever
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
In Divergent Universe, The Lever iterates itself given two arrays $a$ and $b$ of length $n$. In each iteration, The Lever will do the following:
- Choose a random index $i$ such that $a_i > b_i$. Then, decrease $a_i$ by $1$. If there does not exist such $i$, ignore this step.
- Choose a random index $i$ such that $a_i < b_i$. Then, increase $a_i$ by $1$. If there does not exist such $i$, ignore this step.
After each iteration, the Lever will check if step $1$ is ignored, and if so, it will end its iteration.
You’re given the two arrays. Find the number of iterations that the Lever does. It can be shown this number is fixed over all possibilities of random indices that The Lever can choose for each step.
输入格式
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains one integer $n$ ($1 \le n \le 10$).
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10$).
The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10$).
输出格式
Output
For each test case, output one integer — the number of iterations that the Lever does.
解题思路
请先自行思考然后再看题解喵
题意分析：
- 两个数组 a,b , 随机选取 符合条件的i，执行 1,2操作 若无法执行操作便跳过。
- 两个操作都执行完毕或者跳过后该次迭代才算完成
- ** i : $a_i > b_i$ **
- $a_i \text{ } - = \text{ } 1 $;
- ** i : $a_i < b_i$ **
- $a_i \text{ } + = \text{ } 1 $;
- 结束信号：操作1无法执行，在该次迭代后结束
思路：
- 模拟：
直接模拟每次每个i位置的执行情况，由于只有操作1决定迭代是否终止，所以我们只考虑对于 $a_i > b_i$ 的位置
每个位置会迭代 $a_i - b_i$ 次
然后累计迭代次数即可
代码实现
1 | # |
B. Alternating Series
Link：B. Alternating Series
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
You are given an integer $n$. Call an array $a$ of length $n$ good if:
- For all $1 \le i < n$, $a_i \cdot a_{i+1} < 0$ (i.e., the product of adjacent elements is negative).
- For all subarrays$^{\text{∗}}$ with length at least $2$, the sum of all elements in the subarray is positive$^{\text{†}}$.
Additionally, we say a good array $a$ of length $n$ is better than another good array $b$ of length $n$
if $[|a_1|, |a_2|, \ldots, |a_n|]$ is lexicographically smaller$^{\text{‡}}$ than $[|b_1|, |b_2|, \ldots, |b_n|]$. Note that $|z|$ denotes the absolute value of integer $z$.
Output a good array of length $n$ such that it is better than every other good array of length $n$.
$^{\text{∗}}$An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
$^{\text{†}}$An integer $x$ is positive if $x > 0$.
$^{\text{‡}}$A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:
- $a$ is a prefix of $b$, but $a \ne b$; or
- in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.
输入格式
The first line contains an integer $t$ ($1 \leq t \leq 500$) — the number of test cases.
The single line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of your array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
构造要求：
- 对所有的i属于 1-n,ai*ai+1 < 0 ，任意相邻两项异号（且对于任意i a_i !=0 )
- 任意子数组和大于0
- a , b两个序列比大小 -> 对比每一项绝对值，绝对值小的整体就小
目的
- 找到最小的合法序列
思路过程
- 首位
- 序列最小，显然对于第一位我们放 $+1$ 或者 $-1$
- 但倘若 $i$ 位置放 $+1$ 对于邻位($i-1$ 或者 $i+1$)只能放负数 $-x$，但显然对于这样子数组 $[1,-x]$，都会导致和为 $1-x < 1$ ($x \neq 0$) $\rightarrow$ 不为正数导致不合法
- 所以首位放 $-1$
第二位
- 在有了第一位是 $-1$ 的情况下，我们考虑第二三位
- 由于子数组要求和为正数，所以当我们填入负数时，应尽可能让绝对值小，从而让负的少了，正的就可以减小，实现整体数组在该题比较规则下变小
- 所以我们显然可知 负数都是 $-1$ —> 那么就会是 $[-1,; ?,; -1,; ?,; -1,; ?,; -1]$ 这样
- 对于任意 $[-1,; ?,; -1]$ 组合，$? - 2 > 0$ 所以 $?_{\text{min}} = 3$ —> $[-1,; 3,; -1,; 3,; -1,; 3,; -1,; 3]$
- 注意特殊情况，也就是最后一个数字也是 $?$ 的时候，由于 $[-1,; ?,; -1]$ 退化成了 $[-1,; ?]$，所以 $? - 1 > 0$ 此时 $?_{\text{min}} = 2$； ----> 那么就会是 $[-1,; 3,; -1,; 3,; -1,; 3,; -1,; 2]$ 这样
代码实现
1 | # |
C. Make it Equal
link：C. Make it Equal
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
Given two multisets $S$ and $T$ of size $n$ and a positive integer $k$, you may perform the following operations any number (including zero) of times on $S$:
- Select an element $x$ in $S$, and remove one occurrence of $x$ in $S$. Then, either insert $x+k$ into $S$, or insert $|x-k|$ into $S$.
Determine if it is possible to make $S$ equal to $T$. Two multisets $S$ and $T$ are equal if every element appears the same number of times in $S$ and $T$.
输入格式
Input
Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $ 1 \le k \le 10^9$ ) — the size of $S$ and the constant, respectively.
The second line contains $n$ integers $S_1,S_2,\ldots,S_n$ ($0 \le S_i \le 10^9$) — the elements in $S$.
The third line contains $n$ integers $T_1,T_2,\ldots,T_n$ ($0 \le T_i \le 10^9$) — the elements in $T$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
操作性质分析：
对于任意的 $x$ 和 $k$，由于我们可以对 $x$ 执行任意次操作（实际上是执行一次放回 $S$ 中再取出操作），最后就可以变成 $x + nk$ 或 $|x - nk|$
我们把 $x+nk$ 等价换成 $x \bmod k$，也就是用最小的 $(x+nk)$ 来代替 $x, x+k, x+2k, x+3k$。例如：
$$[x = 5,; k = 3] \rightarrow \text{用}; 2 ;\text{代表}; 5-3,;5,;5+3,;5+2\times3 \rightarrow [2,5,8,\ldots];\text{这一部分}$$对于 $|x - nk|$，实际上就是 $k - (x \bmod k)$。同样：
$$[x = 5,; k = 3] \rightarrow \text{用}; 3 - 5 \bmod 3 = 1 ;\text{代表}; |5-2\times3|,;|5-3\times3| \rightarrow [1,4,7,\ldots]$$但由于一个数有两种情况，我们为了避免重复计数，我们在 $[x \bmod k,; k-(x \bmod k)]$ 中选择小的，也就是小于等于 $\frac{k}{2}$ 的部分来代表 $x$
这样我们只需要统计 $S$ 中的代表，看 $T$ 中是否一一对应即可
代码实现
1 | # |
D. Arboris Contractio
link：D. Arboris Contractio
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
Kagari is preparing to archive a tree, and she knows the cost of doing so will depend on its diameter$^{\text{∗}}$. To keep the expense down, her goal is to shrink the diameter as much as possible first. She can perform the following operation on the tree:
- Choose two vertices $s$ and $t$. Let the sequence of vertices on the simple path$^{\text{†}}$ from $s$ to $t$ be $v_0, v_1, \dots, v_k$, where $v_0 = s$ and $v_k = t$.
- Remove all edges along the path. In other words, remove edges $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$.
- Connect vertices $v_1, v_2, \dots, v_k$ directly to $v_0$. In other words, add edges $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$.
It can be shown that the graph is still a tree after the operation.
Help her determine the minimum number of operations required to achieve the minimal diameter.
$^{\text{∗}}$The diameter of a tree is the longest possible distance between any pair of vertices. The distance itself is measured by the number of edges on the unique simple path connecting them.
$^{\text{†}}$A simple path is a path between two vertices in a tree that does not visit any vertex more than once. It can be shown that the simple path between any two vertices is always unique.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of the vertices in the tree.
The following $n-1$ lines of each test case describe the tree. Each of the lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) that indicate an edge between vertex $u$ and $v$. It is guaranteed that these edges form a tree.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
操作性质分析：
- 假设我们选的点是u , v ，其中u 到 v 的简单路径为 : u - x1 - x2 - x3 - x4 - v
- 操作之后 就会变成类似菊花图一样，以u 为中心， x1 x2 x3 x4 v 分布在四周
- 由于操作可以执行无限次，想要直径最小 == 最后的树变成一颗深度为1的菊花图 —> 以根为中心，连向所有节点 (u v1)(u v2)(u v3)这样
- 那我们不妨枚举每一个点 i 作为最后菊花图的根节点，那么对于其他节点，我们只需要选择叶子节点作为 v ,以 i 为 u
这样执行操作之后，所以的点会分布在 i 的四周 那么花费就是 除i和i的子节点外的叶子节点数
菊花图构造分析：
操作过程描述：
- 假设初始选择的点对为 $(u, v)$，其简单路径为：$u -> x_1 -> x_2 -> v$
- 操作后树结构变为以 $u$ 为中心的菊花图：
1
2
3u
/|\
x₁ x₂ v
最优性分析：
- 由于操作可无限次执行，最小直径的极限情况是深度为1的完美菊花图：
$$
\text{中心} \left{\begin{array}{l}
v_1 \
v_2 \
\vdots \
v_n
\end{array}\right.
$$ - 此时直径恒为2（任意两叶子节点通过中心连接）
- 由于操作可无限次执行，最小直径的极限情况是深度为1的完美菊花图：
枚举策略：
- 那我们不妨枚举每一个点 i 作为最后菊花图的根节点，那么对于其他节点，我们只需要选择叶子节点作为 v ,以 i 为 u
这样执行操作之后，所以的点会分布在 i 的四周 那么花费就是 除 [i] 和 [i的子节点] 外的[叶子节点数]。
代码实现
1 | # |
E. Adjacent XOR
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
You’re given an array $a$ of length $n$. For each index $i$ such that $1 \le i < n$, you can perform the following operation at most once:
- Assign $a_i := a_i \oplus a_{i+1}$, where $\oplus$ denotes the bitwise XOR operation. .
You can choose indices and perform the operations in any sequential order.
Given another array $b$ of length $n$, determine if it is possible to transform $a$ to $b$.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$).
The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < 2^{30}$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
- 特殊位置分析
- 对于最后一位 $a_n$ 和 $b_n$，由于没有下一位，所以如果 $a_n \neq b_n$ $\rightarrow$ NO
- 对于倒数第二位 $a_{n-1}$ 和 $b_{n-1}$，$a_{n-1}$ 可以变成 ${a_{n-1}, a_{n-1} \oplus a_n}$，我们判断是否有一种等于 $b_{n-1}$
- 对于倒数第三位 $a_{n-2}$ 和 $b_{n-2}$，$a_{n-2}$ 可以变成 ${a_{n-2}, a_{n-2} \oplus a_{n-1}}$ 此处 $a_{n-1}$ 要么是变化后的也就是 $b_{n-1}$ 要么就是原先的值也就是 $a_{n-1}$
所以 $a_{n-2}$ 其实可以变成 ${a_{n-2}, a_{n-2} \oplus a_{n-1}, a_{n-2} \oplus b_{n-1}}$。判断是否有一种和 $b_{n-2}$ 相同
- 一般位置的分析
- 以此往前的 $a_{n-3}, a_{n-4}$ 一直到 $a_1$ 其实和 $a_{n-2}$ 的操作一模一样
代码实现
1 |
|
F. Unjust Binary Life
time limit per test: 2 seconds
memory limit per test: 256 megabytes
题目描述
Yuri is given two binary strings $a$ and $b$, both of which are of length $n$. The two strings dynamically define an $n \times n$ grid. Let $(i, j)$ denote the cell in the $i$-th row and $j$-th column. The initial value of cell $(i, j)$ has the value of $a_i \oplus b_j$, where $\oplus$ denotes the bitwise XOR operation. .
Yuri’s journey always starts at cell $(1, 1)$. From a cell $(i, j)$, she can only move down to $(i + 1, j)$ or right to $(i, j + 1)$. Her journey is possible if there exists a valid path such that all cells on the path, including $(1, 1)$, have a value of 0.
Before her departure, she can do the following operation for any number of times:
- Choose one index $1 \le i \le n$, and flip the value of either $a_i$ or $b_i$ ($0$ becomes $1$, and $1$ becomes $0$). The grid will also change accordingly.
Let $f(x, y)$ denote the minimum required operations so that Yuri can make her journey to the cell $(x,y)$. You must determine the sum of $f(x, y)$ over all $1 \leq x, y \leq n$.
Note that each of these $n^2$ cases is independent, meaning you need to assume the grid is in its original state in each case (i.e., no actual operations are performed).
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).
The second line of each test case contains a binary string $a$ ($|a| = n$, $a_i \in {0, 1}$).
The third line of each test case contains a binary string $b$ ($|b| = n$, $b_i \in {0, 1}$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
- 首位分析
- 对于$[1,1]$位置，显然就是如果 $a_1 \neq b_1$ $\rightarrow$ $cost[1,1] = 1$;
- 普遍位置分析
- 假设我们目前所处的位置为 ${x,y}$ 我们可以向 ${右}$ 或者向 ${左}$ 移动 ，并且我们目前 $a_x == b_y$ （因为如果不相等，${x,y}$位置不可达）
若我们想往右移动 ，那么必然 $a_x = b_{y+1}$ , 又由于我们有 $a_x == b_y$ 从而得出 $b_y = b_{y+1}$
同理 往下移动的条件就是 $a_x = a_{x+1}$; - 因此假设我们想到达${x,y}$ (注意：此处的$x$，$y$和上面的$x$，$y$不一样，请仔细阅读)
我们必然有 $a_1 = a_2 = … = a_x$（向下移动的条件） 和 $b_1 = b_2 = b_3 = … = b_y$ （向右移动的条件） 以及 $a_x = b_y$ （${x,y}$可达的条件）
整理一下会发现，三个条件最后都可以用等于号连接，也就是让 $a_1 = a_2 = … = a_x = b_1 = b_2 = … = b_y$
也就是说，我们要让$a$在$x$和$b$在$y$的长度内都是一样的，要么都是$1$要么都是$0$
那我们需要修改的就是这一段中$min(1的个数,0的个数)$
- 如何高效计数
我们先预处理一下 $b$ 数组，创建一个
vector<Node> cnt，其中每个元素包含：$$ cnt1 = \text{表示1到i位置1的个数} $$
$$ cnt0 = \text{表示1到i位置0的个数} $$
$$ diff = cnt1 - cnt0 = \text{表示1和0的差值} $$
然后在对 $diff$ 进行排序 $\rightarrow$ 从而得到一个按照 $1$ 和 $0$ 数值差值排序的数组，在数组的前端是 $0$ 多的部分，数组后端是 $1$ 多的部分
然后我们在对该数组的 $cnt1$ 和 $cnt0$ 进行前缀和有了这些准备之后，我们在对 $a$ 从 $1$ 开始，计数 $cnt1$ 和 $cnt0$ ，并获取 $diff$，对于任意的 $a_i$ 位置，我们有 $diff$，也就是 $1$ 和 $0$ 的差值，那当 $b$ 中的 $diff + a$ 的 $diff$ 代表着两个总共的 $cnt1$ 和 $cnt0$，
由于我们想让操作数最小，也就是找到 $1$ 少还是 $0$ 少，
显然，当两者 $diff$ 相加就是 $cnt1 - cnt0$，当值是正数的时候，就是 $1$ 多，反之就是 $0$ 多，
所以我们用二分（因为 $b$ 数组的 $diff$ 是有序的）找到正负分界线，- 对于 $0$ $\rightarrow$ 分界线 我们选择把 $1$ 变成 $0$，
- 分界线 $\rightarrow$ $n$，我们选择把 $0$ 变成 $1$ 即可
总时间就是 $O(n \log n)$
代码实现
1 |
|
G. Wafu!
time limit per test: 3 seconds
memory limit per test: 256 megabytes
题目描述
To help improve her math, Kudryavka is given a set $S$ that consists of $n$ distinct positive integers.
Initially, her score is $1$. She can perform an arbitrary number of the following operations on the set if it is not empty:
- Let the minimum value of $S$ be $m$.
- Multiply her score by $m$.
- Remove $m$ from $S$.
- For every integer $i$ such that $1 \le i < m$, add $i$ to the set $S$. It can be shown that no duplicates are added during this step.
She is addicted to performing operations, but after $k$ operations, she realizes she forgot her score. Please help her determine her score, modulo $10^9+7$.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$).
The second line of each test case contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 10^9$, $s_i \neq s_j$) — the elements of the initial set $S$. It is guaranteed that the set $S$ is not empty before each of the $k$ operations is performed.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
解题思路
请先自行思考然后再看题解喵
此处的内容旅行家以后再来解锁吧
先写一点
- 类似于用二进制表示一个数
代码实现
1 |
|