Problem C. Forsaken City

问题描述

给定一个整数序列 a ，你可以执行以下操作：选择序列的任意一个子序列，并将子序列中的每个元素都减 1。

请计算最少需要多少次操作才能使序列 a 变为非递减序列（即对于所有 ($1 \leq i < n$)，都满足 ($a_i \leq a_{i+1}$)）。

输入

  • 第一行包含一个整数 t（$(1 \leq t \leq 10^4$)），表示测试用例的数量。
  • 每个测试用例的第一行包含一个整数 n（($1 \leq n \leq 2 \times 10^5$)）。
  • 接下来一行包含 n 个整数 ($a_1, a_2, \ldots, a_n$)（($0 \leq a_i \leq 10^9$)）。

保证所有测试用例的 n 的总和不超过 ($2 \times 10^5$)。

输出

对于每个测试用例，输出最少需要的操作次数。

思路

  1. 问题分析：每次操作可以选择任意子序列减 1，这意味着对于每个元素，我们可以独立控制它被减多少次（只要不超过其初始值）。要使序列变为非递减，需要确保每个元素不大于它后面的元素。
  2. 核心观察：
    • 我们需要确定每个元素最终的取值 ($b_i$)，使得 ($b_i \leq a_i$) 且序列 b 是非递减的。
    • 最少操作次数等于最大的 ($a_i - b_i$)（因为每个元素需要被减的次数就是 ($a_i - b_i$)）。
  3. 贪心策略：从后往前遍历序列：
    • 最后一个元素的最终值可以保持不变（即 (b_n = a_n)）。
    • 对于前面的元素 (a_i)，其最终值 (b_i) 最多只能是 (b_{i+1})（以保证非递减），同时不能超过 (a_i)。
    • 当 ($a_i > b_{i+1}$) 时，需要将 ($a_i$) 减到 ($b_{i+1}$)，此时产生的操作次数为($a_i > b_{i+1}$)
    • 当 ($a_i \leq b_{i+1}$) 时，无需操作，直接将 ($b_i$) 设为 ($a_i$)。
  4. 结果计算：在遍历过程中记录最大的操作次数，这就是最少需要的总操作次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int min_val = a[n-1];  // 从最后一个元素开始
    int max_operations = 0;
    
    for (int i = n-1; i >= 0; --i) {
        if (a[i] > min_val) {
            // 需要将a[i]减到min_val，计算操作次数
            max_operations = max(max_operations, a[i] - min_val);
        } else {
            // 更新最小值为当前元素
            min_val = a[i];
        }
    }
    
    cout << max_operations << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

时间复杂度：($O(n)$) ，其中 n 是序列的长度。我们只需要遍历一次序列即可得到结果。

Problem F. The Correlation

问题描述

给定一个长度为 n 的整数序列 ($a_1, a_2, \ldots, a_n$)。你可以执行不超过 n 次操作：选择一个整数 v，并将每个数 ($a_i$) 更新为 ($|a_i - v|$)。

请找出执行一些操作后，序列中所有不同元素对的绝对差之和的最小值，即最小化 ($\sum_{1 \leq i < j \leq n} |a_i - a_j|$)。

由于答案可能很大，请输出这个最小和对 998244353 取模的结果。

输入

  • 第一行包含一个整数 n（($1 \leq n \leq 2 \times 10^5$)）。
  • 第二行包含 n 个整数 ($a_1, a_2, \ldots, a_n$)（($0 \leq a_i \leq 10^9$)）。

输出

输出最小可能的和对 998244353 取模的结果。

思路

  1. 奇偶性不变性：核心发现是每次操作 ($|a_i - v|$) 不会改变 ($a_i$) 的奇偶性。这是因为：
    • 偶数减去任何整数，结果的奇偶性不变
    • 奇数减去任何整数，结果的奇偶性不变
  2. 最小和的构成：
    • 设序列中奇数的数量为 b，则偶数的数量为 (n-b)
    • 奇数与偶数的差的绝对值至少为 1
    • 奇数之间和偶数之间的差可以通过操作变为 0
    • 因此最小可能的和为 ($b \times (n-b)$)
  3. 实现步骤：
    • 统计序列中奇数的数量
    • 计算奇数数量与偶数数量的乘积
    • 返回乘积对 998244353 取模的结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

// const int N=1e6+10;
const int MOD = 998244353;

void solve() {
    int n; cin>>n;
    vector<int> a(n);
    for (int i=0;i<n;++i) cin>>a[i];
    int t=*min_element(a.begin(),a.end());
    int b=0;
    for (int i:a) if ((i-t)%2) b++;
    cout<<((b%MOD)*((n-b)%MOD)%MOD)<<endl;
}

signed main(){
    FASTIO
    int _=1;
    // cin>>_;
    while (_--) solve();
}

解释

  • 时间复杂度：($O(n)$)，仅需一次遍历统计奇数数量

Problem G. Nice Doppelgnger

问题描述

给定一个正偶数 n，构造集合 (${1, 2, \ldots, n}$) 的子集 S，满足：

  1. ($|S| = \frac{n}{2}$)；
  2. 对任意 ($x, y, z \in S$)（可重复），乘积 $xyz$ 不是完全平方数。

输入包含 t 个测试用例，每个测试用例给定 n，输出满足条件的子集 S。

思路分析

通过分析完全平方数的质因数特征（所有质因数指数为偶数），结合 Liouville 函数 ($\lambda(x)$) 的性质实现构造：

  • Liouville 函数定义：对 ($x = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$)，($\lambda(x) = (-1)^{\sum e_i}$)。
  • 关键性质
    1. 完全积性：($\lambda(xy) = \lambda(x)\lambda(y)$)；
    2. 平方数的 ($\lambda$) 值为 1（因指数和为偶数）。

构造策略

选择所有 ($\lambda(x) = -1$) 的元素组成子集 S：

  • 对任意 ($x, y, z \in S$)，($\lambda(xyz) = \lambda(x)\lambda(y)\lambda(z) = (-1)^3 = -1$)；
  • 因平方数的 ($\lambda$) 值为 1，故 $xyz$ 不可能是平方数，满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e6 + 10;
int lambda[MAX_N];
vector<int> candidates;

void preprocess() {
    vector<int> min_prime(MAX_N);
    iota(min_prime.begin(), min_prime.end(), 0);
    lambda[1] = 1;  // 1的质因数和为0，λ=1

    for (int p = 2; p < MAX_N; ++p) {
        if (min_prime[p] == p) {  // p是质数
            lambda[p] = -1;  // 质数指数和为1，λ=-1
            for (int multiple = 2 * p; multiple < MAX_N; multiple += p) {
                if (min_prime[multiple] == multiple) {
                    min_prime[multiple] = p;
                }
            }
        } else {  // 合数，利用完全积性计算
            int p = min_prime[p];
            lambda[p] = lambda[p / p] * lambda[p];
        }
    }

    // 收集λ(x) = -1的元素
    for (int x = 1; x < MAX_N; ++x) {
        if (lambda[x] == -1) {
            candidates.push_back(x);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    preprocess();

    int t;
    cin >> t;
    while (t--) {
        int n, k = n / 2;
        cin >> n;
        // 选取前k个不超过n的候选元素
        auto it = upper_bound(candidates.begin(), candidates.end(), n);
        for (int i = 0; i < k; ++i) {
            if (i) cout << " ";
            cout << candidates[i];
        }
        cout << "\n";
    }
    return 0;
}

时间复杂度：预处理 ($O(N \log \log N)$)，单次查询 ($O(\log N)$)，适用于 ($n \leq 10^6$) 的约束。