編程題目現在在洛谷上都可以提交了。
未完待續，寫不動了。

C++11 編譯命令

g++ A.cpp -o A -Wall -lm -std=c++11

A. 移動距離

本題總分：5 分

問題描述

小明初始在二維平面的原點，他想前往坐標 $(233,666)$。在移動過程中，他只能采用以下兩種移動方式，并且這兩種移動方式可以交替、不限次數地使用：

1. 水平向右移動，即沿著 x 軸正方向移動一定的距離。
2. 沿著一個圓心在原點 $(0,0)$、以他當前位置到原點的距離為半徑的圓的圓周移動，移動方向不限（即順時針或逆時針移動不限）。在這種條件下，他到達目的地最少移動多少單位距離？你只需要輸出答案四舍五入到整數的結果。

思路

最短路徑應該是往右走圓的半徑長度 $r=\sqrt{233^2+666^2}$，然后再延著圓弧走到 $(233,666)$ 這個點。圓弧長度：$l=\alpha r=\arctan \frac{666}{233}r$ ($\alpha$ 是圓弧對應的圓心角，以弧度制表示)。答案是 $1576$

代碼

#include <bits/stdc++.h>
using namespace std;int main() {double r = sqrt(233 * 233 + 666 * 666);double ang = atan(1.0 * 666 / 233);cout << (int)round(ang * r + r) << endl;return 0;
}

B. 客流量上限

本題總分：5 分

問題描述

一家連鎖旅館在全國擁有 $2025$ 個分店，分別編號為 $1$ 至 $2025$。隨著節日臨近，總部決定為每家分店設定每日客流量的上限，分別記作 $A_1$, $A2$, $\dots$, $A_{2025}$。這些上限并非隨意分配，而是需要滿足以下約束條件：

1. $A_1$, $A2$, $\dots$, $A_{2025}$ 必須是 $1$ 至 $2025$ 的一個排列，即每個 $A_i$ 均是 $1$ 至 $2025$ 之間的整數，且所有 Ai 互不相同。
2. 對于任意分店 $i$ 和 $j$（$1\le i,j\le 2025$，$i$ 可等于 $j$），它們的客流量上限 $A_i$ 和 $A_j$ 的乘積不得超過 $i\times j+2025$。這些約束旨在平衡各分店客流壓力，確保服務質量和運營穩定性。現在，請你計算這樣的分配方案究竟有多少種。由于答案可能很大，你只\需輸出其對 $10^9+7$ 取余后的結果即可。

思路

暫無

C. 可分解的正整數

時間限制: 1.0s
內存限制: 256.0MB
本題總分：10 分

問題描述

定義一種特殊的整數序列，這種序列由 連續遞增的整數 組成，并滿足以下條件：

1. 序列長度至少為 $3$。
2. 序列中的數字是連續遞增的整數（即相鄰元素之差為 $1$），可以包括正整數、負整數或 $0$。

例如，$[1,2,3]$、$[4,5,6,7]$ 和 $[?1,0,1]$ 是符合條件的序列，而 $[1,2]$（長度不足）和 $[1,2,4]$（不連續）不符合要求。

現給定一組包含 $N$ 個正整數的數據 $A_1$, $A_2$, $\dots$, $A_N$。如果某個 $A_i$ 能夠表示為符合上述條件的連續整數序列中所有元素的和，則稱 $A_i$ 是可分解的。

請你統計這組數據中可分解的正整數的數量。

輸入格式

輸入的第一行包含一個正整數 $N$，表示數據的個數。

第二行包含 $N$ 個正整數 $A_1$, $A_2$, $\dots$, $A_N$，表示需要判斷是否可分解的正整數序列。

輸出格式

輸出一個整數，表示給定數據中可分解的正整數的數量。

樣例輸入

3
3 6 15

樣例輸出

3

樣例說明

$A_i=3$ 是可分解的，因為 $[0,1,2]$ 的和為 $0+1+2=3$。
$A_i=6$ 是可分解的，因為 $[1,2,3]$ 的和為 $1+2+3=6$。
$A_i=15$ 是可分解的，因為 $[4,5,6]$ 的和為 $4+5+6=15$。
所以可分解的正整數的數量為 $3$。

評測用例規模與約定

對于 $30\%$ 的評測用例，$1\le N\le 100$，$1\le A_i\le 100$。
對于 $100\%$ 的評測用例，$1\le N\le 10^5$，$1\le A_i\le 10^9$。

思路

$[1,10^9]$ 的正整數里面，$1$ 無法被連續整數序列表示，剩余所有的數都可以被以 $1$ 或 $0$ $1$ 為中心的連續整數序列表示。例如，

• $2$ 可以被表示為 $?1$, $0$, $1$, $2$。
• $3$ 可以被表示為 $0$, $1$, $2$。
• $4$ 可以被表示為 $?3$, $?2$, $?1$, $0$, $1$, $2$, $3$, $4$。

