比賽傳送門：

本場比賽開始時題面存在一些問題，私密馬賽！

A.池化【入門教育賽】

根據題目所給公式計算即可。

#include "bits/stdc++.h"signed main() {int t; std::cin >> t;while (t --) {int l, k, s, p; std::cin >> l >> k >> s >> p;int ans = floor((l + 2 * p - k) / s) + 1;std::cout << ans << "\n";}
}

B. 牢e買黃金【入門教育賽】

枚舉賣點$i$，那么僅需找到數組$a$的區間$[1,i?1]$的最小值，維護一個前綴最值即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
using ll = long long;
ll a[N];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, x;cin >> n >> x;for(int i = 1;i <= n;++ i)cin >> a[i];ll mi = a[1], ans = 0;for(int i = 1;i <= n; ++ i){ans = max(ans, a[i] - mi);mi = min(mi, a[i]);}cout << ans * x << '\n';return 0;
}

C.前綴序列【入門教育賽】

思維題，我們從右往左考慮，對于$i$，若$a_i$為負數，就直接將其取相反數就好了，至多$n$次一定可以使得所有元素為非負整數，所以答案就是所有元素的絕對值之和。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
using ll = long long;
ll a[N];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n;cin >> n;for(int i = 1;i <= n;++ i)cin >> a[i];ll ans = 0;for(int i = 1;i <= n; ++ i)ans += (a[i] < 0 ? -a[i] : a[i]);cout << ans << '\n';return 0;
}

D.相鄰最大公約數【入門教育賽】

動態規劃，定義狀態$dp[i][j]$表示$a_i$是否增加$x$（若$j=0$則沒加$x$，反之則加了）的情況下區間$[1,i]$相鄰$gcd$之和。

$dp[i][0]$可以從$dp[i?1][0]$和$dp[i?1][1]$轉移過來，$dp[i][1]$亦同。

狀態轉移方程請見代碼，注意從$2$開始轉移。

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const int N = 1e5 + 9;
ll dp[N][2], a[N];ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, x;cin >> n >> x;for(int i = 1;i <= n; ++ i)cin >> a[i];for(int i = 2;i <= n; ++ i){dp[i][0] = max(dp[i - 1][0] + gcd(a[i - 1], a[i]), dp[i - 1][1] + gcd(a[i - 1] + x, a[i]));dp[i][1] = max(dp[i - 1][0] + gcd(a[i - 1], a[i] + x), dp[i - 1][1] + gcd(a[i - 1] + x, a[i] + x));}cout << max(dp[n][0], dp[n][1]) << '\n';
}

E.基環樹【入門教育賽】

基環樹找環模板題，可用dfs或拓撲排序完成。

dfs解法：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], n;
vector<int> g[N];
bitset<N> vis;
stack<int> stk;
ll ans;bool dfs(int x, int fa){vis[x] = true;stk.push(x);for(const auto &y : g[x]){if(y == fa)continue;if(vis[y]){while(stk.size()){int t = stk.top();stk.pop();ans += a[t];if(t == y)break;}return true;}if(dfs(y, x))return true;}stk.pop();return false;
}int main()
{cin >> n;for(int i = 1;i <= n; ++ i)cin >> a[i];for(int i = 1;i <= n; ++ i){int x, y;cin >> x >> y;if(x == y){cout << a[x] << '\n';return 0;}g[x].push_back(y), g[y].push_back(x);}if(n <= 2){ll ans = 0;for(int i = 1;i <= n; ++ i)ans += a[i];cout << ans << '\n';return 0;}dfs(1, 0);cout << ans << '\n';return 0;
}

拓撲排序做法：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], ind[N], n;
vector<int> g[N];void topo(){queue<int> q;for(int i = 1;i <= n; ++ i){if(ind[i] == 1)q.push(i);}while(q.size()){int x = q.front();q.pop();for(const auto &y : g[x]){if(-- ind[y] == 1)q.push(y);}}
}int main()
{cin >> n;for(int i = 1;i <= n; ++ i)cin >> a[i];set<pair<int, int> > st;for(int i = 1;i <= n; ++ i){int x, y;cin >> x >> y;if(x == y){cout << a[x] << '\n';return 0;}g[x].push_back(y), g[y].push_back(x);ind[x] ++, ind[y] ++;}if(n <= 2){ll ans = 0;for(int i = 1;i <= n; ++ i)ans += a[i];cout << ans << '\n';return 0;}topo();ll ans = 0;for(int i = 1;i <= n; ++ i)if(ind[i] == 2)ans += a[i];cout << ans << '\n';return 0;
}