聲明

本題解為退役蒻茍所寫，不保證正確性，僅供參考。

花了大概2個半小時寫完，感覺比去年省賽簡單，難度大概等價于 codeforces dv4.5 吧

菜雞不熟悉樹上背包，調了一個多小時

題目旁邊的是 cf 預測分

所有代碼均以通過洛谷藍橋杯同步題

A題

算一下弧長和半徑即可得 1576

B題

正解 $2^{1022}\mathrm{mod}10^9+7=781448427$

C: 可分解的正整數 （1000）

問題描述
判斷給定正整數能否表示為長度≥3的連續整數序列之和。

輸入格式

• 第一行：正整數N。
• 第二行：N個正整數A1,A2,…,AN。

輸出格式
可分解的正整數數量。

樣例輸入

3
3 6 15

樣例輸出
3

評測用例規模

1≤N≤105，1≤Ai≤109。

題解

打一下表發現 106 以內所有數除了 1 以外都可以這樣分解，因此答案即為非 1 的數的數量

#include <bits/stdc++.h>using namespace std;
void solve()
{int n;cin >> n;int ans = n;for (int i = 0; i < n; i++){int x;cin >> x;if (x == 1)ans--;}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

---

D: 產值調整 (1000)

問題描述
三礦山產值A,B,C每年按以下規則調整K次：

1. $A\prime =?(B+C)/2?$
2. $B\prime =?(A+C)/2?$
3. $C\prime =?(A+B)/2?$

輸入格式

• 第一行：測試用例數T。
• 每行：A,B,C,K。

輸出格式
調整后的A,B,C。

樣例輸入

2
10 20 30 1
5 5 5 3

樣例輸出

25 20 15
5 5 5

評測用例規模

$1\le T\le 10^5$，$1\le A,B,C,K\le 10^9$。

題解

觀察發現 A,B,C 都在向 $\frac{A+B+C}{3}$ 收斂，且速度很快，所以模擬一下直到三個相等即可。

#include <bits/stdc++.h>using namespace std;using ll = long long;
void solve()
{ll A, B, C, K;cin >> A >> B >> C >> K;while (K--){ll NA = (B + C) >> 1;ll NB = (A + C) >> 1;ll NC = (A + B) >> 1;A = NA, B = NB, C = NC;if (A == B && B == C)break;}cout << A << " " << B << " " << C << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;std::cin >> _;while (_--){solve();}return 0;
}

---

E: 畫展布置 (1200)

問題描述
從N幅畫中選M幅排列，最小化藝術價值變化程度$L={\sum }_{M?1}^{i=1}|B_{i+1}^2?B_i^2|$ 。

輸入格式

• 第一行：N和M。
• 第二行：N個藝術價值A1,A2,…,AN。

輸出格式
L的最小值。

評測用例規模

$2\le M\le N\le 10^5;1\le Ai\le 10^5$。

題解

題目要求從 N 幅畫中選出 M 幅，并排成一列，使得藝術價值變化程度$L={\sum }_{M?1}^{i=1}|B_{i+1}^2?B_i^2|$ 最小。

注意到只要將選中的畫按某種順序排列，如果能讓各個相鄰畫作的 “平方值” 單調變化，則$L=B_M^2?B_1^2$,

其中 B12 和 BM2 分別是選中畫作中最小和最大的平方值。

因為對于任意一個選定的集合，無論中間順序如何，若將它們重新排序為“平方值”遞增的順序，其變化總和必定為$\max (B_i^2)?\min (B_i^2)$

#include <bits/stdc++.h>using namespace std;using ll = long long;
void solve()
{int N, M;cin >> N >> M;vector<ll> A(N), S(N);for (int i = 0; i < N; i++){cin >> A[i];S[i] = A[i] * A[i];}sort(S.begin(), S.end());ll ans = LLONG_MAX;for (int i = 0; i + M - 1 < N; i++){ll diff = S[i + M - 1] - S[i];if (diff < ans)ans = diff;}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

---

F: 水質檢測 (1600)

問題描述
在2×n河床上添加最少檢測器，使所有檢測器連通。

輸入格式

• 兩行：每行長度為n的字符串，#表示檢測器，.表示空白。

輸出格式
最少需添加的檢測器數。

樣例輸入

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

樣例輸出
5

評測用例規模

1≤n≤106

題解

貪心解不可行，正解是dp。

對于每一列 i，我們先根據輸入得到該列的檢測器狀態。

• 若第 1 行第 i 個位置為 #，則該列有上檢測器，對應二進制位 1， $sta[i]|=1$
• 若第 2 行第 i 個位置為 #，則該列有下檢測器，對應二進制位 2， $sta[i]|=2$

我們可以在每一列中選擇是否添加檢測器。由于我們要求連通，我們考慮只在從最左側出現強制檢測器的列到最右側出現強制檢測器的列這一連續區間內填充檢測器。

在每一列，我們可以的最終狀態是：

在該列放置檢測器的情況用一個二進制數表示（1 表示上有檢測器，2 表示下有檢測器，3 表示兩行都有）；我們規定空列是不允許的，因為中斷列會導致連通性斷裂。因此在每一列的狀態可以是 1、2 或 3。

設區間 [L, R] 為所有存在強制檢測器的列的最小與最大列號。如果沒有任何強制檢測器，則答案為 0 。

令 $dp[i][j]$ 表示從列 L 到列 i，將第 i 列狀態設為 j 且保證前后連通時的最小添加數。狀態 j 只能取 1、2、3，但必須滿足與 sta[i] 匹配。

轉移方程：
對于第 i 列，遍歷其允許狀態 j，再枚舉前一列 i?1 允許的狀態 k 滿足 j&k≠0 ，則

$dp[i][j]=mindp[i?1][k]+calc(j,k)$

設狀態 j 取值為 1、2、3。在列 k，若我們選擇狀態 j，則需要補充的檢測器數量為

$calc(j,k)=popcount(k)?popcount(sta[j])$

其中 popcount 是狀態中 1 的個數。例如：若 sta[i] = 0，狀態 1 或 2 費用為 1，狀態 3 費用為 2；若 sta[i] = 1，則狀態 1 費用為 0，狀態 3 費用為 1；以此類推。

#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;void solve()
{string s1, s2;cin >> s1 >> s2;int n = s1.size();vector<int> sta(n);for (int i = 0; i < n; i++){if (s1[i] == '#')sta[i] |= 1;if (s2[i] == '#')sta[i] |= 2;}int L = n, R = -1;for (int i = 0; i < n; i++){if (sta[i] != 0){L = min(L, i);R = max(R, i);}}if (R == -1){cout << 0 << "\n";return;}vector<vector<int>> dp(n, vector<int>(4, inf));auto calc = [&](int p, int t) -> int{int cnt = 0;if (t & 1)cnt++;if (t & 2)cnt++;int num = 0;if (sta[p] & 1)num++;if (sta[p] & 2)num++;return cnt - num;};auto check = [&](int x, int t) -> bool{return (t & sta[x]) == sta[x] && (t != 0);};for (int i = 1; i < 4; i++){if (check(L, i))dp[L][i] = calc(L, i);}for (int i = L + 1; i <= R; i++){for (int j = 1; j < 4; j++){if (!check(i, j))continue;int add = calc(i, j);for (int k = 1; k < 4; k++){if (!check(i - 1, k))continue;if ((k & j) == 0)continue;dp[i][j] = min(dp[i][j], dp[i - 1][k] + add);}}}int ans = inf;for (int i = 1; i < 4; i++){if (check(R, i))ans = min(ans, dp[R][i]);}cout << ans << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

---

G: 生產車間 (1800)

問題描述
樹形結構設備網絡，葉節點生產材料，根節點打包成品。調整節點使所有節點產能不超限，求根節點最大打包量。

輸入格式

• 第一行：設備數n。
• 第二行：各節點權值w1,w2,…,wn。
• 后續n?1行：樹邊。

輸出格式
根節點的最大成品量。

樣例輸入

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

樣例輸出
8

評測用例規模

$1\le n\le 10^3;1\le wi\le 10^3$

題解

跑一下樹上背包即可，需要使用bitset優化。

對于每個節點 u，構造一個布爾數組 $f[u][x]$ ， $f[u][x]=true$ 表示在節點 u 被保留的情況下，通過對其子樹的合理保留或刪除，可以使得從 u 的所有子樹傳上來的材料總量達到 x， x≤w[u] 。
具體的狀態轉移為：

葉節點：只有兩種選擇

• 刪除該節點，貢獻 0（即 $f[u][0]=true$ ）
• 保留該節點，則其實際“產出”就是 w[u] 。

內部節點：初始時沒有選擇任何子樹，狀態為 0；
遍歷每個子節點 v，其返回的狀態集合 g 表示了子樹可能傳上的材料量，利用類似于背包的思路將不同子節點的貢獻累加，但總和不能超過該節點的 w[u] 。

最終，在根節點處， f[1] 為打包能力，答案即為根節點的狀態數組中能達到的最大流量值

#include <bits/stdc++.h>using namespace std;
void solve()
{int n;cin >> n;vector<int> w(n + 1);for (int i = 1; i <= n; i++){cin >> w[i];}vector<vector<int>> adj(n + 1);for (int i = 1; i <= n - 1; i++){int u, v;cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}adj[1].push_back(0);function<vector<bool>(int, int)> dfs = [&](int u, int fa) -> vector<bool>{vector<bool> f(w[u] + 1);if (adj[u].size() == 1){f[0] = true;if (w[u] <= w[u])f[w[u]] = true;return f;}f[0] = true;for (auto &v : adj[u]){if (v == fa)continue;vector<bool> g = dfs(v, u);vector<bool> h(w[u] + 1);for (int i = 0; i <= w[u]; i++){if (!f[i])continue;for (int j = 0; j < g.size(); j++){if (g[j] && i + j <= w[u])h[i + j] = true;}}f.swap(h);}return f;};vector<bool> res = dfs(1, 0);int ans = 0;for (int i = 0; i <= w[1]; i++){if (res[i])ans = max(ans, i);}cout << ans << "\n";
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}

---

H: 裝修報價 （1600）

問題描述

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

然而，當老王提交數據后，他發現這套系統的運作方式并不透明：系統只會給出一個最終報價，而不會公開任何運算過程或中間步驟。公司對此解釋稱，這套系統會依據某種內部算法，在每對相鄰數字之間插入 +（加法）、?（減法）或 ⊕（異或）運算符，并按照特定優先級規則計算結果：異或運算優先級最高，其次是加減。

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

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

輸入格式

• 第一行輸入一個整數 N，表示裝修相關費用的項數。
• 第二行輸入 N 個非負整數 A1,A2,…,AN，表示各項費用。

輸出格式

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

示例輸入

3
0 2 5

示例輸出

11

示例說明

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

• 0⊕2⊕5=7
• 0⊕2+5=7
• 0⊕2?5=?3
• 0+2⊕5=7
• 0+2+5=7
• 0+2?5=?3
• 0?2⊕5=?7
• 0?2+5=3
• 0?2?5=?7

所有結果的總和為：

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

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

評測用例規模

$1\le N\le 10^5,1\le A_i\le 10^9$

題解

注意到：

• 在所有 ⊕ 連續的段內，其結果就是該段內所有數的異或值；
• 在相鄰段之間的運算符為加或減，由于加減具有線性性質（先計算異或段，后做加減運算）可以發現，最終結果實際上為各“段”值的加權和，其中只有最左邊那一段的符號“固定為 +”，而后續各段由于加減符號正負會相互抵消后求和。

具體看“分段”：

• 定義：設在相鄰位置處如果選用非 ⊕ 運算符，則視為“斷開”，形成新段。
• 因為每個位置獨立選運算符，所以可以將所有可能的運算符組合看成對 N?1 個空位的選擇，每個位置可以“接續”（即選 ⊕）或“斷開”（即選加或減），而“斷開”時又有 2 種符號選擇。

觀察發現：

• 若整個序列中沒有斷開，則只有一段，其結果為
  G=A1⊕A2⊕?⊕AN
• 若第一個斷開出現在位置 j（也就是說從 A1 到 Aj 連續使用 ⊕），則第一段的“段值”為
  G1=A1⊕A2⊕?⊕Aj

而后面不論如何選擇（剩余位置隨意），在加減階段由于正負相互抵消，其對總和的貢獻在對所有符號取和時，只有第一段的值會“留下”。 具體地：

• 固定第一斷開出現在 j 的情況下，對于前 j?1 個間隙，必須全選 ⊕（1 種方式）；
• 第 j 個空位選斷開，有 2 種符號選擇；
• 對于位置 $j+1,\dots ,N?1$ 每個空位可任意選（3 種方式），總數為$3^{N?1?j}$.

故滿足“第一斷開位置為 j "的方案數為$2?3^{N?1?j}$

對于這些方案，最終計算（加減累加時）會固定地把第一段 G1 加入結果中（其他段各自正負總和為 0）。

于是，把所有方案按照是否出現斷開以及第一斷開的位次分情況討論，最后所有可能最終結果的總和 S 為

無斷開$S=G_{無斷開}+{\sum }_{N?1}^{j=1}(2?3^{N?1?j})?(A_1\oplus A_2\oplus ?\oplus A_j)$.

這里 $G=A_1\oplus A_2\oplus ?\oplus A_N$。

#include <bits/stdc++.h>using namespace std;using ll = long long;const ll mod = 1000000007;
ll qmi(ll x, ll k, ll p = mod)
{x %= p;ll res = 1;while (k > 0){if (k & 1)res = (res * x) % p;x = (x * x) % p;k >>= 1;}return res;
}
void solve()
{int n;cin >> n;vector<ll> a(n + 1);vector<ll> preXor(n + 1, 0);for (int i = 1; i <= n; i++){cin >> a[i];preXor[i] = preXor[i - 1] ^ a[i];}vector<ll> p3(n);p3[0] = 1;for (int i = 1; i < n; i++){p3[i] = (p3[i - 1] * 3) % mod;}ll ans = preXor[n] % mod;for (int i = 1; i < n; i++){ll t = ((2ll * p3[n - 1 - i]) % mod * preXor[i]) % mod;ans = (ans + t) % mod;}cout << (ans % mod + mod) % mod << "\n";
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;// std::cin >> _;while (_--){solve();}return 0;
}