20191009测试总结

T1：SOJ 2197

很傻的一个背包问题，没啥好说的

#include <iostream>
#include <cstdio>
using namespace std;
int s, sum, f[1005];
int main()
{
    scanf("%d", &s);
    for (int i = 1; i <= s; ++i)
    {
        sum = 0;
        for (int j = 1; j < i; ++j)
            if (i % j == 0)
                sum += j;
        for (int j = s; j >= i; --j)
            f[j] = max(f[j], f[j - i] + sum);
    }
    printf("%d", f[s]);
    return 0;
}

T2：SOJ 2198

首先二分一下答案，然后每个数剪掉这个答案，单调队列维护一下i-l到i-r的最小值，寻找有没有大于0的区间即可

考场上面傻了一下，没想到二分答案，最后打了个暴力走人

#include<iostream>
#include<cstdio>
#define eps 0.000001
using namespace std;
int n, l, r, a[100005], q[100005];
double lef, rig, sum[100005], num[100005];
bool check(double k)
{
    double ans=0;
    for(int i=1;i<=n;++i)
    {
        num[i]=a[i]-k;
        sum[i]=sum[i-1]+num[i];
    }
    int h=1, t=0;
    for(int i=1;i<=n;++i)
    {
        while(h<=t&&i-q[h]>r)
            ++h;
        if(i>=l)
        {
            while(h<=t&&sum[q[t]]>sum[i-l])
                --t;
            q[++t]=i-l;
            ans=max(ans, sum[i]-sum[q[h]]);
        }
    }
    return ans>0;
}
int main()
{
    scanf("%d%d%d", &n ,&l, &r);
    for(int i=1;i<=n;++i)
    {
        scanf("%d", &a[i]);
        if(i==1)
            lef=rig=a[i];
        else
        {
            lef=min(lef, (double)a[i]);
            rig=max(rig, (double)a[i]);
        }
    }
    while(lef+eps<rig)
    {
        double mid=(lef+rig)/2;
        if(check(mid))
            lef=mid;
        else
            rig=mid;
    }
    printf("%.4f", lef);
    return 0;
}

T3：SOJ 2199

用一个类似寻找最小生成树的方法寻找基环树即可。对于一条边，如果两个节点在同一颗树且没有环，就合并，如果两个节点不在同一棵树且两个树上共有一个环，那么也合并。这样就可以找出和最小的情况了。

考场上没有考虑第二种情况，100→50，然后m和n打反，50→0，我大概没有睡清醒。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, fa[500005], huan[500005];
long long ans;
struct node
{
    int a;
    int b;
    int c;
} num[500005];
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
bool cmp(node aa, node bb)
{
    return aa.c < bb.c;
}
int getfather(int x)
{
    if (fa[x] == x)
        return x;
    fa[x] = getfather(fa[x]);
    return fa[x];
}
int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        num[i].a = read();
        num[i].b = read();
        num[i].c = read();
    }
    sort(num + 1, num + m + 1, cmp);
    for (int i = 1; i <= m; ++i)
        if (getfather(num[i].a) != getfather(num[i].b) && (!huan[getfather(num[i].a)] || !huan[getfather(num[i].b)]))
        {
            if (huan[getfather(num[i].a)])
                huan[getfather(num[i].b)] = 1;
            fa[getfather(num[i].a)] = getfather(num[i].b);
            ans = ans + num[i].c;
        }
        else if (!huan[getfather(num[i].a)])
        {
            huan[getfather(num[i].a)] = 1;
            ans = ans + num[i].c;
        }
    for (int i = 1; i <= n; ++i)
        if (!huan[getfather(i)])
        {
            printf("No");
            return 0;
        }
    printf("%lld", ans);
    return 0;
}