题解#

1. $256 * 8 / 32 * 1024 * 1024 = 67108864$

2. 暴力枚举

3. 枚举 + 去重

   1
   for (int i = 0; i < 20; i++)
   2
   {
   3
       for (int j = 0; j < 21; j++)
   4
       {
   5
           vec.push_back({i, j});
   6
       }
   7
   }
   8
   for (int i = 0; i < vec.size(); i++)
   9
   {
   10
       for (int j = i + 1; j < vec.size(); j++)
   11
       {
   12
           int x1 = vec[i].first, y1 = vec[i].second;
   13
           int x2 = vec[j].first, y2 = vec[j].second;
   14
           int A = x2 - x1, B = y1 - y2, C = x1 * y2 - x2 * y1;
   15
           int gcdd = gcd(gcd(A, B), C);
   16
           s.insert({{B / gcdd, A / gcdd}, C / gcdd});
   17
       }
   18
   }
   19
   cout << s.size() << endl;
   

4. 找出 $n$ 的所有因子，枚举合法对

   1
   ll n = 2021041820210418;
   2
   vector<ll> a;
   3
   for (ll i = 1; i * i <= n; i++) {
   4
       if (n % i == 0) {
   5
           a.push_back(i);
   6
           if (i * i != n)
   7
               a.push_back(n / i);
   8
       }
   9
   }
   10
   int ans = 0;
   11
   for (auto x: a) {
   12
       for (auto y: a) {
   13
           if (n % (x * y) == 0) {
   14
               ans++;
   15
           }
   16
       }
   17
   }
   18
   cout << ans << endl;
   

5. 最短路模板题

   1
   #include <bits/stdc++.h>
   2
   using namespace std;
   3
   
   4
   // 计算最大公约数 (GCD)
   5
   int gcd(int a, int b) {
   6
       return b == 0 ? a : gcd(b, a % b);
   7
   }
   8
   
   9
   // 计算最小公倍数 (LCM)
   10
   int lcm(int a, int b) {
   11
       return (a / gcd(a, b)) * b;
   12
   }
   13
   
   14
   // Dijkstra 算法求最短路径
   15
   long long dijkstra(int n) {
   16
       // 定义优先队列 (最小堆)，存储 (距离, 结点)
   17
       priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
   18
   
   19
       // 定义距离数组，初始化为无穷大
   20
       vector<long long> dist(n + 1, LLONG_MAX);
   21
   
   22
       // 起点为结点 1，距离为 0
   23
       dist[1] = 0;
   24
       pq.push({0, 1});
   25
   
   26
       while (!pq.empty()) {
   27
           auto [current_dist, u] = pq.top();
   28
           pq.pop();
   29
   
   30
           // 如果当前距离大于记录的距离，跳过
   31
           if (current_dist > dist[u]) continue;
   32
   
   33
           // 更新邻居的距离
   34
           for (int v = max(1, u - 21); v <= min(n, u + 21); ++v) {
   35
               if (v == u) continue; // 不考虑自己
   36
   
   37
               // 计算边的权重 (LCM)
   38
               int weight = lcm(u, v);
   39
   
   40
               // 更新最短距离
   41
               if (dist[v] > dist[u] + weight) {
   42
                   dist[v] = dist[u] + weight;
   43
                   pq.push({dist[v], v});
   44
               }
   45
           }
   46
       }
   47
   
   48
       // 返回从结点 1 到结点 n 的最短距离
   49
       return dist[n];
   50
   }
   51
   
   52
   int main() {
   53
       ios::sync_with_stdio(false);
   54
       cin.tie(nullptr);
   55
   
   56
       int n = 2021; // 图的结点数
   57
       cout << dijkstra(n) << "\n";
   58
   
   59
       return 0;
   60
   }
   

题解#

将毫秒转化成时分秒并补全前导 $0$

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7

8
    long long timestamp;
9
    cin >> timestamp;
10

11
    // 转换为秒，并取一天内的秒数
12
    long long seconds = timestamp / 1000; // 舍去毫秒
13
    long long seconds_in_day = seconds % (24 * 60 * 60);