代碼

#include <bits/stdc++.h>
using namespace std;int n, a, ans = 0;int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++)cin >> a, ans += (a > 1);cout << ans << endl;return 0;
}

D. 產值調整

時間限制: 1.0s
內存限制: 256.0MB
本題總分：10 分

問題描述

偏遠的小鎮上，三兄弟共同經營著一家小型礦業公司 “兄弟礦業”。公司旗下有三座礦山：金礦、銀礦和銅礦，它們的初始產值分別用非負整數 $A$、$B$ 和 $C$ 表示。這些礦山的產出是小鎮經濟的核心，支撐著三兄弟和許多礦工家庭的生計。

然而，各礦山的產值波動劇烈，有時金礦收益高而銀礦、銅礦低迷，有時則相反。這種不穩定性讓公司收入難以預測，也常引發兄弟間的爭執。為了穩定經營，三兄弟設計了一個公平的產值調整策略，每年執行一次，每次調整時，將根據當前的產值 $A$、$B$、$C$，計算新產值：

1. 金礦新產值 $A$′ $=?\frac{B+C}{2}?$；
2. 銀礦新產值 $B$′ $=?\frac{A+C}{2}?$；
3. 銅礦新產值 $C$′ $=?\frac{A+B}{2}?$。

其中，$??$ 表示向下取整。例如，$?3.7?=3$，$?5.2?=5$。

計算出 $A$′、$B$′、$C$′ 后，同時更新：$A$ 變為 $A$′，$B$ 變為 $B$′，$C$ 變為 $C$′，作
為下一年調整的基礎。

三兄弟認為這個方法能平衡產值波動，于是計劃連續執行 $K$ 次調整。現在，請你幫他們計算，經過 $K$ 次調整后，金礦、銀礦和銅礦的產值分別是多少。

輸入格式

輸入的第一行包含一個整數 $T$ ，表示測試用例的數量。

接下來的 $T$ 行，每行包含四個整數 $A$，$B$，$C$，$K$，分別表示金礦、銀礦和銅礦的初始產值，以及需要執行的調整次數。

輸出格式

對于每個測試用例，輸出一行，包含三個整數，表示經過 $K$ 次調整后金礦、銀礦和銅礦的產值，用空格分隔。

樣例輸入

2
10 20 30 1
5 5 5 3

樣例輸出

25 20 15
5 5 5

評測用例規模與約定

對于 $30\%$ 的評測用例，$1\le T\le 100$，$1\le A,B,C,K\le 10^5$。
對于 $100\%$ 的評測用例，$1\le T\le 10^5$，$1\le A,B,C,K\le 10^9$。

思路

三個數會迅速向某個數收斂，當三個數都一樣時，無論進行多少次操作，結果都不會變了。在三個數都變成一樣之前暴力求解。

代碼

