7月1日 AtCoder Regular Contest 100
题目链接: https://arc100.contest.atcoder.jp/

C – Linear Approximation

思路:
首先看到那个式子比较复杂,其实可以将它化简,把第i项减去i。然后观察式子可以发现那个值就是序列的中位数,然后直接算出答案。其实这就是那个货仓选址的模型,比较重要。

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n;
LL ans, a[200005];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]-=i;
    sort(a+1, a+n+1);
    LL t=a[(n+1)/2];
    for(int i=1; i<=n; i++)
    {
        if(a[i]-t<0) ans+=t-a[i];
        else ans+=a[i]-t;
    }
    printf("%lld\n", ans);
}

D – Equal Cut

思路:
玄学。。。首先可以枚举中间切的那一刀,由于我们希望极差最小,所以有一种感觉就是要分得尽量平均。因此对于中间的每一刀,我们可以确定出左边和右边两刀,把序列左边和右边切得更“平均”,用这个更新答案。其实有一点迷QWQ
代码:

#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 200005
using namespace std;

int n;
LL a[MAXN], ans=INF;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]+=a[i-1];
    int l=1, r=3;
    LL maxn, minn;
    for(int i=2; i<=n-2; i++)
    {
        while(a[l]<a[i]-a[l]) l++;
        while(a[r]-a[i]<a[n]-a[r]) r++;
        if(a[l-1]>a[i]-a[l]) l--;
        if(a[r-1]-a[i]>a[n]-a[r]) r--;
        maxn=max(max(a[l], a[i]-a[l]), max(a[r]-a[i], a[n]-a[r]));
        minn=min(min(a[l], a[i]-a[l]), min(a[r]-a[i], a[n]-a[r]));
        ans=min(ans, maxn-minn);
    }
    printf("%lld\n", ans);
}

E – Or Plus Max

思路:
发现自己位运算是真的菜。。。。

类似于一个DP。首先枚举下标0到1<<n,如果下标x的第i位上是0(二进制)那么它一定包含于(同样是二进制)下标 x&(1<<i)(也就是把那一位变为1)。所以可以用下标x的数来更新下标x&(1<<i)的数之前的最大值。
代码:

#include <bits/stdc++.h>
#define MAXN 300005
#define LL long long
using namespace std;

int n, f[MAXN][2];
LL ans[MAXN], a[MAXN];

void solve(int x, int y)
{
    if(f[x][0]==y || f[x][1]==y) return;
    if(a[f[x][1]]<a[y])
    {
        f[x][1]=y;
        if(a[f[x][0]]<a[f[x][1]]) swap(f[x][0], f[x][1]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=0; i<(1<<n); i++)
    {
        scanf("%lld", &a[i]);
        f[i][0]=i;
    }
    for(int i=0; i<(1<<n); i++) for(int j=0; j<n; j++)
    {
        if((i>>j)&1) continue;
        solve(i|(1<<j), f[i][0]);
        solve(i|(1<<j), f[i][1]);
    }
    for(int i=1; i<(1<<n); i++)
    {
        ans[i]=max(ans[i-1], a[f[i][0]]+a[f[i][1]]);
        printf("%lld\n", ans[i]);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注