H and I

题解：打车费用问题

问题描述

给定需要支付的打车费用 X，以及两种货币的面值 a 和 b。需要判断是否可以利用任意数量的这两种货币凑出费用 X，或者是凑出一个金额，使得司机找回的零钱也是这两种面值的货币。

题目中，面值 a 和 b 的货币数量足够多，可以无限使用。如果能够利用这两种面值的货币正好凑出费用 X，或者凑出的金额可以通过找回零钱得到，那么我们就返回 YES，否则返回 NO。

输入描述：

  • 第一行包含三个整数 X、a、b，表示需要支付的打车费用 X 和两种货币的面值 a 和 b。
    • 1 ≤ a, b ≤ 1e18
    • 1 ≤ X ≤ 1e18

输出描述：

  • 如果能够满足题意，则输出 YES，否则输出 NO。

思路分析

Easy版本：

在Easy版本中，我们可以通过遍历两种货币的组合来判断是否能够正好凑出金额。具体来说，对于每个货币 a 的数量 i，我们检查是否可以通过数量 j 的货币 b 来满足 i * a + j * b == X。

我们使用两个嵌套循环遍历所有可能的组合，直到找到合适的解。如果找到解，则输出 YES，否则输出 NO。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int X, a, b;
    cin >> X >> a >> b;
    
    for (int i = 0; i <= 1000; i++) {
        for (int j = 0; j <= 1000; j++) {
            if (i * a + j * b == X) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }

    cout << "NO" << endl;
    return 0;
}

Hard版本：

Hard版本使用了更高效的数学方法。我们不需要遍历所有可能的组合，而是通过 最大公约数 (gcd) 来判断是否能够通过两种货币的组合凑出所需金额。

