GESP202512五级解析
第一题 数字移动
一、题意概述
给定一个长度为 \(N\)（\(N\) 为偶数）的序列 \(A\)，其中每个正整数恰好出现两次。
一次操作可以选择任意位置的一个数，将它移动到序列中的任意位置，花费等于该数字本身。
目标是通过若干次操作，使得 每一对相同的数字在序列中相邻，并且希望 每次操作的花费不超过某个最小的上限 \(x\)。
要求输出这个最小的 \(x\)。
二、核心观察
若某个数字的值为 \(v\)，移动它一次至少需要花费 \(v\) 点体力 因此：
- 当 \(v > x\) 时，该数字在限制条件下无法被移动
- 当 \(v \le x\) 时，该数字可以自由移动
这启发我们：
将数字分为 “可移动” 和 “不可移动” 两类。
三、二分答案的合理性
设 \(f(x)\) 表示：
是否存在一种方案，使得在 每次操作花费 ≤ \(x\) 的前提下，让所有相同数字相邻。
显然：
- 若 \(f(x) = \text{true}\)，则对于任意 \(x' > x\)，\(f(x')\) 仍然成立
因此，\(f(x)\) 具有 单调性，可以使用 二分答案。
四、可行性判定（关键）
假设当前二分的答案为 \(x\)。
思路
- 所有值 ≤ \(x\) 的数字都可以随意移动，我们可以“暂时忽略”它们
- 剩下的数字（值 > \(x\)）完全不能动，它们的相对顺序必须保持不变
于是问题转化为：
在保持原有顺序的前提下，所有不可移动的数字，是否能两两相邻？
判定条件
从左到右扫描所有 不可移动 的数字：
- 每个数字必须 连续出现两次
- 中间 不能夹杂其他不可移动的数字
只要出现以下情况之一，即无解：
- 两个相同数字之间夹着另一个不可移动的数字
- 某个不可移动的数字只出现了一次（无法配对）
五、判断函数实现
bool check(int x){
int pre = -1; // 待匹配的不可移动的数字
for (int i=1; i<=n; i++){
if (f[i] > x && pre == -1){ // 第一次出现不可移动的数字
pre = f[i];
} else if (f[i] > x && pre != -1){
if (pre == f[i]){ // 配对成功
pre = -1;
} else {
return false; // 配对失败直接返回false
}
}
}
return true;
}
六、完整代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans;
int f[N];
bool check(int x){
int pre = -1;
for (int i=1; i<=n; i++){
if (f[i] > x && pre == -1){
pre = f[i];
} else if (f[i] > x && pre != -1){
if (pre == f[i]){
pre = -1;
} else {
return false;
}
}
}
return true;
}
int main() {
cin >> n;
for (int i=1; i<=n; i++) cin >> f[i];
int l = 0, r=1e5;
while (l <= r){
int mid = (l + r) / 2;
if (check(mid)){
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans;
}
七、总结
本题关键在于：
- 识别 "每次操作花费上限"的二分单调性
- 将问题转化为 不可移动元素的相邻性判定
第二题 相等序列
一、题意概述
小 A 有一个包含 \(N\) 个正整数的序列 \(A=\{A_1,A_2,\ldots,A_N\}\)。小 A 每次可以花费 \(1\) 个金币执行以下任意一种操作：
- 选择序列中一个正整数 \(A_i\)（\(1\le i\le N\)），将 \(A_i\) 变为 \(A_i\times P\)，\(P\) 为任意质数；
- 选择序列中一个正整数 \(A_i\)（\(1\le i\le N\)），将 \(A_i\) 变为 \(\frac{A_i}{P}\)，\(P\) 为任意质数，要求 \(A_i\) 能整除 \(P\)。
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
二、核心观察
题目中说的“乘以一个质数”或“除以一个质数”，实际上就是在改变这个数字的质因数分解形式中，某个质因数的指数（加 1 或减 1）。
| 数字 | 质数 2 的指数 | 质数 3 的指数 | 质数 5 的指数 | 质数 7 的指数 |
|---|---|---|---|---|
| 10 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 35 | 0 | 0 | 1 | 1 |
| 105 | 0 | 1 | 1 | 1 |
| 42 | 1 | 1 | 0 | 1 |
关键思路：分而治之
这个题目的妙处在于：不同质因数之间的操作是互不影响的。 由于不同质数的指数变化 完全独立，我们可以：
-
对每一个出现过的质数 \(p\)
-
单独考虑所有 \(A_i\)中 \(p\) 的指数序列
- 计算把这些指数变成相同值的最小代价
- 对所有质数求和。
三、关键数学结论：中位数原理
在一组数中，使“总绝对偏差之和”最小的点，是中位数。
对于一列数，要想让所有数变成同一个数 \(k\)，且变化量的总和（距离之和）最小，这个 \(k\) 必须是这数列的中位数。
四、核心逻辑
对于某个质数 \(p\)，如果某个数不含 \(p\)，其指数视为 0， 但在代码中，我们只记录 非 0 的指数
分两种情况讨论：
- 非零指数个数 ≤ n/2: 说明至少一半的数本来就没有这个质因数，中位数为 0
- 非零指数个数 > n/2：超过一半的数含有该质因数，中位数指数是整体的中位数
for (int p: st){
if (mp[p].size() <= n/2){ // 非0数字小于 n/2
for (int c: mp[p]){
ans = ans + c;
}
} else {
mp[p].resize(n);
sort(mp[p].begin(), mp[p].end());
int k = mp[p][n/2]; // 取中位数
for (int c: mp[p]){
ans = ans + abs(c - k);
}
}
}
五、完整代码实现
#include <bits/stdc++.h>
using namespace std;
map<int , vector<int>>mp;
set<int> st;
int n, ans;
void init(int k){
for (int i=2; i*i <= k; i++){
int cnt = 0;
while (k % i == 0){
k/=i;
cnt++;
st.insert(i);
}
if (cnt != 0) mp[i].push_back(cnt);
}
if (k != 1){
st.insert(k);
mp[k].push_back(1);
}
}
int main(){
cin >> n;
for (int i=1; i<=n; i++){
int t; cin >> t;
init(t);
}
for (int p: st){
if (mp[p].size() <= n/2){ // 非0数字小于 n/2
for (int c: mp[p]){
ans = ans + c;
}
} else {
mp[p].resize(n);
sort(mp[p].begin(), mp[p].end());
int k = mp[p][n/2]; // 取中位数
for (int c: mp[p]){
ans = ans + abs(c - k);
}
}
}
cout << ans;
}
六、总结
本题关键在于：
- 把数值操作转化为质因数指数变化
- 利用不同质数之间的独立性进行分治
- 通过中位数原理最小化绝对代价