14

15
    // 提取小时、分钟和秒
16
    int hours = seconds_in_day / 3600;
17
    int remaining_seconds = seconds_in_day % 3600;
18
    int minutes = remaining_seconds / 60;
19
    int secs = remaining_seconds % 60;
20

21
    // 格式化输出 HH:MM:SS
22
    printf("%02d:%02d:%02d\n", hours, minutes, secs);
23

24
    return 0;
25
}

题意#

将 $n$ 个砝码凑成尽可能多的重量

题解#

1. 状态表示：
   • 使用一个布尔数组 dp 表示当前可以称出的重量集合。
   • dp[w] = true 表示重量 $w$ 可以被称出。
2. 动态规划更新：
   • 对于每个砝码 $W_i$，我们有两种选择：
     • 将砝码放在天平的一侧（增加重量）。
     • 将砝码放在天平的另一侧（减少重量）。
   • 更新规则为：如果当前可以称出重量 $w$，则可以扩展到 $w + W_i$ 和 $|w - W_i|$。
3. 优化空间复杂度：
   • 因为砝码总重不超过 $10^5$，我们可以使用一个布尔数组 dp，大小为 $10^5+1$，表示所有可能的重量。
4. 最终结果：
   • 统计 dp 数组中值为 true 的元素个数，即为可以称出的不同重量的种类数。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    int N;
6
    cin >> N;
7
    vector<int> weights(N);
8
    for (auto &w : weights) cin >> w;
9
    // 计算砝码总重的最大值
10
    int max_weight = 0;
11
    for (int w : weights) max_weight += w;
12
    // 初始化 dp 数组
13
    vector<bool> dp(max_weight + 1, false);
14
    dp[0] = true; // 初始时可以称出重量 0
15
    // 动态规划更新
16
    for (int i = 0; i < N; ++i) {
17
        int W = weights[i];
18
        // 创建临时数组，避免覆盖当前状态
19
        vector<bool> temp(dp);
20
        for (int w = 0; w <= max_weight; ++w) {
21
            if (dp[w]) {
22
                // 增加重量
23
                if (w + W <= max_weight) temp[w + W] = true;
24
                // 减少重量
25
                if (w >= W) temp[w - W] = true;
26
                else temp[W - w] = true;
27
            }
28
        }
29
        // 更新 dp 数组
30
        dp = move(temp);
31
    }
32
    // 统计可以称出的不同重量的种类数
33
    int count = 0;
34
    for (int w = 1; w <= max_weight; ++w) {
35
        if (dp[w]) ++count;
36
    }
37
    cout << count << "\n";
38
    return 0;
39
}

题意#

计算形如 $1, 1, 2, 1, 2, 3,...1,2...k$ 无限长数列的区间和

题解#

关键点

1. 数列分组：

   • 第 $k$ 组包含 $k$ 个数字，分别是 $1, 2, \dots, k$。
   • 数列中第 $n$ 个数字所属的组可以通过数学公式快速确定。

2. 前缀和优化：

   • 由于 $l_i$ 和 $r_i$ 的范围可能非常大（高达 $10^{12}$），直接模拟数列不可行。
   • 我们需要通过数学公式计算任意位置的前缀和，从而高效地求解区间和。

3. 公式推导：

   • 第 $k$ 组的总和为 $\text{sum}_k = \frac{k(k+1)}{2}$。
   • 前 $m$ 组的总和为 $\text{prefix\_sum}_m = \sum_{k=1}^m \frac{k(k+1)}{2}=\frac{m(m+1)(m+2)}{6}$。
   • 通过二分查找，可以快速定位某个位置属于哪一组。

解题思路

1. 定位组号：

   • 使用二分查找确定某个位置 $n$ 所属的组号 $k$。
   • 每组的起始位置为 $\text{start}_k = \frac{k(k-1)}{2} + 1$。

2. 计算前缀和：

   • 前 $m$ 组的总和为： $$\text{prefix\_sum}_m = \frac{m(m+1)(m+2)}{6}$$
   • 对于任意位置 $n$，先找到其所属的组 $k$，然后计算其在组内的偏移量，得到其值。

