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

2019/10/9 CSP-S 模拟测

原文：https://www.cnblogs.com/kma093/p/11644623.html