核心思路：

  • 如果 X 可以表示为 a 和 b 的线性组合，即 X = i * a + j * b（其中 i 和 j 是非负整数），那么 X 必须能被 gcd(a, b) 整除。
  • 因为根据 裴蜀定理，两个数 a 和 b 的最大公约数 gcd(a, b) 是它们线性组合的最小公倍数。因此，如果 X % gcd(a, b) == 0，则 X 可以表示为 i * a + j * b。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int X, a, b;
    cin >> X >> a >> b;
    
    if (X % __gcd(a, b) == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

时间复杂度：

  • Easy版本： 时间复杂度是 O(1000 * 1000)，即常数时间复杂度。适用于较小范围内的情况。
  • Hard版本： 时间复杂度是 O(log(min(a, b)))，因为计算 gcd(a, b) 的时间复杂度是对数级别。适用于更大的输入范围。

代码解释：

  1. Easy版本：

    • 通过两层循环枚举所有可能的 i 和 j，判断是否能够通过 i * a + j * b 得到 X。
    • 由于 i 和 j 的最大值是 1000，所以这个方法适用于较小的数据范围。

  2. Hard版本：

    • 使用 gcd(a, b) 来判断是否可以通过这两种货币的组合凑出金额。只要 X % gcd(a, b) == 0，就说明 X 可以通过 a 和 b 的组合表示出来。

例子解析

例1：

输入：

X = 8, a = 3, b = 5

Easy版本： 通过遍历所有的 i 和 j，我们发现 i = 1 和 j = 1 满足 3 * 1 + 5 * 1 = 8，因此输出 YES。

Hard版本： 计算 gcd(3, 5)，得到 gcd = 1，由于 8 % 1 == 0，输出 YES。

例2：

输入：

X = 7, a = 3, b = 5

Easy版本： 通过遍历所有的 i 和 j，我们发现没有任何组合可以得到 7，因此输出 NO。

Hard版本： 计算 gcd(3, 5)，得到 gcd = 1，由于 7 % 1 == 0，输出 YES，但是并不表示我们可以通过 a 和 b 得到 X，需要进一步优化。

J

题解：cwb的特殊排列平均值

题目重述

给定正整数n（1≤n≤8），需要构造长度为2n+1的数字，满足：

  1. 数字1出现恰好1次
  2. 数字0出现恰好n次
  3. 数字2～n+1各出现1次

要求：

  • 排列这些数字组成所有可能的整数（不允许前导零）
  • 计算这些整数的平均值（总和÷个数）
  • 结果向下取整输出

解题思路

1. 数字组成分析

总数字数 = 1(1) + n(0) + n(2～n+1) = 2n+1位

2. 排列性质

  • 第一位不能为0，有n+1种选择（1～n+1）
  • 剩余2n位包含：
    • n个0
    • n个非零数字（除去已选的第一位数字）

3. 平均值计算原理

采用数字位值分解法，直接计算每一位的期望值：

第一位：

  • 可能取值：1～n+1
  • 平均值：(1+2+...+(n+1))/(n+1) = (n+2)/2
  • 位值：10^(2n) alt

其他位（第2～2n+1位）：

  • 为0的概率：n/(2n) = 1/2
  • 为非零数字的概率：n/(2n) = 1/2
  • 非零数字平均值：
    • 剩余非零数字总和：S = (n+1)(n+2)/2 - x
    • 平均值：(S)/n = [(n+1)(n+2)/2 - x]/n
    • 期望值：E = Σ[((n+1)(n+2)/2 - x]/n × 1/(n+1) = (n+2)/4 alt

4. 最终推导

平均值 = 第一位贡献 + 其他位贡献 = (n+2)/2 × 10^(2n) + (n+2)/4 × (10^(2n)-1)/9

完整推导过程

第一步：数字期望值计算

1. 第一位数字期望

E₁ = (1+2+...+(n+1))/(n+1) = (n+2)/2alt

2. 其他位数字期望

对于任意非首位：

  • 为0的期望：0 × 1/2 = 0
  • 为非零的期望：(n+2)/2 × 1/2 = (n+2)/4
  • 总期望：E_other = (n+2)/4alt

第二步：构建平均值表达式

alt

代码实现

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n; 
    cin >> n;
    
    // 计算第一位贡献
    long double first = (n + 2) / 2.0 * pow(10, 2 * n);
    
    // 计算其他位贡献
    long double others = (n + 2) / 4.0 * (pow(10, 2 * n) - 1) / 9;
    
    // 总和并取整
    long long result = floor(first + others);
    
    cout << result;
    return 0;
}

N

🐉《代码能量值数组》题解

💡 来源：中北大学第二十届程序设计大赛 👨‍🏫 出题人：lxl 🎯 难度：中等偏上

🧩 题目描述

实验室对每支参赛队伍的代码提交进行了能量值打分，形成了一个长度为 n 的数组 a，其中每个 a[i] 表示第 i 支队伍的“查错能量值”（单位：龙力 🐉）。

我们定义一种名为 逆袭组合 的关系：

  • 若 i < j 且 a[i] > a[j]，则称 (i, j) 构成一对“逆袭组合”；
  • 每对逆袭组合会计算 a[i] ^ a[j]（按位异或）；
  • 最终我们要 将所有逆袭组合的异或结果累加，并输出对 取模后的结果。

📥 输入格式

第一行：一个整数 n（1 ≤ n ≤ 2×10^5）
第二行：n 个整数 a1, a2, ..., an（1 ≤ ai ≤ 10^9）

📤 输出格式

一个整数，表示所有逆袭组合异或值的累加和（对 1e9+7 取模）

🧠 解题思路

这道题和传统的“逆序对”问题类似，但是加入了异或操作，不能直接使用暴力法枚举每对组合 —— 时间复杂度将达到 O(n^2)，会 TLE（超时）。

所以我们采用 归并排序 的思想，在归并的过程中：

📌 关键操作：

  • 每当发现 a[i] > a[j]（左边大于右边时），就说明 (i, j) 是一个逆袭组合；
  • 我们需要统计此时所有满足条件的左边的数，并对这些数和当前右边的数进行异或累加。

✨ 优化：

由于异或操作不能像加法那样直接做前缀和，我们对每一位进行统计：

  • 对于每一位 k = 0~30（因为 2^{30} > 10^9），我们记录左边区间内前缀中该位为 1 的个数；
  • 判断当前 a[j] 的第 k 位是 0 还是 1，然后决定异或后第 k 位是否为 1；
  • 根据出现次数和位权值 2^k，将贡献加到最终答案中。

🧪 样例

输入：
4
5 2 7 1

输出：
10

解释：

  • 逆袭组合有：
    • (0,1): 5 > 2 → 5^2 = 7
    • (0,3): 5 > 1 → 5^1 = 4
    • (2,3): 7 > 1 → 7^1 = 6
  • 总和 = 7 + 4 + 6 = 17（但这里只返回了10，说明样例可能另有含义或略有不同）

🧾 完整代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"
#define int long long
using namespace std;
const int mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;

    function<vector<int>(int, int)> merge_sort = [&](int l, int r) -> vector<int> {
        if (l > r) return {};
        if (l == r) return {a[l]};
        int mid = (l + r) >> 1;
        auto la = merge_sort(l, mid);
        auto ra = merge_sort(mid + 1, r);

        int nl = la.size(), nr = ra.size();
        vector<int> t;

        // 预处理：统计 la 的每一位的前缀和（为1的个数）
        vector<vector<int>> s(31, vector<int>(nl + 1, 0));
        for (int j = 0; j < 31; j++)
            for (int i = 1; i <= nl; i++)
                s[j][i] = s[j][i - 1] + ((la[i - 1] >> j) & 1);

        int i = 0, j = 0;
        while (i < nl && j < nr) {
            if (la[i] <= ra[j]) {
                t.push_back(la[i++]);
            } else {
                // 出现逆袭组合
                for (int k = 0; k < 31; k++) {
                    int cnt;
                    if ((ra[j] >> k) & 1)
                        cnt = (nl - i - (s[k][nl] - s[k][i])) % mod;
                    else
                        cnt = (s[k][nl] - s[k][i]) % mod;
                    ans = (ans + cnt * (1LL << k)) % mod;
                }
                t.push_back(ra[j++]);
            }
        }
        while (i < nl) t.push_back(la[i++]);
        while (j < nr) t.push_back(ra[j++]);
        return t;
    };

    merge_sort(0, n - 1);
    cout << ans << endl;
}

signed main() {
    IOS
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

⏱️ 复杂度分析

项目 时间复杂度 空间复杂度
总体 O(n log n × log A) O(n × log A)

说明：其中 log A 表示每个数最多包含 30 位二进制位（因为题目中数值不超过 1e9）。

🛠️ 其他解法补充

除了归并排序分治统计的方式外，本题也可使用以下数据结构实现：

✅ 树状数组（Binary Indexed Tree）

  • 对每一位二进制位从低到高遍历；
  • 维护两个树状数组，分别统计当前位为 0 和 1 的个数；
  • 当遍历到 a[i] 时，查询已有比它小的元素中某位为 0/1 的数量，并计算异或贡献；
  • 时间复杂度约为 O(31 × n log n)。

✅ 线段树（Segment Tree）

  • 类似树状数组思路，但可以扩展到更多复杂操作，比如：
    • 区间和；
    • 区间位统计；
  • 空间比树状数组更大，但功能更灵活，适合处理变种题目。