#include <bits/stdc++.h>
using namespace std;void solve() {int a, b, c, k;cin >> a >> b >> c >> k;while (k--) {int aa = (b + c) / 2, bb = (a + c) / 2, cc = (a + b) / 2;a = aa, b = bb, c = cc;if (a == b && b == c) break;}cout << a << " " << b << " " << c << "\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}

E. 畫展布置

時間限制: 1.0s
內存限制: 256.0MB
本題總分：15 分

問題描述

畫展策展人小藍和助理小橋為即將舉辦的畫展準備了 $N$ 幅畫作，其藝術價值分別為 $A_1$, $A_2$, $\dots$, $A_N$。他們需要從這 $N$ 幅畫中挑選 $M$ 幅，并按照一定順序布置在展廳的 $M$ 個位置上。如果隨意挑選和排列，藝術價值的變化可能會過于突兀，導致觀眾的觀展體驗不夠流暢。

為了優化布置，他們查閱了《畫展布置指南》。指南指出，理想的畫展應使觀眾在欣賞畫作時，藝術價值的過渡盡量平緩。指南建議，選擇并排列 $M$ 幅畫，應使藝術價值的變化程度通過一個數值 $L$ 來衡量，且該值越小越好。數值 $L$ 的定義為：

$L={\sum }_{i=1}^{M?1}|B_i^2?B_{i+1}^2|$

其中 $B_i$ 表示展廳第 $i$ 個位置上畫作的藝術價值。

現在，他們希望通過精心挑選和排列這 $M$ 幅畫作，使 $L$ 達到最小值，以提升畫展的整體協調性。請你幫他們計算出這個最小值是多少。

輸入格式

輸入共兩行。

第一行包含兩個正整數 $N$ 和 $M$，分別表示畫作的總數和需要挑選的畫作數量。

第二行包含 $N$ 個正整數 $A_1$, $A_2$, $\dots$, $A_N$，表示每幅畫作的藝術價值。

輸入樣例

4 2
1 5 2 4

輸出樣例

3

樣例用例規模與約定

對于 $40\%$ 的評測用例，$2\le M\le N\le 10^3$，$1\le A_i\le 10^3$。
對于 $100\%$ 的評測用例，$2\le M\le N\le 10^5$，$1\le A_i\le 10^5$。

輸出格式

輸出一個整數，表示 $L$ 的最小值。

思路

• 對于選定的若干個數，一定按照大小排序一定最優。
  • 對于 $i<j$，如果交換 $B_i$ 和 $B_j$，即 $B_i^{\prime }=B_j$，$B_j^{\prime }=B_i$，一定會有 $|B_i^2?B_{i?1}^2|+|B_i^2?B_{i+1}^2|+|B_j^2?B_{j?1}^2|+|B_j^2?B_{j+1}^2|<|B_i^{\prime 2}?B_{i?1}^{\prime 2}|+|B_i^{\prime 2}?B_{i+1}^{\prime 2}|+|B_j^{\prime 2}?B_{j?1}^{\prime 2}|+|B_j^{\prime 2}?B_{j+1}^{\prime 2}|$，即交換之后結果更劣。
• 不妨設選定數字從小到大排序，那么 $L={\sum }_{i=1}^{M?1}|B_i^2?B_{i+1}^2|={\sum }_{i=1}^{M?1}(B_{i+1}^2?B_i^2)=B_M^2?B_1^2$，所以我們要讓所選的數最大值與最小值的差盡可能地小。
• 只需要先將 $A$ 數組排序，然后依次選擇連續的 $M$ 個數，算出最小的 $L$ 即可。

代碼

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e5 + 10;
int n, m, a[N], sum[N], ans = LLONG_MAX;signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 2; i <= n; i++)sum[i] = sum[i - 1] + a[i] * a[i] - a[i - 1] * a[i - 1];for (int l = 1; l + m - 1 <= n; l++) {int r = l + m - 1;ans = min(ans, sum[r] - sum[l]);}cout << ans << endl;return 0;
}

F. 水質檢測

時間限制: 1.0s
內存限制: 256.0MB
本題總分：15 分

問題描述

小明需要在一條 $2\times n$ 的河床上鋪設水質檢測器。在他鋪設之前，河床上已經存在一些檢測器。如果兩個檢測器上下或者左右相鄰，那么這兩個檢測器就是互相連通的。連通具有傳遞性，即如果 $A$ 和 $B$ 連通，$B$ 和 $C$ 連通，那么 $A$ 和 $C$ 也連通。現在他需要在河床上增加鋪設一些檢測器使得所有的檢測器都互相連通。他想知道最少需要增加鋪設多少個檢測器？

輸入格式

輸入共兩行，表示一個 $2\times n$ 的河床。

每行一個長度為 $n$ 的字符串，僅包含 # 和 .，其中 # 表示已經存在的檢測器，. 表示空白。

輸出格式

輸出共 $1$ 行，一個整數表示答案。

樣例輸入

.##.....#
.#.#.#...

樣例輸出

5

說明/提示

樣例說明

其中一種方案：

.###....#
.#.######

增加了 5 個檢測器。

評測用例規模與約定

對于 $100\%$ 的評測用例，保證 $n\le 1000000$。

H. 裝修報價

題目描述

老王計劃裝修房子，于是聯系了一家裝修公司。該公司有一套自動報價系統，只需用戶提供 $N$ 項裝修相關費用 $A_1,A_2,\dots ,A_N$，系統便會根據這些費用生成最終的報價。

然而，當老王提交數據后，他發現這套系統的運作方式并不透明：系統只會給出一個最終報價，而不會公開任何運算過程或中間步驟。

公司對此解釋稱，這套系統會依據某種內部算法，在每對相鄰數字之間插入 $+$（加法）、$?$（減法）或 $\oplus$（異或）運算符，并按照特定優先級規則計算結果：異或運算優先級最高，其次是加減。但由于保密性，具體的運算符組合以及中間過程都不會對外公開。

為了驗證系統報價是否合理，老王決定模擬其運作方式，嘗試每種可能的運算符組合，計算出所有可能出現的結果的總和。如果最終報價明顯超出這個范圍，他就有理由懷疑系統存在異常或誤差。只是老王年事已高，手動計算頗為吃力，便向你求助。

現在，請你幫老王算出所有可能的結果的總和。由于該總和可能很大，你只需提供其對 $10^9+7$ 取余后的結果即可。

輸入格式

第一行輸入一個整數 $N$，表示裝修相關費用的項數。

第二行輸入 $N$ 個非負整數 $A_1,A_2,\dots ,A_N$，表示各項費用。

輸出格式

輸出一個整數，表示所有可能的總和對 $10^9+7$ 取余后的結果。

