T1：无限延展
见 P3612 [USACO17JAN]Secret Cow Code S
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
string s; ll k;
cin >> s >> k;
int n = s.size();
while (n < k) {
ll now = n;
while (now < k) now <<= 1;
now >>= 1;
k -= now+1;
if (k == 0) k = now;
}
cout << s[k-1] << '\n';
return 0;
}
T2：树的最大和
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<vector<int>> to(n);
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
--p;
to[p].push_back(i);
}
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> dp(n);
auto dfs = [&](auto& f, int v, int p=-1) -> void {
dp[v] = a[v];
for (int u : to[v]) {
f(f, u, v);
dp[v] += max<ll>(0, dp[u]);
}
};
dfs(dfs, 0);
ll ans = numeric_limits<ll>::max() + 1;
rep(i, n) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
T3：降低均值
见 P2115 [USACO14MAR]Sabotage G
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const double eps = 1e-10;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int tot = accumulate(a.begin(), a.end(), 0);
double wa = 1, ac = 10000;
while (abs(ac-wa) > eps) {
double wj = (ac+wa)/2;
auto ok = [&]{
double t = tot-n*wj;
double now = 0;
for (int i = 1; i < n-1; ++i) {
now += a[i]-wj;
if (now >= t) return true;
if (now < 0) now = 0;
}
return false;
}();
(ok ? ac : wa) = wj;
}
printf("%.2f\n", ac);
return 0;
}