3. 区间和计算：

   • 区间和可以通过前缀和公式快速计算： $$\text{range\_sum}(l, r) = \text{prefix\_sum}_r - \text{prefix\_sum}_{l-1}$$

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
// 计算前 m 组的总和
4
long long prefix_sum_group(long long m) {
5
    return m * (m + 1) * (m + 2) / 6;
6
}
7
// 找到位置 n 所属的组号 k
8
long long find_group(long long n) {
9
    long long left = 1, right = 2e6; // k 的最大值约为 sqrt(2e12)
10
    while (left < right) {
11
        long long mid = (left + right) / 2;
12
        if (mid * (mid + 1) / 2 < n) {
13
            left = mid + 1;
14
        } else {
15
            right = mid;
16
        }
17
    }
18
    return left;
19
}
20
// 计算位置 n 的前缀和
21
long long prefix_sum_position(long long n) {
22
    if (n == 0) return 0;
23
    long long k = find_group(n); // 找到 n 所属的组号
24
    long long start_k = k * (k - 1) / 2 + 1; // 第 k 组的起始位置
25
    long long offset = n - start_k; // 在第 k 组中的偏移量
26
    long long sum_prev_groups = prefix_sum_group(k - 1); // 前 k-1 组的总和
27
    long long sum_current_group = (offset + 1) * (offset + 2) / 2; // 当前组的部分和
28
    return sum_prev_groups + sum_current_group;
29
}
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    int T;
34
    cin >> T;
35
    while (T--) {
36
        long long l, r;
37
        cin >> l >> r;
38
        // 计算区间和
39
        long long result = prefix_sum_position(r) - prefix_sum_position(l - 1);
40
        cout << result << "\n";
41
    }
42
    return 0;
43
}

题解#

1. 模拟任务调度：
   • 使用一个数组 remaining 记录每台计算机的当前剩余运算能力。
   • 使用一个优先队列（最小堆）为每台计算机维护正在运行的任务，按照任务的结束时间排序。
2. 任务分配逻辑：
   • 对于每个任务：
     1. 检查当前计算机是否有已经结束的任务，并释放它们占用的算力。
     2. 判断当前计算机的剩余运算能力是否足够支持新任务。
     3. 如果足够，将任务加入优先队列，并更新剩余运算能力；否则输出 $-1$。
3. 优化点：
   • 使用优先队列（最小堆）确保每次可以快速找到最早结束的任务。
   • 时间复杂度主要由优先队列的操作决定，单次操作的时间复杂度为 $O(\log m)$。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
    int n, m;
8
    cin >> n >> m;
9
    // 每台计算机的初始运算能力
10
    vector<long long> remaining(n + 1);
11
    for (int i = 1; i <= n; ++i) cin >> remaining[i];
12
    // 每台计算机的任务队列 (优先队列，存储 {结束时间, 算力消耗})
13
    vector<priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<>>> tasks(n + 1);
14
    // 处理每个任务
15
    for (int i = 0; i < m; ++i) {
16
        int a, b, c, d;
17
        cin >> a >> b >> c >> d;
18
        // 当前计算机编号为 b
19
        auto &pq = tasks[b];
20
        // 释放已经结束的任务
21
        while (!pq.empty() && pq.top().first <= a) {
22
            remaining[b] += pq.top().second; // 恢复算力
23
            pq.pop();
24
        }
25
        // 判断是否可以接受新任务
26
        if (remaining[b] >= d) {
27
            // 接受任务，更新剩余算力
28
            remaining[b] -= d;
29
            pq.push({a + c, d}); // 加入任务队列 (结束时间为 a + c)
30
            cout << remaining[b] << "\n";
31
        } else {
32
            // 无法接受任务
33
            cout << "-1\n";
34
        }
35
    }
36
    return 0;
37
}

题意#

给定长度为 $n$ 的数列，双方每回合各取一个值异或，求谁最后的值最大

题解#