樣例輸入

3
0 2 5

樣例輸出

11

說明/提示

對于輸入樣例中的三個數 $A=[0,2,5]$，所有可能的運算符組合共有 $9$ 種。計算結果如下：

$0\oplus 2\oplus 5=7$
$0\oplus 2+5=7$
$0\oplus 2?5=?3$
$0+2\oplus 5=7$
$0+2+5=7$
$0+2?5=?3$
$0?2\oplus 5=?7$
$0?2+5=3$
$0?2?5=?7$

所有結果的總和為：

$$7+7+(?3)+7+7+(?3)+(?7)+3+(?7)=11$$

$11$ 對 $10^9+7$ 取余后的值依然為 $11$，因此，輸出結果為 $11$。

評測用例規模與約定

• 對于 $30\%$ 的評測用例，$1\le N\le 13$，$0\le A_i\le 10^3$。
• 對于 $60\%$ 的評測用例，$1\le N\le 10^3$，$0\le A_i\le 10^5$。
• 對于 $100\%$ 的評測用例，$1\le N\le 10^5$，$0\le A_i\le 10^9$。

思路

• 每一種組合真正對答案有貢獻的是一段異或的前綴，如果設計加減的運算會相互抵消，比如 $0\oplus 2?3$，一定會存在一個 $0\oplus 2+3$，后面的加 $+3$ 跟 $?3$ 就抵消掉了。
• 異或前綴 $i$ 對答案貢獻的數量是 $2\times 3^{n?i?1}$。

代碼

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e5 + 10, mod = 1e9 + 7;
int n, a[N], pre[N], pw3[N];signed main() {ios::sync_with_stdio(false); cin.tie(nullptr);cin >> n;pw3[0] = 1;for (int i = 1; i <= n; i++) {cin >> a[i];pw3[i] = pw3[i - 1] * 3 % mod;pre[i] = pre[i - 1] ^ a[i];}int ans = 0;for (int i = 1; i < n; i++) {ans = (ans + (pre[i] * 2 % mod) * pw3[n - i - 1] % mod) % mod;}ans = (ans + pre[n]) % mod;cout << ans << endl;return 0;
}

快讀模板

inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

如果題目中有的變量需要用 long long 的話，可以直接在宏里面把 int 擴展到 long long，這樣比較方便（如下圖）。

#include <bits/stdc++.h>
using namespace std;#define int long longinline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}// 代碼signed main() {// 代碼return 0;
}

對拍代碼

整個對拍需要以下文件。bf.cpp文件里是暴力代碼，std.cpp文件里是用了算法的代碼，data.cpp用來生成輸入樣例，pai.cpp用來比較bf.cpp和stdcpp.out的結果是否相同。

注意：每次更改bf.cpp，std.cpp或data.cpp之后都需要重新編譯之后再運行pai.cpp進行對拍。

接下來以輸出 a + b 的程序來說明。

bf.cpp

#include <bits/stdc++.h>
using namespace std;int main() {int a, b, oup = 0;cin >> a >> b;for (int i = 1; i <= a; i++) oup++;for (int i = 1; i <= b; i++) oup++;cout << oup;return 0;
}

std.cpp

#include <bits/stdc++.h>
using namespace std;int main() {int a, b;cin >> a >> b;if (a > 0) cout << a << endl;cout << a + b << endl;return 0;
}

data.cpp

#include <bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(rng);
}int main() {srand(time(0));int a = rand(1, 100000000), b = rand(1, 100000000); // 隨機生成兩個數字cout << a << ' ' << b << endl; // 按照格式輸出return 0;
}

pai.cpp

可以不用自己創建txt文件，編譯運行一次 pai.cpp 之后會自動生成相應 txt 文件。

#include <bits/stdc++.h>
using namespace std;int main() {int t = 1;while (1) {printf("test%d: ", t++);system("data.exe > in.txt"); // 用 data.exe 生成輸入樣例，并存入 in.txt 文件中system("std.exe < in.txt > stdout.txt");// 將 in.txt 文件中的輸入樣例用來測試 std.cpp 中的代碼，并將結果輸出到 stdout.txt 文件中system("bf.exe < in.txt > bfout.txt");// 將 in.txt 文件中的輸入樣例用來測試 bf.cpp 中的代碼，并將結果輸出到 bf.out 文件中// 比較 stdout.txt 和 bfout.txt 文件是否一樣，一樣返回 false，不一樣返回 trueif (system("fc stdout.txt bfout.txt")) return 0;}
}

下圖是 pai.cpp 運行后的輸出結果，會顯示 WA 和輸出不一樣的地方。

如果輸出樣例一樣的話，會一直顯示找不到差異。

這個時候接著寫下一道題就好了，讓它在后臺接著運行，有可能后面會出現不一樣的地方。