第十六屆藍橋杯大賽軟件賽C/C++大學B組題解
試題A: 移動距離
問題描述
小明初始在二維平面的原點，他想前往坐標(233,666)。在移動過程中，他只能采用以下兩種移動方式，并且這兩種移動方式可以交替、不限次數地使用：
- 水平向右移動，即沿著x軸正方向移動一定的距離。
- 沿著一個圓心在原點(0,0)、以他當前位置到原點的距離為半徑的圓的圓周移動，移動方向不限（即順時針或逆時針移動不限）。
在這種條件下，他到達目的地最少移動多少單位距離？你只需要輸出答案四舍五入到整數的結果。
解題思路
這個問題可以轉化為：如何從原點到達目標點，使得路徑長度最小。
首先，我們可以觀察到，如果目標點在x軸上，那么直接水平向右移動是最優的。
對于一般情況，我們可以分兩步走：
- 先沿著x軸正方向移動到點(r,0)，其中r是目標點到原點的距離
- 然后沿著半徑為r的圓弧移動到目標點
目標點(233,666)到原點的距離為：
r = √(2332 + 6662) = √(54289 + 443556) = √497845 ≈ 705.58
第一步移動距離為r = 705.58
第二步需要計算圓弧長度。目標點與x軸正方向的夾角為：
θ = arctan(666/233) ≈ 1.2323弧度
圓弧長度 = r·θ = 705.58 × 1.2323 ≈ 869.49
總移動距離 = 705.58 + 869.49 = 1575.07
四舍五入到整數為1575。
答案
1575
試題B: 客流量上限
問題描述
一家連鎖旅館在全國擁有2025個分店，分別編號為1至2025。隨著節日臨近，總部決定為每家分店設定每日客流量的上限，分別記作A?,A?,…,A????。這些上限并非隨意分配，而是需要滿足以下約束條件：
- A?,A?,…,A????必須是1至2025的一個排列，即每個A_i均是1至2025之間的整數，且所有A_i互不相同。
- 對于任意分店i和j（1≤i,j≤2025，i可等于j），它們的客流量上限A_i和A_j的乘積不得超過i×j+2025。
現在，請你計算這樣的分配方案究竟有多少種。由于答案可能很大，你只需輸出其對10^9+7取余后的結果即可。
解題思路
這個問題要求我們計算滿足特定約束條件的排列數量。讓我們逐步分析這個問題：
約束條件分析
- A?, A?, …, A???? 必須是 1 到 2025 的一個排列
- 對于任意 i 和 j (1 ≤ i,j ≤ 2025)，必須滿足 A? × A? ≤ i × j + 2025
關鍵觀察
首先，我們考慮當 i = j 時的特殊情況：
- 此時約束條件變為：A? × A? ≤ i × i + 2025
- 即：A?2 ≤ i2 + 2025
- 因此：A? ≤ √(i2 + 2025)
通過計算和分析，我們可以得出以下結論：
-
對于 1014 ≤ i ≤ 2025 的情況：
- 約束條件要求 A? ≤ i
- 由于 A? 必須是 1 到 2025 之間的整數，且所有 A? 互不相同
- 最優解是 A? = i（這樣可以最大化其他位置的選擇空間）
-
對于 1 ≤ i ≤ 1012 的情況：
- 約束條件允許 A? ≤ i + 1
- 對于這些位置，我們有兩種選擇：A? = i 或 A? = i + 1
-
對于 1013 ≤ i ≤ 1013 的情況：
- 這個位置的值已經被前面的分析確定
組合計算
根據上述分析：
- 對于位置 1014 到 2025（共 1012 個位置），每個位置的值唯一確定為 A? = i
- 對于位置 1 到 1012（共 1012 個位置），每個位置有兩種可能的選擇
- 因此，總的方案數為 21?12
由于答案可能很大，我們需要對 10? + 7 取模。最終答案為：
21?12 mod (10? + 7) = 781448427
代碼實現
#include <bits/stdc++.h>
using namespace std;const int MOD = 1e9 + 7;
const int N = 2025;// 計算2的冪次取模
long long pow_mod(long long base, long long exp, long long mod) {long long result = 1;base %= mod;while (exp > 0) {if (exp & 1) {result = (result * base) % mod;}base = (base * base) % mod;exp >>= 1;}return result;
}int main() {// 根據分析，答案為2^1012 mod (10^9 + 7)long long ans = pow_mod(2, 1012, MOD);cout << ans << endl;return 0;
}
答案：
781448427
試題C: 可分解的正整數
問題描述
定義一種特殊的整數序列，這種序列由連續遞增的整數組成，并滿足以下條件：
- 序列長度至少為3。
- 序列中的數字是連續遞增的整數（即相鄰元素之差為1），可以包括正整數、負整數或0。
例如，[1,2,3]、[4,5,6,7]和[-1,0,1]是符合條件的序列，而[1,2]（長度不足）和[1,2,4]（不連續）不符合要求。
現給定一組包含N個正整數的數據A?,A?,…,A_N。如果某個A_i能夠表示為符合上述條件的連續整數序列中所有元素的和，則稱A_i是可分解的。請你統計這組數據中可分解的正整數的數量。
解題思路
代碼實現
#include<bits/stdc++.h>
using namespace std;int main(){int n;int t;int ans = 0;cin>>n;for(int i = 0;i < n;i++){cin>>t;if(t != 1){ans++;}}cout<<ans<<endl;return 0;
}
試題D: 產值調整
問題描述
偏遠的小鎮上，三兄弟共同經營著一家小型礦業公司"兄弟礦業"。公司旗下有三座礦山：金礦、銀礦和銅礦，它們的初始產值分別用非負整數A、B和C表示。
為了穩定經營，三兄弟設計了一個產值調整策略，每年執行一次，每次調整時，將根據當前的產值A、B、C，計算新產值：
- 金礦新產值A′=?(B+C)/2?；
- 銀礦新產值B′=?(A+C)/2?；
- 銅礦新產值C′=?(A+B)/2?。
其中，??表示向下取整。計算出A′、B′、C′后，同時更新：A變為A′，B變為B′，C變為C′，作為下一年調整的基礎。
三兄弟計劃連續執行K次調整。現在，請你幫他們計算，經過K次調整后，金礦、銀礦和銅礦的產值分別是多少。
解題思路
我們可以直接模擬這個過程，但由于K可能很大（最大10^9），直接模擬會超時。
觀察調整規則，我們可以發現：
- 如果A=B=C，那么調整后仍然是A=B=C
- 如果不相等，每次調整后的值會趨向于平均值
實際上，經過足夠多次調整后，三個值會變得相等或者在一個很小的范圍內循環。
通過數學分析和實驗，我們可以發現：
- 如果初始值全部相等，那么調整后仍然相等
- 如果不全相等，經過最多6次調整，三個值要么全部相等，要么會進入一個長度不超過3的循環
因此，我們可以先模擬前幾次調整，然后根據情況決定最終結果。
代碼實現
#include <bits/stdc++.h>
using namespace std;void adjust(long long& a, long long& b, long long& c) {long long new_a = (b + c) / 2;long long new_b = (a + c) / 2;long long new_c = (a + b) / 2;a = new_a;b = new_b;c = new_c;
}int main() {int T;cin >> T;while (T--) {long long A, B, C, K;cin >> A >> B >> C >> K;// 如果已經相等，不需要調整if (A == B && B == C) {cout << A << " " << B << " " << C << endl;continue;}while(K--){adjust(A,B,C);// 如果已經相等，不需要調整if (A == B && B == C) {break;}}cout << A << " " << B << " " << C << endl;}return 0;
}
答案
對于樣例輸入：
-
A=10, B=20, C=30, K=1
-
一次調整后：A′=25, B′=20, C′=15
-
A=5, B=5, C=5, K=3
-
初始值已經相等，調整后仍然是A=5, B=5, C=5
試題E: 畫展布置
問題描述
畫展策展人小藍和助理小橋為即將舉辦的畫展準備了N幅畫作，其藝術價值分別為A?,A?,…,A_N。他們需要從這N幅畫中挑選M幅，并按照一定順序布置在展廳的M個位置上。
為了優化布置，他們希望使藝術價值的變化程度通過一個數值L來衡量，且該值越小越好。數值L的定義為：
L = Σ(i=1 to M-1) |B2??? - B2?|
其中B_i表示展廳第i個位置上畫作的藝術價值。
現在，他們希望通過精心挑選和排列這M幅畫作，使L達到最小值。請你幫他們計算出這個最小值是多少。
解題思路
這個問題要求我們從N幅畫中選擇M幅，并排列它們，使得相鄰畫作藝術價值平方的差的絕對值之和最小。
首先，我們可以觀察到，對于任意兩幅畫的藝術價值a和b，|a2 - b2| = |a-b|·|a+b|。這意味著，如果我們想要最小化|a2 - b2|，我們應該選擇藝術價值接近的畫作放在相鄰位置。
一個直觀的策略是：
- 對所有畫作的藝術價值進行排序
- 選擇M幅連續的畫作（因為連續的畫作藝術價值差異最小）
- 按照特定順序排列這M幅畫作，使得L最小
對于排列順序，我們可以證明，最優的排列方式是按照藝術價值從小到大或從大到小排列。
代碼實現
#include <bits/stdc++.h>
using namespace std;int main() {int N, M;cin >> N >> M;vector<int> values(N);for (int i = 0; i < N; i++) {cin >> values[i];}// 排序sort(values.begin(), values.end());// 計算所有可能的連續M幅畫作的L值long long min_L = LLONG_MAX;for (int i = 0; i <= N - M; i++) {vector<int> selected(values.begin() + i, values.begin() + i + M);// 計算按照從小到大排列的L值long long L1 = 0;for (int j = 0; j < M - 1; j++) {long long diff = (long long)selected[j+1] * selected[j+1] - (long long)selected[j] * selected[j];L1 += abs(diff);}// 計算按照從大到小排列的L值long long L2 = 0;for (int j = 0; j < M - 1; j++) {long long diff = (long long)selected[M-j-2] * selected[M-j-2] - (long long)selected[M-j-1] * selected[M-j-1];L2 += abs(diff);}min_L = min(min_L, min(L1, L2));}cout << min_L << endl;return 0;
}
答案
對于樣例輸入：
N=4, M=2, 藝術價值為[1, 5, 2, 4]
排序后為[1, 2, 4, 5]
可能的連續2幅畫作為：[1,2], [2,4], [4,5]
計算L值：
- [1,2]: |22 - 12| = |4 - 1| = 3
- [2,4]: |42 - 22| = |16 - 4| = 12
- [4,5]: |52 - 42| = |25 - 16| = 9
最小的L值為3。
試題F: 水質檢測
問題描述
小明需要在一條2×n的河床上鋪設水質檢測器。在他鋪設之前，河床上已經存在一些檢測器。如果兩個檢測器上下或者左右相鄰，那么這兩個檢測器就是互相連通的。連通具有傳遞性，即如果A和B連通，B和C連通，那么A和C也連通。現在他需要在河床上增加鋪設一些檢測器使得所有的檢測器都互相連通。他想知道最少需要增加鋪設多少個檢測器？
解題思路
這是一個連通性問題，可以使用并查集或深度優先搜索來解決。
首先，我們需要找出已有檢測器形成的所有連通分量。然后，我們需要添加最少的檢測器來連接這些分量。
對于每兩個相鄰的連通分量，我們只需要添加一個檢測器就可以連接它們。因此，如果有k個連通分量，我們至少需要添加k-1個檢測器。
但是，我們還需要考慮如何放置這些檢測器，使得添加的數量最少。一種策略是：
- 對于每個連通分量，找出其邊界點
- 對于相鄰的兩個連通分量，找出它們之間的最短路徑
- 在這條路徑上添加檢測器
代碼實現
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};int main() {string row1, row2;cin >> row1 >> row2;int n = row1.length();vector<vector<char>> grid(2, vector<char>(n));for (int j = 0; j < n; j++) {grid[0][j] = row1[j];grid[1][j] = row2[j];}// 標記連通分量vector<vector<int>> component(2, vector<int>(n, -1));int comp_id = 0;for (int i = 0; i < 2; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '#' && component[i][j] == -1) {// BFS標記連通分量queue<pair<int, int>> q;q.push({i, j});component[i][j] = comp_id;while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int d = 0; d < 4; d++) {int nx = x + dx[d];int ny = y + dy[d];if (nx >= 0 && nx < 2 && ny >= 0 && ny < n && grid[nx][ny] == '#' && component[nx][ny] == -1) {component[nx][ny] = comp_id;q.push({nx, ny});}}}comp_id++;}}}// 如果沒有檢測器或只有一個連通分量，特殊處理if (comp_id == 0) {cout << 0 << endl;return 0;}if (comp_id == 1) {cout << 0 << endl;return 0;}// 計算連通分量之間的最短距離vector<vector<int>> dist(comp_id, vector<int>(comp_id, INT_MAX));for (int c1 = 0; c1 < comp_id; c1++) {// BFS計算從c1到其他連通分量的最短距離vector<vector<int>> distance(2, vector<int>(n, -1));queue<pair<int, int>> q;for (int i = 0; i < 2; i++) {for (int j = 0; j < n; j++) {if (component[i][j] == c1) {q.push({i, j});distance[i][j] = 0;}}}while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int d = 0; d < 4; d++) {int nx = x + dx[d];int ny = y + dy[d];if (nx >= 0 && nx < 2 && ny >= 0 && ny < n && distance[nx][ny] == -1) {distance[nx][ny] = distance[x][y] + 1;q.push({nx, ny});if (grid[nx][ny] == '#') {int c2 = component[nx][ny];if (c2 != c1) {dist[c1][c2] = min(dist[c1][c2], distance[nx][ny] - 1);}}}}}}// 使用最小生成樹算法連接所有連通分量vector<bool> visited(comp_id, false);visited[0] = true;int total_dist = 0;for (int i = 1; i < comp_id; i++) {int min_dist = INT_MAX;int next_comp = -1;for (int j = 0; j < comp_id; j++) {if (visited[j]) {for (int k = 0; k < comp_id; k++) {if (!visited[k] && dist[j][k] < min_dist) {min_dist = dist[j][k];next_comp = k;}}}}visited[next_comp] = true;total_dist += min_dist;}cout << total_dist << endl;return 0;
}
答案
對于樣例輸入：
.##.....#
.#.#.#...
已有的檢測器形成了4個連通分量。要使它們全部連通，需要添加5個檢測器。
試題G: 生產車間
問題描述
小明正在改造一個生產車間的生產流水線。這個車間共有n臺設備，構成以1為根結點的一棵樹，結點i有權值w_i。其中葉節點的權值w_i表示每單位時間將產出w_i單位的材料并送往父結點，根結點的權值w_i表示每單位時間內能打包多少單位成品，其他結點的權值w_i表示每單位時間最多能加工w_i單位的材料并送往父結點。
由于當前生產線中某些結點存在產能不夠的問題導致生產線無法正常運行，即存在某些結點每單位時間收到的材料超過了當前結點的加工能力上限。小明計劃刪除一些結點使得所有結點都能正常運行。他想知道刪除一些結點后根結點每單位時間內最多能打包多少單位的成品？
解題思路
這個問題描述了一個生產流水線優化場景：
- 有n臺設備構成一棵以1為根的樹
- 每個節點有權值w_i，表示其加工能力
- 葉節點產生材料，非葉節點加工材料，根節點打包成品
- 如果節點接收的材料超過其加工能力，生產線無法正常運行
- 可以刪除一些節點（及其子樹）使所有節點正常運行
- 目標是最大化根節點的產出
關鍵洞察：這是一個樹形結構上的優化問題，我們需要決定保留或刪除每個節點，以使根節點的產出最大化。要注意并不是每個節點的最大值組合起來并就一定是所求的最優解，比如樣例數據，樣例解釋見代碼后
我們采用自底向上的方法，從葉子節點開始，計算每個節點在不同情況下可能的產出值：
-
對于每個節點，我們有兩個基本選擇：
- 保留節點：節點產生其權值的產出（對于葉子節點）或處理子節點的材料（對于非葉子節點）
- 刪除節點：節點產出為0
-
對于非葉子節點，我們需要：
- 收集所有子節點的可能產出值
- 組合這些產出值，確保總和不超過當前節點的加工能力
- 計算當前節點所有可能的產出值
-
最終，根節點的最大可能產出值就是答案
代碼實現
#include <bits/stdc++.h>
using namespace std;const int MAX_NODES = 1005;
vector<int> g[MAX_NODES]; // 樹結構的鄰接表
int n, capacity[MAX_NODES]; // 節點數和各節點容量/*** 計算以current_node為根的子樹能提供的合法材料數值集合* @param current_node 當前處理的節點* @param parent_node 父節點（防止回溯）* @return 包含所有可能值的有序集合*/
set<int> dfs(int current_node, int parent_node) {// g[current_node].size() == 1 表示無向圖的葉子節點//parent_node != 0 避免出現鏈狀if (g[current_node].size() == 1 && parent_node != 0) {return {capacity[current_node], 0}; // 保留或關閉該節點}set<int> valid_sums = {0}; // 初始化，包含0（全關閉情況）// 使用范圍for循環遍歷鄰接節點for (int child_node : g[current_node]) {if (child_node == parent_node) continue; // 跳過父節點auto child_outputs = dfs(child_node, current_node);//深入遍歷子節點set<int> current_sums = valid_sums; // 當前狀態的副本//依次將任意兩個子節點的所有取值進行組合for (int parent_sum : current_sums) {for (int child_contribution : child_outputs) {int total = parent_sum + child_contribution;if (total <= capacity[current_node]) {valid_sums.insert(total);}}}}return valid_sums;//返回該節點的所有取值情況
}int main() {// 輸入處理cin >> n;for (int i = 1; i <= n; ++i) {cin >> capacity[i];}// 構建樹結構for (int i = 1; i < n; ++i) {int node_a, node_b;cin >> node_a >> node_b;g[node_a].push_back(node_b);g[node_b].push_back(node_a);}// 計算并輸出最大打包量cout << *dfs(1, 0).rbegin() << endl;return 0;
}
注意：這份代碼在部分網站測試會有極少量測試集超時，對此可以使用使用位運算bitset代替集合：
#include <bits/stdc++.h>
using namespace std;const int MAXN = 1005;
const int MAXW = 1001; // 最大權值+1int n; // 節點數量
int w[MAXN]; // 每個節點的權值（容量）
vector<int> graph[MAXN]; // 無向圖鄰接表/*** 計算以u為根的子樹能提供的合法材料數值集合* 使用bitset優化狀態表示和組合操作* @param u 當前處理的節點* @param parent 父節點（防止回溯）* @return 包含所有可能值的位向量*/
bitset<MAXW> dfs(int u, int parent) {// 判斷是否為葉子節點if (graph[u].size() == 1 && parent != 0) {bitset<MAXW> result;result[0] = 1; // 可以產出0（刪除節點）result[w[u]] = 1; // 可以產出w[u]（保留節點）return result;}// 初始化結果位向量，只有0位為1（表示所有子節點都關閉的情況）bitset<MAXW> result;result[0] = 1;// 遍歷所有子節點for (int v : graph[u]) {if (v == parent) continue; // 跳過父節點// 遞歸計算子節點的所有可能產出bitset<MAXW> child_outputs = dfs(v, u);// 保存當前結果的副本bitset<MAXW> current = result;result.reset(); // 清空結果// 優化的組合操作for (int i = 0; i <= w[u]; i++) {if (current[i]) {// 對于當前值i，與子節點的每個可能產出組合for (int j = 0; j <= w[u] - i; j++) {if (child_outputs[j]) {result[i + j] = 1;}}}}}return result; // 返回所有可能的產出值
}int main() {ios_base::sync_with_stdio(false); // 優化輸入輸出cin.tie(nullptr);cin >> n;// 讀取每個節點的權值for (int i = 1; i <= n; i++) {cin >> w[i];}// 讀取樹的邊for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;graph[u].push_back(v);graph[v].push_back(u);}// 計算根節點的所有可能產出bitset<MAXW> root_outputs = dfs(1, 0);// 找出最大可能產出int ans = 0;for (int i = MAXW - 1; i >= 0; i--) {if (root_outputs[i]) {ans = i;break;}}cout << ans << endl;return 0;
}
樣例詳細闡述
讓我們以給定的樣例來詳細說明算法的執行過程：
9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9
樹的結構如下：
1/ \2 3/|\
4 5 6/|\7 8 9
節點權值：w = [9, 7, 3, 7, 1, 6, 2, 2, 7]（索引從1開始）
執行DFS過程：
-
葉子節點：
- 節點3：返回3, 0
- 節點4：返回7, 0
- 節點5：返回1, 0
- 節點7：返回2, 0
- 節點8：返回2, 0
- 節點9：返回7, 0
-
節點6（容量為6）：
-
初始結果集：0
-
處理子節點7（2, 0）：結果集變為0, 2
-
處理子節點8（2, 0）：結果集變為0, 2, 4
-
處理子節點9（7, 0）：
-
0 + 0 = 0，已在結果集中
-
0 + 7 = 7 > 6，超過容量，不添加
-
2 + 0 = 2，已在結果集中
-
2 + 7 = 9 > 6，超過容量，不添加
-
4 + 0 = 4，添加到結果集
-
4 + 7 = 11 > 6，超過容量，不添加
最終結果集：0, 2, 4
-
-
節點2（容量為7）：
-
初始結果集：0
-
處理子節點4（7, 0）：結果集變為0, 7
-
處理子節點5（1, 0）：結果集變為0, 1, 7, 8，但8 > 7，所以實際為0, 1, 7
-
處理子節點6（0, 2, 4）：
-
組合后得到0, 1, 2, 4, 7, 3 (2 + 1), 9 (2 + 7 應舍去), 5(4 + 1), 11(4 + 7 應舍去)
-
最終結果集：0, 1, 2, 3, 4, 5, 7
- 根節點1（容量為9）：
-
初始結果集：0
-
處理子節點2（0, 1, 2, 3, 4, 5, 7）：結果集變為0, 1, 2, 3, 4, 5, 7
-
處理子節點3（3, 0）：
-
組合后得到0, 1, 2, 3, 4, 5, 6 (3 + 3), 7 (4 + 3), 8 (5 + 3),10 (7 + 1)，但10 > 9，所以實際為0, 1, 2, 3, 4, 5, 6, 7, 8
-
最終結果集：0, 1, 2, 3, 4, 5, 6, 7, 8
- 最終答案：根節點1的結果集中的最大值為8
試題H: 裝修報價
問題描述
老王計劃裝修房子，聯系了一家裝修公司。該公司有一套自動報價系統，只需用戶提供N項裝修相關費用A?,A?,…,A_N，系統便會根據這些費用生成最終的報價。
系統會依據某種內部算法，在每對相鄰數字之間插入+（加法）、?（減法）或⊕（異或）運算符，并按照特定優先級規則計算結果：異或運算優先級最高，其次是加減。
老王決定模擬其運作方式，嘗試每種可能的運算符組合，計算出所有可能出現的結果的總和。請你幫老王算出所有可能的結果的總和。由于該總和可能很大，你只需提供其對10^9+7取余后的結果即可。
方法一：前綴異或枚舉法
解題思路
核心思想是枚舉前綴異或的長度，計算每個前綴異或在所有可能組合中的貢獻，然后求和。
關鍵洞察：
- 考慮給表達式的第一個值前面也補上+號，例如：2?3⊕4 實際上是 +2?3⊕4
- 由于異或運算的優先級高于加減法，連續的異或運算結果可以合并成一個數字，使表達式變成只包含+和-的形式
- 所有的"+XXX"和"-XXX"在不同的式子中會同時出現，它們的貢獻會相互抵消,也就是：對組合的式子分割為A+B，那么一定存在A-B的組合情況，這兩者相加就會使得B相互抵消了，僅有A有貢獻值
- 對最終結果有貢獻的只有前綴異或
對于長度為i的前綴異或S[i]（即A[1] ⊕ A[2] ⊕ … ⊕ A[i]），其貢獻計算方式為：
- 第i+1個位置的運算符必須是+或-（2種選擇，即把前面i個運算符的結果看作是一個數字A，后面的運算看作一個數字B），不能是異或（A + B / A - B）
- 其中，第i+2到第n個位置的運算符可以是任意三種（3^(n-i-1)種選擇，無論是哪一種都有對應的組合將其抵消掉）
- 因此，貢獻為：S[i] * 2 * 3^(n-i-1)
**特殊情況：**當i=n時（即所有數字都異或），貢獻為S[i]。
最后的總結果就是所有前綴異或的加權和：
結果 = S_1 * 2 * 3^(n-2) + S_2 * 2 * 3^(n-3) + ... + S_(n-1) * 2 * 3^0 + S_n * 1
代碼實現
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int MOD = 1e9 + 7;
vector<int> a;// 優化計算a^b % MOD
ll cal(ll a, ll b) {ll res = 1;while (b > 0) {//b是奇數，先乘掉一個aif (b % 2 == 1) res = (res * a) % MOD;//a^10 = (a ^ 2) ^ 5從而降低循環次數a = (a * a) % MOD;//指數b /= 2b /= 2;}return res;
}int main() {int n;cin >> n;// 只有一個數字if (n == 1) {int x;cin >> x;cout << x << endl;//直接輸出return 0;}a.resize(n + 1);//存儲n個數字for (int i = 1; i <= n; i++) {cin >> a[i];}ll ans = 0;ll s = 0;//存儲異或值（即a[1] ⊕ a[2] ⊕ ... ⊕ a[i]）for (int i = 1; i <= n; i++) {s ^= a[i];if (i < n) {// 不是最后一個數字：貢獻為 s * 2 * 3^(n-i-1)ll cnt = (s * 2) % MOD;cnt = (cnt * cal(3, n - i - 1)) % MOD;ans = (ans + cnt) % MOD;} else {// 是最后一個數字：貢獻為 sans = (ans + s) % MOD;}}cout << ans << endl;return 0;
}
樣例分析
以樣例 [0, 2, 5] 為例，詳細演示算法執行過程：
初始狀態：
- n = 3
- A = [0, 0, 2, 5]（代碼執行時索引從1開始）
- ans = 0
- s= 0
第1次迭代 (i=1, A[1]=0)：
- s= 0 ^ 0 = 0
- i < n，計算貢獻：
- cnt = 0 * 2 * 3^(3-1-1) = 0 * 2 * 3^1 = 0 * 2 * 3 = 0
- ans = 0 + 0 = 0
第2次迭代 (i=2, A[2]=2)：
-
s = 0 ^ 2 = 2
-
i < n，計算貢獻：
-
cnt = 2 * 2 * 3^(3-2-1) = 2 * 2 * 3^0 = 2 * 2 * 1 = 4
-
ans = 0 + 4 = 4
第3次迭代 (i=3, A[3]=5)：
-
s = 2 ^ 5 = 7
-
i = n，計算貢獻：
-
cnt = 7
-
ans = 4 + 7 = 11
最終答案為11，與樣例一致。
方法二：遞推關系法
解題思路
核心思想是根據方法一原理，利用遞推關系直接計算所有可能結果的總和，避免枚舉所有3^(N-1)種組合。
關鍵洞察：
-
對于除第一項外的每一項，其貢獻總和為0。這是因為對于任意非第一項的數字A[i]，如果我們將其前面的+改為-（或將-改為+），而保持其他運算符不變，這兩種情況的結果會互為相反數，在總和中相互抵消。
- 例如數據a,b,c : a + b + c; a + b - c; a + b ⊕ c 我們可以用a - b + c; a - b - c; a - b ⊕ c 完全消去b的貢獻
-
唯一有貢獻的是從第一項開始的連續異或序列（前綴異或）。
基于這一洞察，我們可以推導出遞推關系：
- 設S[k]表示前k個數的異或和：S[k] = A[1] ⊕ A[2] ⊕ … ⊕ A[k]
- 設Ans[k]表示考慮前k個數字時所有可能結果的總和
遞推關系為：
Ans[k] = 3 * Ans[k-1] - S[k-1] + S[k]
這個遞推關系可以這樣理解：
- 當考慮第k個數字時，該數字前的符號有3種可能（添加+、-或⊕），所以乘以3
- 需要減去前k-1個數字的異或和S[k-1]的貢獻，因為在計算3*Ans[k-1]時重復計算了
- 需要加上包含第k個數字的新異或和,S[k]的貢獻
代碼解釋
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int MOD = 1e9 + 7;int main() {int n;cin >> n;ll ans = 0; // 總答案ll s = 0; // 當前前綴異或和for (int i = 1; i <= n; i++) {int x;cin >> x;// 更新答案：ans = ans * 3 - s + (s ^ x)ans = (ans * 3 - s + (s ^ x) + MOD) % MOD;// 更新前綴異或和s ^= x;}cout << ans << endl;return 0;
}
)
