T1: 最大约数和
给定一个正整数 S, 现在要求你选出若干个互不相同的正整数, 使得它们的和不大于 S, 而且每个数的因数 (不包括本身) 之和最大. S <= 1000
分析:
其实考完才听他们说是背包, 不过也没差了, 不管了
首先约数和 \(sum\)是可以预处理的, 用类似埃氏筛的方式枚举一下然后累加一下
然后发现有很明显的阶段, 考虑 \(dp\)
\(f[i] = f[j] + sum[i - j], 0 <= j <= i\)
代码:
- #include<bits/stdc++.h>
- #define N (1000 + 10)
- #define int long long
- using namespace std;
- int n;
- int f[N], sum[N];
- signed main() {
- freopen("sum.in", "r", stdin);
- freopen("sum.out", "w", stdout);
- scanf("%lld", &n);
- for (register int i = 1; i <= n; ++i)
- for (register int j = 2; i * j <= n; ++j) sum[i * j] += i;
- for (register int i = 1; i <= n; ++i)
- for (register int j = 0; j <= i; ++j) f[i] = max(f[i], f[j] + sum[i - j]);
- printf("%lld", f[n]);
- return 0;
- }
T2: 最佳序列
给一个长度为 n 的数组 A, 给定 L, R, 求所有满足长度大等于 L, 小等于 R 的 A 数组的子区间的平均值的最大值. n <= 1e5
分析:
考场没思路, 前缀和 + 枚举区间长度 \(60pts\)走人
观察数据范围可以套一个 \(log\), 试试二分平均值
怎么 \(check\)呢
每次重构前缀和数组 \(sum\), 在前缀和数组上减去二分的 \(mid\), 那么问题转化为判断区间上有没有一段长度在 \([L, R]\)之间的区间最小值大于 \(0\)
枚举右端点 \(i\), 则左端点的可能区间为 \([i - R, i - L]\), 区间和为 \(sum[i] - sum[左端点 - 1]\)
对于每一个枚举的 \(i\),\(sum[i - L]\)相当于一个定值, 那么维护 \(sum[左端点 - 1]\)的最小值, 若其能使区间和 \(>=0\)则答案合法, 否则答案不合法
维护最小值用单调队列
代码:
- #include<bits/stdc++.h>
- #define N (500000 + 10)
- using namespace std;
- inline int read() {
- int cnt = 0, f = 1; char c = getchar();
- while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
- while (isdigit(c)) {cnt = (cnt <<3) + (cnt << 1) + (c ^ 48); c = getchar();}
- return cnt * f;
- }
- int n, L, R, head, tail;
- double a[N], sum[N], q[N], pos[N], gmax;
- bool check(double r) {
- memset(q, 0, sizeof q);
- memset(sum, 0, sizeof sum);
- head = 1, tail = 0;
- for (register int i = 1; i <= n; ++i) sum[i] = 1.0 * a[i] - r + sum[i - 1];
- for (register int i = L; i <= n; ++i) {
- while (head <= tail && q[tail]>= sum[i - L]) --tail;
- while (head <= tail && pos[head] + R <i) ++head;
- q[++tail] = sum[i - L];
- pos[tail] = i - L;
- if (sum[i] - q[head]>= 0) return true;
- }
- return false;
- }
- int main() {
- n = read(), L = read(), R = read();
- for (register int i = 1; i <= n; ++i) a[i] = read(), gmax = max(gmax, a[i]);
- double mid;
- double l = 0, r = 1.0 * gmax;
- for(register int i = 1; i <= 100; ++i) {
- mid = (l + r) / 2;
- // cout<<mid<<endl;
- if (check(mid)) l = mid;
- else r = mid;
- }
- printf("%.4lf", mid);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3232776.html