第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 H题_十四届蓝桥杯c++a组

问题描述

---

格式输入

输入的第一行包含一个整数 n 。
第二行包含 n 个整数 Ai ，相邻整数之间使用一个空格分隔。

---

格式输出

输出一行包含一个整数表示答案。

---

样例输入

5
1 2 3 4 5

---

样例输出

39

---

评测用例规模与约定

对于 30% 的评测用例，n ≤ 300 ；
对于 60% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 10^5，0 ≤ Ai ≤ 2
^20 。

---

解析

可以用前缀和的思想解决问题，先算出1~n的异或结果，然后再将各段的结果计算累加起来。过70%，大佬教教怎么过全部。

---

参考程序

70%

#include <iostream>
using namespace std;

const int N = 1e5 + 5;
int n, a[N], pre[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] ^ a[i];
    }
    long long ans = 0;
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            ans += pre[r] ^ pre[l - 1];
        }
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

100%

#include <stdio.h>

int n, a[100000];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    long long ans = 0;
    for (int k = 0; k <= 20; ++k) {
        int cnt[]{ 1, 0 }, j = 0;
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            j ^= (a[i] >> k) & 1;
            sum += cnt[j ^ 1];
            cnt[j]++;
        }
        ans += sum << k;
    }
    printf("%lld", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以个人刷题整理为目的，如若侵权，请联系删除~