1. 数列的所有元素 $X_1, X_2, \dots, X_n$ 的异或和为 $S = X_1 \oplus X_2 \oplus \cdots \oplus X_n$
2. 如果 $S = 0$，则无论 Alice 和 Bob 如何分配，最终两人的数值必然相等，结果为平局
3. 否则，由于高位 $1$ 的价值显然大于低位 $1$ 的价值，故从高位向低位枚举：
   1. 假设当前位是 $1$ 的数量是 $1$，则 $Alice$ 先手选择该数字后，由于低位不可能超过高位，因此 $Alice$ 必胜
   2. 假设当前位为 $1$ 的数量是偶数，一个偶数只能拆分成两个奇偶性相同的非负整数，所以 $Alice$ 和 $Bob$ 在该位的值一定相同，故不影响胜负
   3. 假设当前位为 $1$ 的数量是奇数，一个奇数只能拆分成两个奇偶性不同的非负整数，那么当前这一位一定能分出胜负，因此谁拿到奇数个谁就获胜。如果所有数这一位都是 $1$ ，那么先手获胜，否则后手可以选择这一位为 $0$ 的数改变先后手顺序，因此当 $n - x$ 为偶数时，$Alice$ 获胜，否则 $Bob$ 获胜。

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<int> a(32);
6
    int sum = 0;
7
    for (int i = 0; i < n; i++) {
8
        int x;
9
        cin >> x;
10
        sum ^= x;
11
        for (int j = 0; j < 32; j++) {
12
            if (x & (1 << j))
13
                a[j]++;
14
        }
15
    }
16
    if (!sum) {
17
        cout << "0\n";
18
        return;
19
    }
20
    for (int i = 31; i >= 0; i--) {
21
        if (a[i] % 2 == 0) {
22
            continue;
23
        }
24
        if (a[i] == 1) {
25
            cout << "1\n";
26
            return;
27
        }
28
        if((n - a[i]) % 2 == 0){
29
            cout << "1\n";
30
        }
31
        else{
32
            cout << "-1\n";
33
        }
34
        return;
35
    }
36
}

题意#

我们需要帮助小蓝购买巧克力，使得他能够吃 $x$ 天，并且总花费最小。每种巧克力有以下属性：

1. 单价：每块巧克力的价格为 $a_i$。
2. 保质期：巧克力只能在接下来的 $b_i$ 天内食用。
3. 数量：每种巧克力最多可以购买 $c_i$ 块。

题解#

为了尽可能地减小吃巧克力的花费，用一个堆来维护当前没有过期的巧克力中的最小值，从最后一天开始向前枚举，并将当天没有过期的巧克力加入堆中，每天取堆的最小值，并判断数量是否耗尽即可。

如果从第一天枚举，堆中的合法巧克力种类是不断减少的，那么会出现因为优先选择保质期长的最小值而无法选择保质期短的次小值，而从后往前枚举堆中的合法巧克力种类是增多而非减少的，故不会出现这种问题

代码#

1
struct node {
2
    int a, b;
3
    mutable int c;
4

5
    bool operator<(const node &rhs) const {
6
        return a > rhs.a;
7
    }
8
};
9

10
void idol_produce(int testCase) {
11
    /*Code Here*/
12
    int x, n;
13
    cin >> x >> n;
14
    priority_queue<node> q;
15
    vector<node> a(n + 1);
16
    for (int i = 1; i <= n; i++) {
17
        cin >> a[i].a >> a[i].b >> a[i].c;
18
    }
19
    sort(a.begin() + 1, a.end(), [](node &lhs, node &rhs) {
20
        return lhs.b < rhs.b;
21
    });
22
    ll ans = 0;
23
    for (int i = x; i >= 1; i--) {
24
        while (!a.empty() && a.back().b >= i) {
25
            q.push(a.back());
26
            a.pop_back();
27
        }
28
        while (q.top().c == 0) {
29
            q.pop();
30
        }
31
        if (q.empty()) {
32
            cout << -1 << '\n';
33
            return;
34
        }
35
        ans += q.top().a;
36
        q.top().c--;
37
    }
38
    cout << ans << '\n';
39
}