【官方题解】StarryCoding 入门教育赛 2 | acm | 蓝桥杯 | 新手入门

比赛传送门：

本场比赛开始时题面存在一些问题，私密马赛！

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;
}